Задача 76209
|
|
 |
Условие
Даны два натуральных числа a и b, не равные нулю
одновременно. Вычислить НОД(a,b) — наибольший общий
делитель а и b.
Решение
Вариант 1.
if a > b then begin
| k := a;
end else begin
| k := b;
end;
{k = max (a,b)}
{инвариант: никакое число, большее k, не является
общим делителем}
while not ((a mod k = 0) and (b mod k = 0)) do begin
| k := k - 1;
end;
{k - общий делитель, большие - нет}
Вариант 2 (алгоритм Евклида).
Будем считать, что НОД(0,0)=0. Тогда НОД(a,b) =
НОД(a-b,b) = НОД(a,b-a); НОД(a,0) =
НОД(0,a) = a для всех
a,b≥0.
m := a; n := b;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n;
| end else begin
| | n := n - m;
| end;
end;
{m = 0 или n = 0}
if m = 0 then begin
| k := n;
end else begin {n = 0}
| k := m;
end;
