21.1. Ещё пример задания

Ниже записан алгоритм. После выполнения алгоритма было напечатано 3 числа. Первые два напечатанных числа – это числа 9 и 81. Какое наибольшее число может быть напечатано третьим?

var x, y, z: integer;

r, a, b: integer;

begin

readln(x, у);

if у x then begin

z:= x; x:= у; у:= z;

end;

a:= x; b:= y;

while b 0 do begin

r:= a mod b;

a:= b;

b:= r;

end;

writeln(a);

writeln(x);

write(у);

end.

Решение:

1. сложность этой задачи состоит в том, чтобы разобраться в алгоритме

2. сначала вводятся два числа и переставляются так, чтобы в переменной x было наибольшее число, а в переменной y – наименьшее из двух:

if у x then begin

z:= x; x:= у; у:= z;

end;

1. затем исходные значения копируются в переменные a и b и с ними выполняется следующий алгоритм

while b 0 do begin

r:= a mod b;

a:= b;

b:= r;

end;

его суть сводится к тому, что меньшее из двух чисел, a и b, каждый раз заменяется на остаток от деления большего на меньшее до тех пор, пока этот остаток не станет равен нулю;

1. делаем вывод, что это классический Алгоритм Евклида, который служит для вычисления наибольшего общего делителя (НОД) двух чисел; это делитель в результате оказывается в переменной a

2. смотрим, что выводится на экран: сначала значение переменной a (наибольший общий делитель исходных чисел, НОД(x,y)), затем значение x (большее из исходных чисел) и значение y (меньшее из исходных чисел)

3. по условию первое число – 9, второе – 81, поэтому третье число должно быть меньше, чем 81, и НОД(81,y) = 9

4. наибольшее число, которое меньше 81 и делится на 9, равно 72 (обратите внимание, что исходные числа не могут быть равны, потому что в этом случае их НОД был бы равен 81)

5. ответ: 72