Az Euklideszi algoritmus az egyik legrégebbi, mégis rendkívül hatékony algoritmus a legnagyobb közös osztó (LNKO, angolul GCD) meghatározására két szám között. Az algoritmus az osztási maradék ismételt alkalmazásán alapul: a két szám legnagyobb közös osztója megegyezik a kisebb szám és az osztási maradék legnagyobb közös osztójával.
Az algoritmus logikája: 1. Vegyünk két számot, (a) és (b), ahol (a b). 2. Osszuk el (a)-t (b)-vel, és határozzuk meg az osztási maradékot ((r)). 3. Az új számok: (a b), (b r). 4. Addig ismételjük, amíg (b = 0). Ekkor (a) a legnagyobb közös osztó.
Példa működésre: - (a = 48), (b = 18): - (48 = 2) maradék (12), - (a = 18), (b = 12), - (18 = 1) maradék (6), - (a = 12), (b = 6), - (12 = 2) maradék (0), - LNKO = 6.
Időkomplexitás: - Az algoritmus hatékonysága (O(((a, b)))), mivel minden iterációban a kisebbik szám legalább felére csökken.
Euklideszi(a, b):
amíg b ≠ 0:
r = a % b
a = b
b = r
visszatér a
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# Példa
print(gcd(48, 18)) # Kimenet: 6
#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
cout << gcd(48, 18) << endl; // Kimenet: 6
return 0;
}
A kiterjesztett változat nemcsak az LNKO-t határozza meg, hanem két egész számot, (x)-et és (y)-t is, amelyek kielégítik az alábbi összefüggést: .
KiterjesztettEuklideszi(a, b):
ha b = 0:
visszatér (a, 1, 0)
(gcd, x1, y1) = KiterjesztettEuklideszi(b, a % b)
x = y1
y = x1 - (a // b) * y1
visszatér (gcd, x, y)
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
gcd, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd, x, y
# Példa
g, x, y = extended_gcd(48, 18)
print(f"GCD: {g}, x: {x}, y: {y}") # Kimenet: GCD: 6, x: -1, y: 3
Az Euklideszi algoritmus és annak kiterjesztett változata alapvető matematikai eszközök, amelyek hatékonyan számolják a legnagyobb közös osztót, illetve annak lineáris kombinációját. Pythonban és C++-ban egyszerűen implementálható, és széles körben használják a számelmélet, kriptográfia és algoritmusok területén.