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

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

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

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

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

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

Код Python:

   from math import * def euclid_algo (x, y, verbose = True): if 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) если подробный: print (' gcd is% s '% x)  return xeuclid_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:

Оцените статью
nanomode.ru
Добавить комментарий