добавлено: 10 Jun 2008 17:58 Расширенный алгоритм ЕвклидаВ то время как "обычный" алгоритм Евклида просто находит наибольший общий делитель двух чисел и , расширенный алгоритм Евклида находит помимо НОД также коэффициенты и такие, что: Т.е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа. АлгоритмВнести вычисление этих коэффициентов в алгоритм Евклида несложно, достаточно вывести формулы, по которым они меняются при переходе от пары к паре (знаком процента мы обозначаем взятие остатка от деления). Итак, пусть мы нашли решение задачи для новой пары : и хотим получить решение для нашей пары : Для этого преобразуем величину : Подставим это в приведённое выше выражение с и и получим: и, выполняя перегруппировку слагаемых, получаем: Сравнивая это с исходным выражением над неизвестными и , получаем требуемые выражения: Реализацияint gcd (int a, int b, int & x, int & y) { if (a == 0) { x = 0; y = 1; return b; } int x1, y1; int d = gcd (b%a, a, x1, y1); x = y1 - (b / a) * x1; y = x1; return d; } Это рекурсивная функция, которая по-прежнему возвращает значение НОД от чисел и , но помимо этого — также искомые коэффициенты и в виде параметров функции, передающихся по ссылкам. База рекурсии — случай . Тогда НОД равен , и, очевидно, требуемые коэффициенты и равны и соответственно. В остальных случаях работает обычное решение, а коэффициенты пересчитываются по вышеописанным формулам. Расширенный алгоритм Евклида в такой реализации работает корректно даже для отрицательных чисел. Литература
|