Как использовать алгоритм Евклида для поиска GCF/GCD?

Question

Я создал метод, который позволяет мне найти GCF/GCD двух чисел, и хотя у меня есть рабочий код, я не знаю, как и почему он работает. Я понимаю алгоритм Евклида, но не знаю, как его использует следующий фрагмент.

private int gcd(int a, int b) 
    { 
    if (b == 0) 
    return a; 
    else if(a ==0) 
    return b; 
    else 
    return gcd(b, a % b); 

    } 

Я особенно смущен тем, что он возвращает, потому что почему возвращались два значения? И что делает a% b? Как это использует алгоритм Евклида?

Answer 1

«наибольший общий делитель двух чисел не изменяется, если большее число заменяется его разность с меньшим числом.»

(wikipedia - Euclidean algorithm)

Таким образом, по модулю:
Модульное возвращает остаток от целочисленного между двумя дивизия целых чисел. Целочисленное деление - это деление без дробей или плавающих точек. Обозначим целочисленное деление как m /\ n.

m /\ n = o; 
m % n = p; 
o * n + p = m; 

В качестве примера,

29 /\ 3 = 9; (3 goes - whole - into 29 9 times) 
29 % 3 = 2; (the integer division of 29 into 3 has a remainder of 2) 
9 * 3 + 2 = 29; (9 goes into 29 3 times (and 3 goes into 29 9 times), with a remainder of 2) 

Обратите внимание, что если m меньше n (т.е. m < n), то n переходит в m 0 раз (m /\ n = 0), так что остаток от целочисленного деления будет be m (m % n = m, потому что o * n + p = m и так (0*n) + p = 0 + p = p = m);

Итак, как работает эта функция? давайте попробуем его использовать.

1 - НОД (т, п), м < п
Таким образом, если мы начинаем gcd(m, n) с m, который меньше, чем n, единственное, что происходит на следующем вложенном вызове НОД является то, что порядок изменений аргументов: gcd(n, m % n) = gcd(n, m);

2 - НОД (п, м), м < п
Итак, теперь первый аргумент больше второго.
Согласно алгоритму Евклида, мы хотим сделать что-то большее для двух чисел. Мы хотим заменить его разницей между ним и меньшим числом. Мы могли бы сделать m - n кучу раз. Но то, что делает m % n, является таким же, как вычитание n от m столько раз, сколько возможно до, поэтому это приведет к отрицательному числу. Выполнение вычитания будет выглядеть как (((m - n) - n) - n) - n) и так далее. Но если мы расширим это, получим: m - (n * o). Потому что o * n + p = m, мы видим, что m - (n * o) = p и p = m % n. Таким образом, многократное вычитание меньшего из большего числа такое же, как и для модуля большего размера с меньшим.
На следующем этапе второй аргумент может быть 0 (если n был делителем m). В этом случае функция возвращает n. это верно, потому что n является делителем самого себя, а также, как мы видели, делителем m.
Или второй аргумент может быть меньше n. Это связано с тем, что остаток от целочисленного деления m до n должен быть меньше n - это связано с тем, что если остаток деления был больше n, то n мог бы поместиться в m еще раз, ; это абсурдный результат. Предполагая, что n не равен 0, то второй аргумент (назовем его p) меньше n.
Итак, теперь мы звоним gcd(n, p), где p < n.

3 - НОД (п, р), р < п
Что происходит сейчас? ну, мы точно в том же месте, что и в предыдущем абзаце. Теперь мы просто повторяем этот шаг, т. Е. Будем продолжать называть gcd(a, b), пока меньшее из двух чисел, переданных в gcd(a ,b), не будет делителем большего из двух чисел (это означает, что a % b = 0), и в этом случае вы просто возвращаете меньше из двух чисел.

Answer 2

1) Что делает a% b?
% - модуль или оператор остатка в Java. Оператор% возвращает оставшуюся часть двух чисел. Например, 8% 3 равно 2, потому что 8, деленная на 3, оставляет остаток от 2.

2) Алгоритм Евклида основан на принципе, что наибольший общий делитель двух чисел не изменяется, если большее число заменяется на его разница с меньшим числом. Фактически, ваша функция gcd используется более эффективная версия евклидова алгоритма. Эта версия вместо этого заменяет большее количество двух чисел на оставшуюся часть, когда делится на меньшую из двух (с этой версией алгоритм останавливается при достижении нулевого остатка). Это доказал Габриэль Ламе в 1844 году (https://en.wikipedia.org/wiki/Euclidean_algorithm)

3) Функция gcd не возвращает два значения, это рекурсивная функция. Рекурсивная функция - это функция, которая либо называет себя, либо находится в потенциальном цикле вызовов функций. В случае вашей функции gcd она будет повторяться до тех пор, пока один из двух параметров не станет нулевым, а значение gcd останется параметром останова.
Вы можете узнать больше о рекурсивной функции по этой ссылке.
http://pages.cs.wisc.edu/~calvin/cs110/RECURSION.html

Answer 3

Учитывая, что ваш вопрос содержит несколько компонентов, я обсужу эволюцию классического алгоритма Евклида в рекурсивный метод, который вы представили. Обратите внимание, что методы, представленные здесь, предполагают, что a >= b

Метод ниже, скорее всего, реализует алгоритм, который вы знакомы с, которые неоднократно вычитает b (меньшее число) от a (большее число), до тех пор, пока не больше или равно b. Если a == 0, остатка нет, давая b как GCD. В противном случае значения a и b заменяются, и повторное вычитание продолжается.

public int classic_gcd(int a, int b) { 
    while (true) { 
     while (a >= b) 
      a = a - b; 

     if (a == 0) 
      return b; 

     int c = b; 
     b = a; 
     a = c; 
    } 
} 

Поскольку внутренний цикл в то время как, по существу, вычисляет напоминание о a, деленное на b, он может быть заменен оператором модуля. Это значительно улучшает скорость сходимости алгоритма, заменяя потенциально большое количество вычитаний одной операцией модуля. Рассмотрите возможность поиска GCD 12,288 и 6, что приведет к более чем 2000 вычитанию. Это улучшение показано в модифицированном методе ниже.

public int mod_gcd(int a, int b) { 
    while (true) { 
     int c = a % b; 
     if (c == 0) 
      return b; 

     a = b; 
     b = c; 
    } 
} 

Наконец, модифицированный алгоритм может быть выражен в виде рекурсивного алгоритма, то есть, он вызывает на себя следующим образом:

public int recurse_gcd(int a, int b) { 
    if (b == 0) 
     return a; 
    else 
     return recurse_gcd(b, a % b); 
} 

Этот метод выполняет то же самое, как и раньше. Однако, а не цикл, метод вызывает себя (который, если не проверен, также является бесконечным циклом). Обмен значениями осуществляется путем изменения порядка аргументов, переданных методу.

Помните, что вышеприведенные методы предназначены исключительно для демонстрации и не должны использоваться в производственном коде.