Задание 3 - часть 5
При r>0 этот процесс можно продолжить. Имеем: b > r > r1 > r2 > r3 >, ..., но так как b, r, r1, r2, r3 - неотрицательные целые числа, то найдется n такое, что rn = 0. В соответствии с высказанным утверждением
НОД(a, b) = НОД(b, r) = НОД(r1, r) = ... = НОД(rn-1, 0) = rn-1.
Практически это выглядит так. Надо найти НОД чисел 888 и 351.
Большим из них является 888, a = 888, b = 351.
Находим остаток от деления a на b: 888 mod 351 = 186, r = 186;
заменим a на b и b на остаток r, получим: a = 351, b = 186;
снова находим остаток от деления a на b: 351 mod 186 = 165, r = 165;
заменим a на b и b на остаток r, получим: a = 186, b = 165;
находим остаток от деления a на b: 186 mod 165 = 21, r = 21;
заменим a на b и b на остаток r, получим: a = 165, b = 21;
находим остаток от деления a на b; 165 mod 21 = 18, r = 18;
заменим a на b и b на остаток r, получим: a = 21, b = 18;
находим остаток от деления a на b; 21 mod 18 = 3, r = 3;
заменим a на b и b на остаток r, получим: a = 18, b = 3;
находим остаток от деления a на b: 18 mod 3 = 0, r = 0;
заменим a на b и b на остаток r, получим: a = 3, b = 0.
Как только b стало равным нулю, цикл заканчивается, выдается значение a, которое и является наибольшим общим делителем, НОД(888, 351) = a = 3.
Этот процесс можно записать в виде следующей цепочки, которая в общем виде была записана выше:
НОД(888, 351) = НОД(351, 186) = НОД(186, 165) =
= НОД(165, 21) = НОД(21, 18) = НОД(18, 3) = НОД(3, 0) = 3.
Замечание. Совсем не обязательно выбирать большее из двух чисел. Если число a окажется меньшим, тогда при первом шаге цикла произойдет перестановка чисел a и b.
Например, a = 351, b = 888. Находится остаток от деления a на b:
Понятно даже без глубокого анализа, что этот алгоритм значительно быстрее приводит нас к результату и выполняется без ненужных операций, т. е. не вынуждает компьютер работать впустую.
Программа
Program
Problem2c; { 2 - способ. Алгоритм Евклида }
uses WinCrt;
var
a, b, r, a1, b1 : integer;
begin
write('Введите первое число '); readln(a);
write('Введите второе, не равное нулю, число ');
readln(b);
a1 := a; b1 := b;
repeat
r := a mod b;
a := b; b := r
until b = 0;
writeln('НОД чисел ', a1, ' и ', b1, ' равен ', a)
end.