ГДЗ по информатике 9 класс Семакин, Залогова, Русакова § 16. Алгоритм Евклида с ответами

1. Выполните на компьютере программу Evklid (из параграфа). Протестируйте ее на значениях М = 32, N = 24; М = 696, N = 234.

Program Evklid(input, output);

var M, N, Ost: integer;

begin
writeln('Enter M:');
readln(M);
writeln('Enter N:');
readln(N);

while N <> 0 do
begin
Ost := M mod N;
M := N;
N := Ost;
end;

writeln('GCD: ', M);
end.

Результаты тестирования:

М = 32, N = 24:
Enter M:
32
Enter N:
24
GCD: 8

М = 696, N = 234:
Enter M:
696
Enter N:
234
GCD: 6

2. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:
НОД(А, В, С) * НОД(НОД(А, В), С).

Program GCD(input, output);

var A, B, C, GCD1, GCD2: integer;

function gcd(a, b: integer): integer;
var ost: integer;
begin
while b <> 0 do
begin
ost := a mod b;
a := b;
b := ost;
end;
gcd := a;
end;

begin
writeln('Enter A:');
readln(A);
writeln('Enter B:');
readln(B);
writeln('Enter C:');
readln(C);

GCD1 := gcd(A, B);
GCD2 := gcd(GCD1, C);

writeln('GCD: ', GCD2 * GCD1);
end.

3. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:
А * В = НОД(А, В)-НОК(А, В).

Program LCM(input, output);

var A, B, GCD, LCM: integer;

function gcd(a, b: integer): integer;
var ost: integer;
begin
while b <> 0 do
begin
ost := a mod b;
a := b;
b := ost;
end;
gcd := a;
end;

begin
writeln('Enter A:');
readln(A);
writeln('Enter B:');
readln(B);

GCD := gcd(A, B);
LCM := (A * B) div GCD;

writeln('LCM: ', LCM);
end.