Программирование
+2Простая программа питон
Ввести с клавиатуры два натуральных числа и сравнить количество шагов цикла для вычисления их НОД с помощью обычного и модифицированного алгоритмов Евклида.
По дате
По рейтингу
1234567891011121314
x, y = map(int, input().split())
a, b, c = x, y, 0
while a:
if b > a: a, b = b, a
a -= b
c += 1
print('Обычный, итераций:', c, ' НОД:', b)
a, b, c = x, y, 0
while b:
a, b = b, a % b
c += 1
print('Модифицированный, итераций:', c, ' НОД:', a) Для модифицированного min / max не нужны. А для простого можно обойтись перестановкой уменьшаемого и вычитаемого.
Да элементарно:
123456789101112131415161718
a, b = map(int, input().split())
cm = cc = 0
x, y = max(a, b), min(a, b)
while y:
m = x % y
x, y = max(m, y), min(m, y)
cm += 1
gm = x
x, y = max(a, b), min(a, b)
while y:
m = x - y
x, y = max(m, y), min(m, y)
cc += 1
print(f"НОД мод.: {gm}, обычн.: {x}")
print(f"Шагов мод.: {cm}, обычн.: {cc}")
Для двух соседних чисел Фиббоначчи число шагов там и там будет почти одинаковым. А для произвольных наугад взятых обычно отличается довольно сильно.
Первый цикл - модифицированный алгоритм (делениями), второй - обычный (вычитаниями).