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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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 влечет за собой выполнение АЯ после этого шага.

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

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