Question

Даны 2 натуральных числа A, B. Определить их наибольший общий делитель​

Answer 1

Ответ:

var

 a, b, c: integer;

begin

 Writeln('Введите два числа');

 Read(a, b);

 repeat

   if a > b then

     a := a mod b

   else b := b mod a

 until (a = 0) or (b = 0);

 c := a + b;

 Writeln('Наибольший общий делитель: ', c);

end.

Answer 2

Для определения наибольшего общего делителя (НОД) двух натуральных чисел A и B можно использовать алгоритм Евклида. Этот алгоритм основан на том, что НОД двух чисел не изменится, если из большего числа вычесть меньшее, и так продолжать до тех пор, пока числа не станут равными.

Вот псевдокод для алгоритма Евклида:

lessCopy code
function euclidean_algorithm(A, B):
    while B ≠ 0:
        remainder = A % B
        A = B
        B = remainder
    return A

Применяем этот алгоритм для нахождения НОД чисел A и B:

1. Пусть A = 36, B = 48.
2. Начинаем цикл:
   • Первая итерация: remainder = 36 % 48 = 36, A = 48, B = 36.
   • Вторая итерация: remainder = 48 % 36 = 12, A = 36, B = 12.
   • Третья итерация: remainder = 36 % 12 = 0, A = 12, B = 0.
3. Цикл завершен, и НОД(36, 48) = 12.

Таким образом, наибольший общий делитель чисел 36 и 48 равен 12.