1.
Буратино учится искать НОД. Моделирование
Алгоритм Евклида — это способ нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Оригинальная версия алгоритма, когда НОД находится вычитанием, была открыта Евклидом (III в. до н. э).
В настоящее время Алгоритм Евклида "вычитанием" используется как метод или часть вычислительных алгоритмов.
Сформулировать Алгоритм Евклида можно так:
Из Большего вычти Меньшее и запиши вместо Большего
Продолжай, пока не получишь равенство.
Для чисел A и B, на языке программирования, это можно записать так:
while (A!=B):
if A>B :
A=A-B
else :
B=B-A
В современной математике понятие НОД (greatest common divisor) используется для большого круга объектов (главное, чтобы из можно было сравнивать и вычитать).
Так, для целых чисел НОД(A,0)=A и НОД(A,B)=НОД(|A|,|B|)
На уроках математики Мальвина научила Буратино находить наибольший общий делитель двух натуральных чисел с помощью простого Алгоритма Евклида.
В качестве проверочного задания Мальвина попросила Буратино найти НОД для чисел A и В, с записью полного решения.
Полная запись решения для числе 24 и 32 имеет следующий вид:
24 32
24 8
16 8
8 8
Помогите Буратино выполнить задание Мальвины.
Входные данные : Числа A, B (числа записаны в две строки, каждое не более 1000)
Выходные данные: Полная запись решения (набор строк, в каждой результат очередного действия, смотри пример)
| входные данные |
выходные данные |
127
127 |
127 127 |
45
21 |
45 21
24 21
3 21
3 18
3 15
3 12
3 9
3 6
3 3 |
Напишите программу
Auto