3. fejezet - Algoritmusokról általában

3.1. Euklideszi algoritmus

Az algoritmus szóról sokaknak elsőre az euklideszi algoritmus jut az eszébe, ezért kezdjünk ezzel!

Euklideszi algoritmus:

Adott két pozitív egész szám: m és n. 
Keresendő legnagyobb közös osztójuk, vagyis az a legnagyobb pozitív egész, amelyik mindkettőnek az osztója. 

Az algoritmus a következő lépésekkel írható le:

E1. Osszuk el m-et n-nel, a maradék legyen r.

E2. Ha r=0, akkor az algoritmus véget ért, az eredmény n.

E3. Legyen m ← n és n ← r, és folytassuk az algoritmust az E1 lépéssel.

Kövessük az algoritmus futását a 119 és 544 számokra, azaz legyen m = 119 és n = 544!

3.1. táblázat - Euklideszi algoritmus lépései az m=119 és n=544 számokra

LépésÁllapot (végrehajtás előtt)Állapot (végrehajtás után)
E1m=119, n=544, r=rm=119, n=544, r=119
E2m=119, n=544, r=119m=119, n=544, r=119
E3m=119, n=544, r=119m=544, n=119, r=119
E1m=544, n=119, r=119m=544, n=119, r=68
E2m=544, n=119, r=68m=544, n=119, r=68
E3m=544, n=119, r=68m=119, n=68, r=68
E1m=119, n=68, r=68m=119, n=68, r=51
E2m=119, n=68, r=51m=119, n=68, r=51
E3m=119, n=68, r=51m=68, n=51, r=51
E1m=68, n=51, r=51m=68, n=51, r=17
E2m=68, n=51, r=17m=68, n=51, r=17
E3m=68, n=51, r=17m=51, n=17, r=17
E1m=51, n=17, r=17m=51, n=17, r=0
E2m=51, n=17, r=0m=51, n=17, r=0

Az n utolsó értéke 17 volt, ennek megfelelően a 119 és az 544 számok legnagyobb közös osztója 17. Az euklidészi algoritmust természetesen nem csak lépések listájaként, hanem folyamatábrával is megadhatjuk.

3.1. ábra - Az Euklideszi algoritmus folyamatábrája

Az Euklideszi algoritmus folyamatábrája