Най-голям общ делител и най-малко общо кратно

Greatest Common Divisor and Least Common Multiple

Какво е най-голям общ делител?
Какво е най-малко общо кратно?
Разширен алгоритъм на Евклид и приложения

Автор: Соня Милева

Математиката е неизменна част от информатиката независимо дали някои го отричат или не! Следователно логично е да се решават математически задачи в програмирането, което се случва много често по състезания. Най-много такива задачи могат да се срещнат в TopCoder и на руски състезания. Математическите задачи често включват намиране на НОД и НОК (за опростяване на дроби или в задачи свързани с теория на числата) – понякога това директно ни дава отговора, а друг път е само малка, но важна част от голяма заплетена задача.

Най-голям общ делител

?	Ще отбелязваме най-големия общ делител на a и b НОД(a, b) или gcd(a, b)

Най-голям общ делител е най-голямото цяло число което дели две числа без остатък.

Дадени са две числа a и b. Да се намери най-големият им общ делител.

Наивният метод е да пробваме всеки един делител на едното число дали дели и другото. Този алгоритъм ще има сложност O(min(a, b)).

int
 gcdNaive(int
 a,
 int b) {
    for
 (int
 i =
 min(a,
 b);
 i >
=
 1
;
 i-
-) {
        if
 (a %
 i =
=
 0
 &
&
 b %
 i =
=
 0) {
            return
 i;
        }
    }
}

Ако сме малко по-умни и първо намерим делителите на едното число, след което проверим кой е максималният от тях, който дели другото, бихме получили сложност O(sqrt(min(a, b))).

Алгоритъм на Евклид (с изваждане)

Алгоритъмът на Евклид за пресмятане на НОД произлиза от теоремата на Безу: ако имаме две неотрицателни цели числа a и b, които имат НОД d, то съществуват цели числа x и y за които е изпълнено уравнението: ax + by = d. Следователно НОД на две числа не се променя ако заместим по-голямото с разликата между него и по-малкото. Ако повторим тази процедура докато едното число не стане нула, то в този момент другото число е равно на НОД на двете първоначални. Алтернативно можем да спрем още на стъпката в която двете числа са равни - тогава те са равни и на НОД-а си.

Например за числата 84 и 18 имаме: НОД(84, 18) = НОД(84-18, 18) = НОД(66, 18) = НОД(48, 18) = НОД(30, 18) = НОД(12, 18) = НОД(6, 12) = НОД(6, 6) = 6. Този алгоритъм ще има сложност O(max(a, b)), която се достига при НОД(a, 1).

int
 gcdEuclidSubtraction(int
 a,
 int b) {
    while
 (a !
= b) {
        if
 (a < b) {
            swap(a,
 b);
        }
        a -
=
 b;
    }
    return
 a;
}

Алгоритъм на Евклид (с остатъци)

Предишният алгоритъм може да бъде опитимизиран още тъй като при голяма разлика между двете числа ще трябва да се направят много изваждания. Можем вместо да заместваме по-голямото число с разликата, да го заместваме с остатъка при делението на по-голямото на по-малкото. При тази оптимизация е доказано, че никога не се правят повече от 5 * (броя цифри на по-малкото число) стъпки. Този алгоритъм ще има сложност O(log10(max(a, b))) .

int
 gcdEuclidRemainder(int
 a,
 int b) {
    return
 b =
=
 0
 ?
 a :
 gcdEuclidRemainder(b,
 a %
 b);
}

А ето и итеративно решение на последния алгоритъм:

int
 gcdEuclidRemainderIter(int
 a,
 int b) {
    while
 (b !
=
 0) {
        a %
=
 b;
        swap(a,
 b);
    }
    return
 a;
}

НОД на повече от две числа

НОД на повече от две числа можем да намерим като намерим НОД първо на първите две, после на тях и на следващото и т.н. Например за три числа имаме:

gcd({a,
 b,
 c}) =
 gcd(gcd(a,
 b),
 c);

По аналогичен начин можем да разширим алгоритъма за произволен брой числа.

Най-малко общо кратно

?	Ще отбелязваме най-малкото общо кратно на a и b НОК(a, b) или lcm(a, b).

Най-малко общо кратно е най-малкото цяло положително число, което се дели на дадените числа без остатък.

Дадени са две числа a и b. Да се намери най-малкото им общо кратно.

Наивният алгоритъм е с цикъл по отговора, което би значело да генерираме всички числа до a * b и да проверим дали a и b се делят едновременно на някое от тях. Този алгоритъм ще ни даде сложност O(a∙b).

long
 long
 lcmNaive(int
 a,
 int b) {
    for
 (long
 long
 i =
 max(a,
 b);
 i <
=
 (long
 long
)a *
 b;
 i+
+) {
        if
 (i %
 a =
=
 0
 &
&
 i %
 b =
=
 0) {
            return
 i;
        }
    }
}

Ефективен алгоритъм

Ако a и b са взаимно прости (т.е. имат НОД = 1), НОК(a, b) = a * b. Иначе НОК(a, b) < a * b или по-точно НОК(a, b) = a * b / НОД(a, b). Допълнително можем да попроменим израза по следния начин за да намалим размера на междинните стойности: НОК(a, b) = a * (b / НОД(a, b)). Този алгоритъм ще ни даде сложност O(log10(max(a, b))) .

long
 long
 lcm(int
 a,
 int b) {
    return
 (long
 long
)a *
 (b /
 gcdEuclidRemainder(a,
 b));
}

НОК на повече от две числа

Както и за НОД, НОК на повече от две числа можем да намерим като намерим НОК първо на първите две, после на тях и на следващото и т.н. Например за три числа имаме:

lcm({a,
 b,
 c}) =
 lcm(lcm(a,
 b),
 c);

По аналогичен начин можем да разширим алгоритъма за произволен брой числа.

Разширен алгоритъм на Евклид

Задачи за тренировка

Референции

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 22558 пъти.