Написать программу нахождения наибольшего общего делителя (НОД) двух неотрицательных чисел

Лабораторная работа №6.

Тема: «Разработка, отладка и испытание циклических алгоритмов и программ с известным числом повторений с внутренними ветвлениями».

Цель работы: составление программ на языке Pascal с использованием цикла с постусловием repeat-until.

Программные средства: система программирования ABC Pascal.

ЗАДАНИЕ №1.

Написать программу нахождения наибольшего общего делителя (НОД) двух неотрицательных чисел.

Решение:

1. Воспользуемся алгоритмом Евклида

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.

Пусть Х и У одновременно не равные нулю целые неотрицательные числа и пусть . Если У=0, то НОД (Х,У)=Х, а если , то для чисел Х,У и ч, где ч – остаток от деления Х на У, выполнится равенство НОД (Х,У)=НОД(У, ч).

Например, пусть Х=48, а У=18

НОД (48, 18)=НОД (18,12)=НОД (12,6)=НОД(6,0)=6

1. Составим программу на языке Pascal, используя все описанное в пункте 1 и воспользуемся оператором цикла с постусловием.

Program example;

Var

x, y: integer;

begin

writeln (‘Введите два числа’);

readln (x, y);

repeat

if x>y

then x:=x mod y

else y:=y mod x;

until (x=0) or (y=0);

writeln (‘НОД=’,x+y);

readln

end.