Главная » Просмотр файлов » Д. Кнут - Искусство программирования том 1

Д. Кнут - Искусство программирования том 1 (1119450), страница 9

Файл №1119450 Д. Кнут - Искусство программирования том 1 (Д. Кнут - Искусство программирования том 1) 9 страницаД. Кнут - Искусство программирования том 1 (1119450) страница 92019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

конкретную ситуацию; математики называют это эмпирическим результатом или предположением. Для того чтобы прояснить суть дела, рассмотрим еще один поучительный при-. мер. Пусть р(п) обозначает количество разбиений числа и, т. е. количество различных способов записи числа.п в виде суммы целых положительных чисел (порядок слагаемых значения не имеет). Так как для числа 5 существует ровно семь таких способов записи, т. е. 1+1+1+1+1=2+1+1+1=2+2+1=3+1+1=3+2=4+1=5. то р(5) = 7.

На самом деле установить первые пять значений функции р(п) довольно легко: р(1) = 1, р(2) = 2, р(З) = 3, р(4) = 5, р~б) = 7. На этом основании мы могли бы предварительно сформулировать по индукции предположение о том, что последовательность р(2), р(З),, пробегает множество просглмх чисел. Для проверки данной гипотезы продолжаем вычисления и находим р(6). Ура! р(6) = 11, что подтверждает наше предположение. [Но, к сожалению, оказырается, что р(7) равно 15.

Увы, все идет насмарку, и приходится начинать сначала. Известно, что значения р(п) отличаются довольно сложным поведением, хотя С. Рамануджану (Я. Вашапп1ап) удалось угадать н доказать много замечательных фактов, касающихся этих чисел. Более подробную информацию можно найти в книге С. Н. Нагду, Вашвлц)ап (Ьопдоп: СашЬгк!8е 1)п!гегв!1у Ргевв, 1940), гл. 6 и 8.] Математическая индукция не имеет ничего общего с тем индуктивным методом, который мы только что описали.

Это не догадка, а неопровержимое доказательство утверждения; скажу больше: это доказательство бесконечного числа утверждений, по одному для каждого и. пИндукциейп этот метод назван только потому, что сначала нужно выдвинуть предположение о том, чп1а нужно доказать, а ватпем уже применять метод математической индукции. Начиная с этою момента, слово пиндукцияп в книге будет использоваться только для обозначения доказательства методом математической индукции. Существует геометрический способ доказательства соотношения (2). На рис.

3 для и = 6 показано, что пт ' ! ' ' ы клеток разбиты на группы 1+3+. +(2п — 1) клеток. Но в конечном счете этот рисунок можно считать пдоказательствомп только в случае, если мы покажем, что 7 данное построение можно выполнить для любого и. А это, в сущности, и будет доказательством по индукции. В нашем доказательстве соотношения (2) был ис- в пользован только частный случай (Ь); мы просто показали, что из справедливости Р(и) следует справедли- 1 вость Р(п + 1).

Это очень важный случай, который Рис. 3. Нечетныечислав встречается довольно часто, но в следующем примере сумме дают квадрат. будут проиллюстрированы более широкие возможности метода математической индукции. Определим последовашельяосгль Фибоначчи Го, Р1, Ев, ... с помощью такого правила: Гв = О, Г1 — — 1, а каждый последующий член равен сумме двух предыдущих. Таким образом, первые члены этой последовательности выглядят так: О, 1, 1, 2, 3, 5, 8, 13, ... (более подробно мы изучим эту последовательность в разделе 1.2.8). А теперь докажем, что если через ф обозначить число (1 + Л )/2, то имеем Р < ~п — 1 (3) для всех целых положительных и.

Назовем эту формулу утверждением Р(п). Если и = 1, то Р1 — — 1 = фв = ф" ', поэтому и. (а) выполнен. Переходя к п. (Ь), заметим сначала, что Р(2) также справедливо, поскольку Рз = 1 < 1.6 < ф' = фт '. А теперь, если все Р(1), Р(2), ..., Р(п) справедливы и и > 1, то мы знаем, в частности, что справедливы Р(п — 1) и Р(п). Поэтому Рп 1 < ф" з и Гп < ф" 1 Складывая данные неравенства, получаем Рп.~-1 = Рп-1 + Рп - ф" '.! ф" ' = Ф" '(1+ ф) (4) Важное свойство числа ф, которое и является причиной первоочередною выбора этого числа для данной задачи, состоит в том, что 1+ф фз (5) Подставив (5) в (4), получим Р„ез ( ф", а это и есть утверждение Р(и + 1).

Таким образом, п. (Ь) выполнен и формула (3) доказана методом математической индукции. Обратите внимание, что п. (Ь) мы выполняли двумя различными способами: непосредсизвенно доказали Р(п + 1) при и = 1 и использовали индуктивный метод при и > 1. Это было необходимо, так как при и = 1 ссылка на Р(я — 1) = Р(О) была бы незаконной. Математическую индукцию можно использовать также для доказательства фактов, касающихся алгориньнов. Давайте рассмотрим следующее обобщение алгоритма Евклида. Алгоритм Е (06оби~еннмй алгоритм Евклида). Даны два целых положительных числа т и и. Требуется найти их наибольший общий делителье 4 и два целых числа а и Ь, таких, что ат + Ьи = с~.

