Модифицированный алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на остаток от деления большего на меньшее до тех пор, пока остаток не станет равно нулю; тогда второе число и есть НОД. Напишите программу, которая реализует этот алгоритм.
Входные данные:
Входная строка содержит два числа, разделённые пробелом – a и b .
Выходные данные:
Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем – количество шагов цикла, которые были выполнены.
Примеры:
Входные данные:
21 14
Выходные данные:
7 3
var
i,j,k,n:integer;
a,b,c:array[,] of integer;
begin
Write('Число строк (столбцов) матрицы: '); Read(n);
SetLength(a,n,n);
SetLength(b,n,n);
SetLength(c,n,n);
Randomize;
Writeln('Матрица A');
for i:=0 to n-1 do begin
for j:=0 to n-1 do begin
a[i,j]:=Random(90)+10;
Write(a[i,j]:3)
end;
Writeln
end;
Writeln('Матрица B');
for i:=0 to n-1 do begin
for j:=0 to n-1 do begin
b[i,j]:=Random(90)+10;
Write(b[i,j]:3)
end;
Writeln
end;
// умножение и вывод
Writeln('Матрица C');
for i:=0 to n-1 do begin
for j:=0 to n-1 do begin
c[i,j]:=0;
for k:=0 to n-1 do c[i,j]:=c[i,j]+a[i,k]*b[k,j];
Write(c[i,j]:6)
end;
Writeln
end;
end.
Тестовое решение
Число строк (столбцов) матрицы: 5
Матрица A
25 81 17 87 40
36 79 25 98 66
90 64 73 30 54
75 12 92 48 84
94 91 71 96 94
Матрица B
38 96 54 10 24
66 47 13 15 81
87 33 35 11 19
48 20 16 40 14
34 94 91 97 64
Матрица C
13311 12268 8030 9012 11262
15705 16158 11420 12142 13334
17271 19733 13641 9101 12607
16806 19656 15838 12010 10568
23559 26400 18834 16044 18336