Двоичный алгоритм Евклида вычисления наибольшего общего делителя - 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.
Объяснение кода листинга программы
- Программа начинается с объявления двух переменных типа integer: x и y.
- Затем определяется функция 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.
- Далее определена функция lcm(a, b), которая вычисляет наименьшее общее кратное двух чисел a и b. Она использует функцию gcd(a, b) для вычисления наибольшего общего делителя и затем умножает его на b.
- В основной части программы пользователю предлагается ввести два числа, после чего они вводятся в переменные x и y.
- Затем вызываются функции gcd(x, y) и lcm(x, y), и результаты выводятся на экран.