Е1. [Инициализация.] Присвоить а' <- 6 з — 1, а +- 6' +- О, с ~ — т, д +- и. Е2. [Деление.] Пусть д и и — это частное и остаток от деления с на д соответственно. (Тогда с = уй+ г, где О ( г < д.) ЕЗ. [Остаток — нуль?] Если г = О, то выполнение алгоритма прекращается; в этом случае имеем азп + Ьп = 4, как и требовалось. Е4. [Повторение цикла.] Присвоить с +- е1, 4 з- г, г < — а', а' < — а, а е- с — да, г < — Ь', Ь' ~- Ь, 6+- с — 46 и вернуться к шагу Е2.

! Если изъять из алгоритма переменные а, Ь, а' и Ь' и использовать зп и и в качестве вспомогательных переменных с и И, то получим старый алгоритм 1.1Е. В новой версии алгоритма выполняется немного больше вычислений, так как необходимо определить коэффициенты а и Ь. Предположим, что т = 1 769 и и = 551. Тогда последовательно (после шага Е2) имеем: а' а 6' 6 с Н д г 1 О О 1 1769 551 3 Йзз О 1 1 -3 551 116 4 87 1 -4 -3 13 116 87 1 29 — 4 5 13 — 16 87 29 3 О Проверяя полученные результаты, убеждаемся в том, что все правильно, так как 5 х 1769 — 16 х 551 = 8845 — 8816 = 29, т. е. мы получили наибольший общий делитель чисел 1 769 и 551. Теперь нужно доказать, что рассматриваемый алгоритм работает правильно при любых из и и.

Для этого попробуем применить метод математической индукции к следующему утверждению Р(и): "Алгоритм Е дает правильное решение для заданного и и всех целых зп". Но провести подобное доказательство не так-то просто, поэтому нужно доказать сначала несколько дополнительных фактов. После Сокращеннг — код (ягеагще еооипои ой Мео~).

— Лрим. иерее. некоторого изучения проблемы выясняется, что нужно доказать какой-то факт, связанный с коэффициентами а, Ь, а' и Ь'. Этот факт заключается в том, что равенства а'т+Ь'и =с, ат+Ьп =д (6) если любое утверждение, которое соответствует стрелке, ведущей к блоку, верно до выполне>щя операция нз этого блока, то все утверждения, которые соответствуют стрелкам, ведущим от блока, также верны после выполнения операцшь (у) Согласно описанному методу для нашего примера мы должны доказать, что если до выполнения шага Е2 верно Аг либо Аб, то после выполнения этого шага верно АЯ.

(В данном случае утверждение Аг является более сильным, чем Аб, т. е. из .42 верны в каждом случае выполнения шага Е2. Данные равенства можно доказать непосредственно, заметив, что они безусловно справедливы после первого выполнения шага Е2 и что шаг Е4 не меняет это положение вещей (см. упр. 6). Теперь мы готовы индукцией по и доказать, что алгоритм Е работает правильно. Если гп кратно п, то очевидно, что алгоритм работает правильно, поскольку его работа заканчивается на шаге ЕЗ в первом же цикле и мы получаем верный результат.

Это происходит всегда, когда и = 1. Поэтому остается провести доказательство для случая, когда и > 1 и т не является кратным и. В такой ситуации в первом цикле осуществляется переход к шагу Е4 и выполняются операции присвоения с э- и, д э — г. И так как г ( и, по индукции можно предположить, что окончательное значение д — это наибольший общий делитель чисел и и г. Из доказательства, приведенного в разделе 1.1, следует, что пары (т, п) и (п,г) имеют одинаковые наибольшие общие делители и, в частности, один и тот же наибольший общий делитель. Значит, д — это наибольший общий делитель чисел т и и и согласно (6) ат + Ьп = д.

Фраза, которая в приведенном выше доказательстве выделена ку.рсивом, является иллюстрацией того общепринятого условного языка, который так часто используется в доказательствах методом индукции, Например, выполняя и. (Ь), вместо того чтобы сказать "Теперь предположим, что утверждения Р(1),Р(2),...,Р(п) справедливы, и на этом основании докажем справедливосты тверждения Р(и+ 1)", мы будем говорить просто "Теперь докажем утверждение Р(п); по индукции мм лэожем предположить, что Р(Ь) верно для любого 1 < lс ( и". Если хорошо вдуматься и посмотреть на все вышесказанное с несколько иной точки зрения, то перед нами предстанет общий метод доказательства корректности любого алгоритма. Идея состоит в том, чтобы взять блок-схему некоторого алгоритма и к каждой стрелке добавить примечание о текущем состоянии дел в тот момент, который соответствует стрелке.

На рис. 4 эти примечания (мы их будем называть также утверждениями) обозначены через А1, Ай, ...., Аб. (Все они сделаны при дополнительном условии, что переменные принимают только целые значения: зто условие опущено с целью экономии места.) В утверждении А1 даются первоначальные предположения о входных данных алгоритма, а в А4 формулируется положение о том, что мы хотим доказать по поводу выходных значений а, Ь и д. Общий метод заключается в том, чтобы для каждого блока на блок-схеме доказать следующее: - — — А1! тп>0, п>0. АЯ! с=та >О, 4=и > О, а= 6! =О, а' =Ь= К вЂ” — А Я! ат + Ьп = и, а'т + Ь'и = с = 04 + г, О < г < д, Осд(с, 4) = ясд(т, п).

---А4! ат+ 6п=к=бсд(т,п). — — - — А5! ат+ Ьп= 4, а т+ Ь п=с=ап+ г О < г < 4, ясй(с, 4) = Осй(т, и). -Аб! ат+ 6п = 4, а т+ Ьп = с, 4>0, йсй(с, 4) = Оса(т, п). Рис. 4. Блок-схема алгоритма Е, дополненная примечаниями, которые доказывают правильность работы алгоритма. следует Аб. Поэтому нам достаточно доказать, что выполнение Аб до шага Е2 влечет за собой выполнение АЯ после этого шага.

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее