Двоичный алгоритм Евклида вычисления наибольшего общего делителя - Pascal ABC

Узнай цену своей работы

Формулировка задачи:

Напишите программу для стандартного и двоичного алгоритмов Евклида вычисления наибольшего общего делителя.

Решение задачи: «Двоичный алгоритм Евклида вычисления наибольшего общего делителя»

textual
Листинг программы
program euclid;
var 
  x, y : integer;
 
function gcd(a, b : integer) : integer;
begin
  while(true) do begin
    if(a = 0) then break;
    if(b = 0) then break;
    if(a > b) then a := a mod b else b := b mod a;
  end;
  gcd := a + b;
end;
 
function lcm(a, b : integer) : integer;
begin
  lcm := (a div gcd(a, b)) * b;
end;
 
begin
  write('Введите два числа: ');
  readln(x, y);
  writeln('НОД: ', gcd(x, y),', НОК: ', lcm(x, y));
end.

Объяснение кода листинга программы

  1. Программа начинается с объявления двух переменных типа integer: x и y.
  2. Затем определяется функция gcd(a, b), которая реализует двоичный алгоритм Евклида для вычисления наибольшего общего делителя двух чисел a и b. В цикле while выполняются следующие действия:
    • Если a равно 0, то цикл прерывается, так как наибольший общий делитель равен b.
    • Если b равно 0, то цикл прерывается, так как наибольший общий делитель равен a.
    • Если a больше b, то a делится на b и результат сравнивается с b. Если он равен b, то a заменяется на a mod b, иначе b заменяется на b mod a.
    • Когда a равно 0 или b равно 0, цикл прерывается и наибольший общий делитель равен a + b.
  3. Далее определена функция lcm(a, b), которая вычисляет наименьшее общее кратное двух чисел a и b. Она использует функцию gcd(a, b) для вычисления наибольшего общего делителя и затем умножает его на b.
  4. В основной части программы пользователю предлагается ввести два числа, после чего они вводятся в переменные x и y.
  5. Затем вызываются функции gcd(x, y) и lcm(x, y), и результаты выводятся на экран.

Оцени полезность:

6   голосов , оценка 3.333 из 5
Похожие ответы