E005. Extended Euclidean algorithm

e-maxx algorithm original: C/C++ #algorithm #emaxx #math #number-theory
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
Static

Источник: e-maxx.ru/algo, страница PDF 18.

В то время как "обычный" Euclidean algorithm просто находит наибольший общий делитель двух чисел

и

,

Extended Euclidean algorithm находит помимо НОД также коэффициенты

и

такие, что: Т.е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.

Algoritmo

Внести вычисление этих коэффициентов в Euclidean algorithm несложно, достаточно вывести формулы, по которым

они меняются при переходе от пары

к паре

(знаком процента мы обозначаем взятие остатка

от деления).

Итак, пусть мы нашли Solución

задачи для новой пары

:

и хотим получить Solución

для нашей пары

:

Для этого преобразуем величину

:

Подставим это в приведённое выше выражение с

и

и получим: и, выполняя перегруппировку слагаемых, получаем:

Сравнивая это с исходным выражением над неизвестными

и

, получаем требуемые выражения:

Implementación

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;

} Это рекурсивная функция, которая по-прежнему returns значение НОД от чисел

и

, но помимо этого —

также искомые коэффициенты

и

в виде параметров функции, передающихся по ссылкам.

База рекурсии — случай

. Тогда НОД равен

, и, очевидно, требуемые коэффициенты

и

равны

и

соответственно. В остальных случаях работает обычное Solución, а коэффициенты пересчитываются по вышеописанным формулам. Extended Euclidean algorithm в такой реализации работает корректно даже для отрицательных чисел.

References

● Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Algoritmoы: Построение и

анализ [2005]

C# solución

borrador automático, revisar antes de enviar 
using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    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;
    }
}

C++ solución

coincidente/original 
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;
}

Java solución

borrador automático, revisar antes de enviar 
import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    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;
    }
}

Материал разбит как Algoritmoическая Tarea: изучить постановку, понять асимптотику и реализовать Algoritmo на выбранном языке.

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes
Todavía no hay vacantes activas.