Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

2.4. Az euklideszi és a kibővített euklideszi algoritmus

2.4. Az euklideszi és a kibővített euklideszi algoritmus

2.13. Tétel. A legnagyobb közös osztó rekurziós tétele

Tetszőleges és két egész szám esetén fennáll, hogy .

Bizonyítás. Az az -ból ismételt kivonásaival megkapható és így a redukciós tétel (2.12) értelmében az állításunk igaz.

A rekurziós tétel révén készíthető el az euklideszi algoritmus a legnagyobb közös osztó meghatározására. Az algoritmus pszeudokódja:

2.3. Példa. Példa az algoritmusra: ,

2.14. Tétel. Lamé tétele

Ha az euklideszi algoritmusban és valamely -ra, akkor a rekurziós hívások száma kevesebb, mint .

A tételt nem bizonyítjuk

A tétel következménye, hogy ha , akkor a rekurziós hívások száma kevesebb, mint , valamint becslést tudunk adni erre a -ra közvetlenül a -ből. A értékére jól memorizálható becslés az, hogy vehető a tizes számrendszerbeli jegyei ötszörösének. (Valójában megmutatható, hogy itt a kisebb reláció is igaz.) A meggondolás az alábbi:

Bizonyítható, hogy az euklideszi algoritmusnak a legrosszabb bemenő adatai a szomszédos Fibonacci számok. Az euklideszi algoritmus időigénye azon feltételezés mellett, hogy az aritmetikai műveletek konstans ideig tartanak függetlenül a benne szereplő számértékek nagyságától. Ha a számok nagyságát is figyelembe vesszük, akkor az időigény . Az euklideszi algoritmus némi bővítéssel alkalmassá tehető arra, hogy a legnagyobb közös osztó lineáris kombinációként történő előállításában szereplő és együtthatókat is meghatározza. Tekintsük az euklideszi táblát.

A tábla sorában a rekurziós tétel alapján érvényes a összefüggés, ahol továbbá

A és indexű sorok között a kapcsolat:

Kaptunk egy összefüggést az , és az , együtthatók között az egymást követő sorokra, ha fentről lefelé haladunk a táblában.

Haladjunk most lentről fölfelé! Akkor 2.1-ból és kifejezve:

Az utolsó sor esetén viszont , azaz és . Az utolsó sorból indulva így visszafelé sorról-sorra haladva az és értékek kiszámíthatók. Végül az és is kiadódik. Ez a módosítás vezet az euklideszi algoritmus kibővítésére, melynek pszeudokódját alább közöljük.

2.4. Példa. Példa kibővített euklideszi algoritmusra

Az algoritmus eredményeképpen és adódott. Ellenőrzésképpen

ami valóban megfelel az elvárásoknak.