Как использовать алгоритм Евклида, чтобы найти 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);

  }

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

Answer 1

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

(википедия - евклидов алгоритм)

Итак, по модулю:
По модулю возвращается остаток целочисленного деления между двумя целыми числами. Целочисленное деление - это деление без дробей или с плавающей точкой. Давайте обозначим целочисленное деление как 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), поэтому остаток от целочисленного деления будет m (m % n = m, так как o * n + p = m так что (0*n) + p = 0 + p = p = m);

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

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

2 - gcd (n, m), m
Хорошо, теперь первый аргумент больше второго.
Согласно алгоритму Евклида, мы хотим сделать что-то для большего из двух чисел. Мы хотим заменить его на разницу между ним и меньшим числом. Мы могли бы сделать 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(n, p), p
Что происходит сейчас? ну, мы точно в том же месте, что и в предыдущем абзаце. Теперь мы просто повторим этот шаг, то есть продолжим gcd(a, b)до тех пор, пока меньшее из двух чисел, которые передаются в gcd(a ,b) является делителем большего из двух чисел, (что означает, что a % b = 0) в этом случае вы просто возвращаете меньшее из двух чисел.

Answer 2

Учитывая, что ваш вопрос имеет несколько компонентов, я буду обсуждать эволюцию классического алгоритма Евклида в рекурсивный метод, который вы представили. Обратите внимание, что представленные здесь методы предполагают, что 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;
    }
}

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

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);
}

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

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

Answer 3

1) Что делает% 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