Величайшая функция общего деноминатора не имеет смысла

Question

Я нашел функцию, которая работает, но я не понимаю, почему она работает. Я думаю, что он должен вывести 8, но вместо этого он дает мне правильный ответ 4. Кстати, Python.

def gcd (a, b):
    while(b != 0):
        t = b
        a = b
        b = t % b

return a

Опять же, когда a = 8 и b = 20, он правильно выплевывает из 4, но когда я печатаю (8% 20), он выплевывает 8. так чего мне не хватает?

Answer 1

Здесь вы указываете Евклидов метод [wiki] . В вашем коде есть опечатка, это должно быть:

def gcd (a, b):
    while(b != 0):
        <b>t = a</b>
        a = b
        b = t % b
    return a

Обратите внимание, что это " swaps " a и b в каждой итерации. Действительно, если вы позвоните gcd(8, 10), чем до первых l oop a = 8 и b = 20.

Затем после первой итерации a = 20 и b = 8 % 20, поэтому после первой итерации a = 20 и b = 8. В следующем раунде мы вычисляем a = 8 и b = 20 % 8, это равно b = 4. Тогда, наконец, в последнем раунде будут установлены a = 4 и b = 8 % 4, поэтому b = 0, и мы можем остановиться.

Как указано в статье в Википедии, он работает на основе того факта, что:

Евклидов алгоритм основан на том принципе, что наибольший общий делитель двух чисел не изменяется, если большее число заменяется его разностью с меньшим числом .

Другими словами, это означает, что если a , то gcd (a, b) = gcd (a, b - a) . Мы можем продолжать вычитать a из b , пока не достигнем значения между 0 и b , следовательно, gcd (a, b ) = gcd (a, b mod a) . Поскольку мы знаем, что a mod b находится между 0 (включительно) и b (эксклюзивно), мы можем поменять местами два числа чтобы убедиться, что самый большой из двух снова позиционируется первым. Мы можем продолжать с этим, пока не достигнем нуля для самого маленького.