Программирование цикла. Алгоритм Евклида

Постановка задачи:
Требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел
НОД
НОД двух натуральных чисел- это
самое большое натуральное число,
на которое они делятся нацело.
НАПРИМЕР: НОД(12,18)=6

Постановка задачи:
Дано: M и N
Найти: НОД(M,N)
НОД
АЛГОРИТМ ЕВКЛИДА:
Если два числа равны,
то ответ любое из них
иначе перейти к 2)
2) Заменить большее число разностью
большего и меньшего из чисел
3) Вернуться к 1)

Блок-схема алгоритма Евклида
Н А Ч А Л О
Ввод M и N
M ≠ N
N=N-M
M=M-N
M > N
нет
да
да
нет
Вывод M
К О Н Е Ц

Структура алгоритма Евклида
Н А Ч А Л О
Ввод M и N
M ≠ N
N=N-M
M=M-N
M > N
нет
да
да
нет
Вывод M
К О Н Е Ц
Цикл-пока
Повторяет выполнение, пока значения M и N не равны друг другу

Структура алгоритма Евклида
Н А Ч А Л О
Ввод M и N
M ≠ N
N=N-M
M=M-N
M > N
нет
да
да
нет
Вывод M
К О Н Е Ц
Вложенное ветвление
Заменяет большее из двух значений на их разность

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Блок-схема алгоритма Евклида
Н А Ч А Л О
Ввод M и N
M ≠ N
N=N-M
M=M-N
M > N
нет
да
да
нет
Вывод M
К О Н Е Ц

Программа на Паскале
Program Evklid;
var m,n:integer;
Begin
writeln(‘Введите m и n’);
readln (m,n);
while m<>n do
begin
If m>n
then m:=m-n
else n:=n-m
end;
write (‘НОД=‘,m);
end.

Отладка и тестирование задачи на ПК:
Выполнить на ПК программу. Протестировать ее на значениях
1) M= 32
N=24
2) M= 696
N=234

Постановка задачи:
Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:
А х В=НОД(А,В) х НОК (А,В)