Доказательство правильности программ | Алгоритм Евклида (11_68_pol) (68 часов в уч. год)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращённый курс, по 2 часа в неделю)


Урок 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качать материалы урока







Наверх