Евклидова алгоритм (вычитание) в питоне

Question

В «Великих математических проблемах - Видение бесконечности», стр. 18 Иан Стюарт ссылался на предложение Евклида 2, Книга VII элемента, которая является очень элементарным методом нахождения Величайшего общего делителя. Я цитирую: «Он работает путем многократного вычитания меньшего числа из большего, затем применяя аналогичный процесс к полученному остатку и меньшему числу и продолжая, пока не останется никакого остатка». Например, с 630 и 135. 135 повторяется «вычитается» с 630 (495, 360, 225) и, наконец, получается 90, что меньше 135. Таким образом, числа инвертируются и 90 многократно вычитаются из 135, чтобы, наконец, 45 Затем 45 вычитают из 90 и, наконец, получают 0, получая 45 gcd. Это иногда называют евклидовым алгоритмом поиска gcd.

Чтобы научить новичка (ребенок 10 лет), мне нужно написать код в python. Не должно быть никакого определения функции, ни он не должен использовать какую-либо другую математическую операцию, кроме вычитания. Я хочу использовать if/while/else/elif/continue/break. Должно быть предусмотрено, что если заданы три числа (или больше), вся программа должна быть повторена, чтобы определить меньшую. Ранняя цепочка на gcd не смотрит алгоритм с этой точки зрения.

Answer 1

Типичным быстрое решение для алгоритма GCD будет какая-то итерационный вариант, как это:

def gcd(x, y): 
    while y != 0: 
     (x, y) = (y, x % y) 

    return x 

В самом деле, в Python вы бы просто использовать непосредственно функцию НОД, представленную модулем дробей.

И если вы хотите такую ​​функции, чтобы иметь дело с несколькими значениями вы бы просто использовать уменьшить:

reduce(gcd,your_array) 

Теперь, кажется, что вы хотите ограничить себя использовать только петли + вычитания так один из возможных решений для решения с й, у положительных числа будут такие:

def gcd_unopt(x, y): 
    print x,y 

    while x!=y: 
     while x>y: 
      x -= y 
      print x,y 
     while y>x: 
      y -= x 
      print x,y 

    return x 

print reduce(gcd_unopt,[630,135]) 

Не уверен, почему вы хотите, чтобы избежать использования функций, НОДОМ является функцией по определению, даже так, что это просто, чтобы избавиться от декларации функции и использовать параметры как глобальные переменные, например:

x = 630 
y = 135 

print x,y 

while x!=y: 
    while x>y: 
     x -= y 
     print x,y 
    while y>x: 
     y -= x 
     print x,y