Методические указания к выполнению контрольных работ по дисциплине "Основы программирования" (стр. 7 из 40)

Действие I 4. Увеличить k. Увеличить k на 1 и перейти к шагу I 2. ô Поскольку этот алгоритм выдает доказательство утверждения Р(п) для любого заданного п, метод доказательства, сформулированный в пп. (а) и (b), логически обоснован. Он называется доказательством методом математической индукции.

Понятие математической индукции следует отличать от того, что в научной практике обычно называют индуктивным методом. Данный метод заключается в том, что ученый делает некоторые наблюдения и создает «по индукции» общую теорию или выдвигает гипотезу, объясняющую эти факты. Например, на основании пяти соотношений (1.4), приведенных выше, мы могли бы сформулировать соотношение (1.5). В этом смысле индукция – не более чем догадка или попытка объяснить конкретную ситуацию; математики называют это эмпирическим результатом или предположением.

Для того чтобы прояснить суть дела, рассмотрим еще один поучительный пример. Пусть р(п) обозначает количество разбиений числа п, т.е. количество различных способов записи числа п в виде суммы целых положительных чисел (порядок слагаемых значения не имеет). Так как для числа 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)=3, р(4) = 5, р(5) = 7.

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

Математическая индукция не имеет ничего общего с тем индуктивным методом, который мы только что описали. «Индукцией» этот метод назван только потому, что сначала нужно выдвинуть предположение о том, что нужно доказать, а затем уже применять метод математической индукции. Начиная с этого момента, слово «индукция» будет использоваться только для обозначения доказательства методом математической индукции.

Есть еще одно доказательство соотношения (1.5). На рис. 1.3 для п = 6 показано, что п² клеток разбиты на группы 1 + 3 + (2n – 1) клеток. Но, в конечном счете, этот рисунок можно считать «доказательством» только в случае, если мы покажем, что данное построение можно выполнить для любого п. А это, в сущности, и будет доказательством по индукции.

В нашем доказательстве соотношения (1.5) был использован только частный случай (b); мы просто показали, что из справедливости Р(п) следует справедливость Р(п+1). Это очень важный случай, который встречается довольно часто, но в следующем примере будут проиллюстрированы более широкие возможности метода математической индукции.

Пример 1-3. Числа Фибоначчи.

Определим последовательность Фибоначчи F₀, F₁, F₂, ..., F₂ с помощью такого правила: F₀ = 0, F₁ = 1, а каждый последующий член равен сумме двух предыдущих. Таким образом, первые члены этой последовательности выглядят так: 0, 1, 1, 2, 3, 5, 8, 13, ... . Далее введем обозначение:

. (1.6)

Докажем, что неравенство

справедливо для всех целых положительных чисел n. Назовем эту формулу утверждением P(n).

Если n = 1, то F₁= 1 = f⁰ = f ^{n – 1} , поэтому п. (а) выполнен.

Переходя к п. (б), заметим сначала, что Р(2) также справедливо, поскольку F₁ = 1 < 1.6 < f¹ = f ^{2 – 1}. А теперь, если все Р(1), Р(2), ..., Р(п) справедливы и п > 1, то мы знаем, в частности, что справедливы Р(п – 1) и Р(п). Поэтому

и

. Складывая данные неравенства, получаем:

. (1.7)

Важное свойство числа ф, которое и является причиной первоочередного выбора этого числа для данной задачи, состоит в том, что

1 + f = f². (1.8)

Подставив (1.8) в (1.7), получим

, а это и есть утверждение Р(п+1). Таким образом, п. (b) выполнен, и формула (1.6) доказана методом математической индукции. Обратите внимание, что п. (b) мы выполняли двумя различными способами: непосредственно доказали Р(п + 1) при п=1 и использовали индуктивный метод при п > 1. Это было необходимо, так как при п=1 ссылка на Р(п – 1) = Р(0) была бы незаконной.

1.4. Обобщенный алгоритм Евклида

Пример 1-4. Математическую индукцию можно использовать также для доказательства фактов, касающихся алгоритмов. Давайте рассмотрим следующее обобщение алгоритма Евклида.

Алгоритм Е (обобщенный алгоритм Евклида). Даны два целых положительных числа m и b. Требуется найти их наибольший общий делитель d и два целых числа а и b, таких, что am + bn = d.

Действие E l. Инициализация.

Присвоить а' ¬ b ¬ 1, а ¬ b' ¬ 0, с ¬ т, d ¬ n.

Действие Е 2. Деление.

Пусть q и r – это частное и остаток от деления с на d соответственно. Тогда

с = qd + r, где 0 £ r < d.

Действие Е З. Остаток – это нуль?

Если r = 0, то выполнение алгоритма прекращается; в этом случае имеем

am + bn = d,

как и требовалось.

Действие Е 4. Повторение цикла.

Присвоить

с ¬ d, d ¬ r, t ¬ а', а' ¬ а, а ¬ (t – qa), t ¬ b', b' ¬ b, b ¬ (t – qb)

и вернуться к шагу Е2.

Если изъять из алгоритма переменные а, b, а' и b' и использовать m и n в качестве вспомогательных переменных с и d, то получим старый алгоритм Е (см. параграф 1.1). В новой версии алгоритма выполняется немного больше вычислений, так как необходимо определить коэффициенты a и b. Предположим, что m = 1769 и n = 551. Тогда последовательно (после шага Е 2) имеем:

а'	a	b'	b	c	d	q	r
1	0	0	1	1769	551	3	116
0	1	1	– 3	551	116	4	87
1	– 4	– 3	13	116	87	1	29
– 4	5	13	– 16	87	29	3	0

Проверяя полученные результаты, убеждаемся в том, что все правильно, так как 5 ´ 1769 - 16 ´ 551 = 8845 - 8816 = 29, т.е. мы получили наибольший общий делитель чисел 1769 и 551.

Теперь нужно доказать, что рассматриваемый алгоритм работает правильно при любых т и п. Для этого попробуем применить метод математической индукции к следующему утверждению Р(п): «Алгоритм Е дает правильное решение для заданного n и всех целых m». Но провести подобное доказательство не так-то просто, поэтому нужно доказать сначала несколько дополнительных фактов. После некоторого изучения проблемы выясняется, что нужно доказать какой-то факт, связанный с коэффициентами а, b, а' и b'. Этот факт заключается в том, что равенства

а'т + b'п = с, am + bn = d (1.9)

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

Теперь мы готовы индукцией по п доказать, что алгоритм Е работает правильно. Если т кратно п, то очевидно, что алгоритм работает правильно, поскольку его работа заканчивается на шаге ЕЗ в первом же цикле и мы получаем верный результат. Это происходит всегда, когда n = 1. Поэтому остается провести доказательство для случая, когда п > 1 и т не является кратным п. В такой ситуации в первом цикле осуществляется переход к шагу Е4 и выполняются операции присвоения с ¬ п, d ¬ r. И так как r < п, по индукции можно предположить, что окончательное значение d – наибольший общий делитель чисел п и r. Из доказательства, приведенного в параграфе 1.2. следует, что пары {т,п} и {п,r} имеют одинаковые наибольшие общие делители и, в частности, один и тот же наибольший общий делитель. Значит, d – это наибольший общий делитель чисел m и n и согласно (1.9) am + bn = d.