Wikiszótár

euklideszi algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɛuklidɛsiɒlɡoritmuʃ]

Főnév

euklideszi algoritmus

  1. (matematika, algoritmusok) Módszer két különböző szám legnagyobb közös osztójának megtalálására.
    1. Osszuk el maradékosan a nagyobbik számot a másik számmal.
    2. Ha a maradék 0, akkor a legnagyobb közös osztó éppen a kisebbik szám.
    3. Ha a maradék nullától különböző, akkor a keresett legnagyobb közös osztó megegyezik a maradék és a kisebb szám legnagyobb közös osztójával, ezért megismételhetjük az első lépést erre a két számra.

Euklideszi algoritmus bemutatása

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.


Elmélet

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.


Pszeudokód

Euklideszi(a, b):
    amíg b ≠ 0:
        r = a % b
        a = b
        b = r
    visszatér a

Python implementáció

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Példa
print(gcd(48, 18))  # Kimenet: 6

C++ implementáció

#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;
}

Kiterjesztett Euklideszi algoritmus

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: [ a x + b y = (a, b) ].

Pszeudokód a kiterjesztett verzióhoz

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)

Python implementáció (kiterjesztett változat)

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

Összegzés

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.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=euklideszi_algoritmus&oldid=3479433”