ИЗВЕСТНЫЕ АЛГОРИТМЫ
Алгоритм Эвклида
(нахождение наибольшего общего делителя)
Описание алгоритма нахождения НОД вычитанием
1. Из большего числа вычесть меньшее.
Найти НОД для 30 и 18.
30-18 = 12
18-12 = 6
12-6 = 6
6-6 = 0 Конец: НОД равен уменьшаемому или вычитаемому.
НОД (30, 18) = 6
Программа на языке Python
a = int(input(‘Введите первое число: ’))
b = int(input(‘Введите второе число: ’))
while a != b:
if a > b:
a = a - b
else:
b = b - a
print ('NOD =', a)
Этот алгоритм для нахождения НОД двух чисел не самый оптимальный. Например, для a = 1000 000 и b = 2 этот алгоритм будет выполняться 500 000 раз.