Урок 35
Доказательство правильности программ
(§37. Доказательство правильности программ)
Содержание урока
Как доказать правильность программы?
Алгоритм Евклида
Алгоритм Евклида
Теперь докажем, что один из древнейших известных алгоритмов — алгоритм Евклида — действительно вычисляет наибольший общий делитель (НОД) двух натуральных чисел (мы рассматривали его в 10 классе).
Алгоритм Евклида. Пусть заданы два натуральных числа т и п, причём ; m ≥ n для вычисления НОД(m, n) следует многократно заменять большее число остатком от деления большего на меньшее до тех пор, пока меньшее число не станет равным нулю. Тогда оставшееся ненулевое число и есть НОД(m, n).
Программа, основанная на алгоритме Евклида, может выглядеть, например, так (здесь а, b и r — целочисленные переменные):
Докажем, что в результате этого алгоритма в переменной а находится НОД(m, n).
В строке 1 исходные значения копируются из переменных m и n соответственно в переменные а и b. Очевидно, что при этом выполнено условие НОД(а, b) = НОД(m, n).
На каждом шаге цикла (в строках 3-4) вычисляется остаток г от деления а на b и пара (а, b) заменяется на пару (b, r). Какими свойствами обладают полученные значения b и r?
Поскольку r — это остаток от деления а на b, до выполнения строк 3-4 было справедливо равенство а = bр + r, где р — некоторое целое число. Тогда, если а и b имеют общий делитель, то такой же делитель имеет и r. Следовательно, НОД(b, r) = НОД(а, b) = = НОД(m, n). Это значит, что условие НОД(а, b) = НОД(m, n) по-прежнему выполняется после каждого шага цикла.
Поскольку остаток r с каждым шагом строго уменьшается, в конце концов он станет равным нулю и запишется в переменную b при выполнении строки 4. Цикл сразу же закончится, поскольку нарушится условие его выполнения. После завершения работы цикла условие НОД(а, b) = НОД (m, n) по-прежнему выполняется, но, кроме того, b = 0. Отсюда следует, что а = НОД(m, n).
Следующая страница 
Инвариант цикла
Cкачать материалы урока
