Как работает евклидов алгоритм? - PullRequest
Новая
       8

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

11 голосов
/ 15 мая 2011

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

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 (получите мод). Затем 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, но это ускользает от меня. Помогите пожалуйста?

Ответы [ 5 ]

25 голосов
/ 15 мая 2011

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

В основном все сводится к тому, что для двух целых чисел 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 Так как a> = b> r, у нас есть два случая:

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

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

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

1 голос
/ 15 мая 2011

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

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

0 голосов
/ 22 февраля 2015

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

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

Рассмотрим пример, когда выдолжен был найти ГКД (3084,1424).Предположим, что d это GCD.Что означает д |3084 и д |1424 (используя символ «|», чтобы сказать «делит»).

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

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

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

d |1424 и д |236 подразумевает, что d |(1424 - 236).Итак, д |(1424-6 (236)) => d |8.

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

d |236 и д |8, что подразумевает d |(236 - 8).Итак, д |(236 - 29 (8)) => d |4.

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

Принимая те же шаги,

d |8 и д |4 подразумевает d |(8-4).Итак, д |(8 - 2 (4)) => d |0.

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

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

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

0 голосов
/ 21 ноября 2014

Вот интересное сообщение в блоге: Томинология .

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

0 голосов
/ 15 мая 2011

учитывая, что '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 для получения подробной информации)

...