Доказательство. while (x>0)and(y>0) do

Базис. При n = 0 и n = 1 проверяем простой подстановкой.

Предположение. Пусть при n ≥ 0 формула верна.

Вывод. При n + 1 получаем:

учитывая, что

.

_________________________________________

Число называют золотым сечением.

__________________________________________

Алгоритм Евклида, вычисляющий наиболь­ший общий делитель НОД(a, b) двух целых чисел a ≥ 0, b ≥ 0, основан на инвариантных соотноше­ниях:

1) НОД(a, 0) = a;

2) НОД(a, b) = НОД(b, a);

3) НОД(a, b) = НОД(a mod b, b), a ≥ b > 0.

__________________________________________

Докажем третье соотношение.

Операция r = a mod b эквивалентна много­кратному вычитанию b из a до тех пор, пока не будет выполняться 0 ≤ r < b. Поэтому доста­точно доказать, что

НОД(a, b) = НОД(a – b, b), a ≥ b > 0.

Пусть верно противоположное утверждение, а именно:

НОД(a, b) = d, НОД(a – b, b) = c, причем c ≠ d.

Но тогда , при этом , а также – оба целые, в то время как может быть целым лишь в случае, если c = d. Это проти­воречие и доказывает третье соотношение.

__________________________________________

Последовательность пар { x_i, y_i } такова, что НОД(x_i, y_i) = НОД(a, b), max(x_i, y_i) > max(x_{i + 1}, y_{i + 1})

_________________________________________

x:=a; y:=b;

while (x>0)and(y>0) do

if x>=y then x:=x mod y

else y:=y mod x;

if x>0 then nod:=x

else nod:=y

_________________________________________

Трудоемкость программы определяется чис­лами a и b. Наихудший случай будет, если при

f_k ≥ max(a, b) > f_{k – 1},

где f_k, f_{k – 1} – числа последовательности Фибо­наччи, выполняется условие

max(a, b) = f_k , min(a, b) = f_{k – 1} .

Тогда k – количество выполнений цикла. Пренебрегая вторым слагаемым в формуле

и логарифмируя левую и правую части, получим:

, ,

Т.е. трудоемкость алгоритма Евклида имеет порядок O (log max(a, b)).

__________________________________________