Объясните пожалуйста, почему не работает программа поиска НОД двух числе по алгоритму Евклида.

Question

Алгоритм на русском. Если а=b, то НОД = а или b. Если это не так, то выбираем из чисел наибольшее и вычитаем из него наименьшее. Получившееся значение присваиваем числу, которое было наибольшим. (Пример a=5, b=3, то a=5-3=2) Повторяем алгоритм пока a не станет равным b.

program Evklid;

var a, b: integer;

begin

writeln('Введите a и b');

readln(a);

readln(b);

m1: if a=b then writeln(a)

else;

if a>b then a:=a-b;

else b:=b-a;

goto m1;

writeln('НОД чисел',a,'и',b=a);

end.

program Evklid;

var a, b: integer;

begin

writeln('Введите a и b');

readln(a);

readln(b);

m1: if a=b then writeln(a)

else;

if a>b then a:=a-b;

else b:=b-a;

goto m1;

writeln('НОД чисел',a,'и',b=a);

end.

Ирина Кох(Волкова) · Accepted Answer

Во-первых, алгоритм Евклида, насколько я помню, ориентируется не на вычитание, а на деление нацело. Иначе для того, чтобы выяснить, что НОД (2000002, 2) = 2, потребуется два миллиона вычитаний.

Во-вторых, все эти goto, если их использовать неразумно, приводят к зацикливаниям, как в данном случае.

Так что я бы написал этот алгоритм немного по-другому:

PROGRAM Evklid;

VAR
a, b, c: integer;

BEGIN

WriteLn('Введите a и b');
ReadLn(a);
ReadLn(b);

c := a MOD b;

WHILE (c <> 0) DO
BEGIN
a := b;
b := c;
c := a MOD b;
END;

WriteLn('НОД = ', b);

END.

d.alekcey · Answer

Потому что лишняя точка я запятой.