Как работает Евклидово Алгоритм?

Я просто нашел этот алгоритм для вычисления наибольшего общего делителя в своих лекциях:

public static int gcd( int a, int b ) {
    while (b != 0) {
        final int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Итак, r - остаток при делении b на a (получить mod). Затем b присваивается a, а остаток присваивается b, а a возвращается. Я не могу за свою жизнь видеть, как это работает!

И тогда, по-видимому, этот алгоритм не работает для всех случаев, и тогда он должен использоваться:

public static int gcd( int a, int b ) {
    final int gcd;
    if (b != 0) {
        final int q = a / b;
        final int r = a % b; // a == r + q * b AND r == a - q * b.
        gcd = gcd( b, r );
    } else {
        gcd = a;
    }
    return gcd;
}

Я не понимаю причины этого. Обычно я получаю рекурсию и хорошо разбираюсь в Java, но это ускользает от меня. Помогите пожалуйста?

Ответы

Ответ 1

В статье Wikipedia содержится объяснение, но это нелегко найти сразу (также, процедура + доказательство не всегда ответьте на вопрос "почему это работает" ).

В основном это сводится к тому, что для двух целых чисел a, b (при условии a >= b) всегда можно написать a = bq + r, где r < б.

Если d = gcd (a, b), то мы можем написать a = ds и b = dt. Итак, мы имеем ds = qdt + r. Поскольку левая часть делится на d, правая часть также должна делиться на d. А так как qdt делится на d, вывод состоит в том, что r также должен быть делимым на d.

Подводя итог: имеем a = bq + r, где r < b и a, b и r делятся на gcd (a, b).

Так как a >= b > r, мы имеем два случая:

  • Если r = 0, то a = bq, и, следовательно, b делит как b, так и a. Следовательно, gcd (a, b) = b.
  • В противном случае (r > 0) мы можем свести задачу нахождения gcd (a, b) к задаче нахождения gcd (b, r), которая является точно таким же числом (поскольку a, b и r все делятся по d).

Почему это сокращение? Поскольку r < б. Таким образом, мы имеем дело с числами, которые определенно меньше. Это означает, что нам нужно лишь применить это сокращение к конечному числу раз, прежде чем мы достигнем г = 0.

Теперь, r = a% b, который, надеюсь, объяснит ваш код.

Ответ 2

Они эквивалентны. Прежде всего следует отметить, что q во второй программе вообще не используется. Другая разница - это просто итерация против рекурсии.

Что касается того, почему это работает, ссылка на Википедии, связанная выше, хороша. Первая иллюстрация, в частности, эффективна для интуитивной передачи "почему", а анимация ниже иллюстрирует "как".

Ответ 3

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

gdc(first number, second number)
  as long as (second number > 0) {
      int remainder = first % second;
      gcd = try(second as first, remainder as second);
  }
}

Запрет попытки применить это к нецелым, при каких обстоятельствах этот алгоритм терпит неудачу?

(также см. http://en.wikipedia.org/wiki/Euclidean_algorithm для подробной информации)

Ответ 4

Вот интересное сообщение в блоге: Tominology.

Там, где обсуждается много интуиции, стоящей за евклидовым алгоритмом, она реализована в JavaScript, но я считаю, что, если кто-то хочет, не сложно преобразовать код в Java.

Ответ 5

Здесь - очень полезное объяснение, которое я нашел.

Для тех, кто слишком ленив, чтобы открыть его, вот что он говорит:

Рассмотрим пример, когда вам нужно было найти GCD (3084,1424). Предположим, что d является GCD. Это означает, что d | 3084 и d | 1424 (используя символ "|", чтобы сказать "делит" ).

Отсюда следует, что d | (3084-1424). Теперь мы попытаемся уменьшить эти числа, которые делятся на d (в данном случае 3084 и 1024) как можно больше, так что мы достигнем 0 как одно из чисел. Помните, что GCD (a, 0) является a.

Так как d | (3084 - 1424), следует, что d | (3084-2 (1424)) что означает d | 236.
Подсказка: (3084 - 2 * 1424 = 236)

Теперь забудьте о начальных числах, нам просто нужно решить для d, и мы знаем, что d является наибольшим числом, которое делит 236, 1424 и 3084. Таким образом, мы используем меньшие два числа, чтобы продолжить, потому что оно будет сходиться проблема в направлении 0.

d | 1424 и d | 236 следует, что d | (1424-236).
Итак, d | (1424 - 6 (236)) = > d | 8.

Теперь мы знаем, что d - наибольшее число, делящее 8, 236, 1424 и 3084. Взяв меньшие два, мы имеем

d | 236 и d | 8, откуда следует d | (236-8).
Итак, d | (236 - 29 (8)) = > d | 4.

Снова список чисел, делящихся на d, увеличивается и сходится (числа становятся меньше, ближе к 0). В настоящее время d является наибольшим числом, которое делит 4, 8, 236, 1424, 3084.

Выполняя те же действия,

d | 8 и d | 4 следует, что d | (8-4).
Итак, d | (8 - 2 (4)) = > d | 0.

Список чисел, делящихся на d, теперь равен 0, 4, 8, 236, 1484, 3084. GCD (a, 0) всегда a. Итак, как только у вас будет 0 в качестве одного из двух чисел, другим номером будет gcd из оригинала два и все те, которые вошли между ними.

Это именно то, что делает ваш код. Вы можете распознать состояние терминала как GCD (a, 0) = a.

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