E005. Extended Euclidean algorithm

e-maxx algorithm original: C/C++ #algorithm #emaxx #math #number-theory
Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.
Static

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

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

и

,

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

и

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

Algorithmus

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

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

к паре

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

от деления).

Итак, пусть мы нашли Lösung

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

:

и хотим получить Lösung

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

:

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

:

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

и

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

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

и

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

Implementierung

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 значение НОД от чисел

и

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

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

и

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

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

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

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

и

равны

и

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

References

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

анализ [2005]

C# Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
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++ Lösung

zugeordnet/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 Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
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;
    }
}

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

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen
Es gibt noch keine aktiven Stellen.