Python Math: реализовать евклидов алгоритм для вычисления наибольшего общего делителя

Python Math: Упражнение 76 с решением

Напишите программу на Python для реализации евклидова алгоритма для вычисления наибольшего общего делителя (gcd).

Примечание. В математике евклидов алгоритм [a], или алгоритм Евклида, является эффективным методом для вычисления наибольшего общего делителя (GCD) из двух чисел, наибольшего числа, которое делит их оба, не оставляя остаток.

Евклидов алгоритм основан на том принципе, что наибольший общий делитель двух чисел не изменяется, если большее число заменяется его разностью с меньшим числом. Например, 21 - это GCD 252 и 105 (252 = 21 × 12 и 105 = 21 × 5), и то же число 21 также является GCD 105 и 147 = 252 - 105.

Пример решения : -

Код Python:

from math import *
def euclid_algo(x, y, verbose=True):
	if x < y: # We want x >= y
		return euclid_algo(y, x, verbose)
	print()
	while y != 0:
		if verbose: print('%s = %s * %s + %s' % (x, floor(x/y), y, x % y))
		(x, y) = (y, x % y)
	
	if verbose: print('gcd is %s' % x) 
	return x
euclid_algo(150, 304)
euclid_algo(1000, 10)
euclid_algo(150, 9)

Пример вывода:

 304 = 2 * 150 + 4                                                                                             
150 = 37 * 4 + 2                                                                                              
4 = 2 * 2 + 0                                                                                                 
жк 2                                                                                                      
                                                                                                              
1000 = 100 * 10 + 0                                                                                           
жк 10                                                                                                     
                                                                                                              
150 = 16 * 9 + 6                                                                                              
9 = 1 * 6 + 3                                                                                                 
6 = 2 * 3 + 0                                                                                                 
жк 3

Иллюстрированная презентация:

Блок - схема:

Визуализируйте выполнение кода Python:

Следующий инструмент визуализирует, что компьютер делает шаг за шагом при выполнении указанной программы:

Редактор кода Python:

Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Предыдущий: Напишите программу на Python для расчета кластеров с использованием метода иерархической кластеризации.
Далее: Напишите программу на Python для преобразования цвета RGB в цвет HSV.