Matematikai algoritmusok

A Legendre – algoritmus

Ez az algoritmus pozitív egész kitevős hatványokat számol ki, jóval kisebb idő alatt, mint ha a hatványozás eredeti formáját használnánk. Az algoritmus a következőképpen működik: az a a k-adikon elvégzéséhez k-1 darab szorzást kell alkalmaznunk, ha szépen sorjában végezzük el azokat. Viszont minden tényező egyenlő (a), így azokat csoportosíthatjuk (hiszen a szorzás művelete asszociatív). Ha tehát már tudjuk a  a értékét, akkor ezt már a továbbiakban nem kell újra kiszámolni, hanem felhasználhatjuk a következő két tényező esetében. Így már lényegében megvan a * a * a * a értéke, vagyis a következő négy tényezőnél sem kell újra elvégezni a szorzást. Ezt az elgondolást folytatva csökkenthető a szorzások száma, ami hatékony algoritmushoz vezet.

Nézzük a pszeudokódot:

Eljárás legendre_algoritmus:

Er = 1    'Er: eredmény

Be: al, kit    'al: alap; kit: kitevő

Ciklus amíg kit > 0

Ha kit páratlan Akkor

Er = Er * al

kit = kit – 1

Egyébként

al = al * al

kit = kit / 2

Elágazás vége

Ciklus vége

Eljárás vége

Az Euklideszi algoritmus

Ezzel az algoritmussal már kilencedik osztályban találkozhattunk, mikor két szám legnagyobb közös osztóját kellett megkeresni. Ennek meghatározását általában a prímtényezős felbontás segítségével végeztük el, de annak műveletigénye megfelelően nagy számoknál sokszorosa az Euklideszi algoritmusénak.

A kérdés tehát az, hogyan számoljuk ki a, b ismeretében (a ; b)-t ? Feltehető, hogy a > b, hiszen ha egyenlők, nem sok értelme van legnagyobb közös osztót keresni. Osszuk tehát el a-t b-vel maradékosan. Ha a maradék 0, készen vagyunk, (a ; b) = b. Ha nem 0, akkor most a b-t osszuk el az első lépésben kapott maradékkal, ha itt 0 maradékot kapunk, akkor (a ; b) = maradék. Ha itt sem kapunk 0-át, folytassuk tovább az eljárást, az utolsó nem nulla maradék lesz a és b legnagyobb közös osztója.

Nézzük most már a pszeudokódot:

Eljárás euklideszi_algoritmus:

Be: a , b

Ciklus amíg b <>0

maradék = a mod b

a = b

b = maradék

Ciklus vége

Eljárás vége.

A fent leírt algoritmus tehát a legnagyobb közös osztó kiszámítására használatos, de a legkisebb közös többszörös is meghatározható segítségével. Azt az alapvető információt kell ismernünk hozzá, hogy (a ; b ) * [a ; b ] = a * b, azaz a két szám szorzatát elegendő elosztani a már megtalált legnagyobb közös osztóval, és már meg is kaptuk a keresett legkisebb közös többszöröst.

Eratosztenész szitája

A legnagyobb közös osztó meghatározása közben felmerülhet a nagy probléma (még ma is annak számít, korunk hipertechnikája mellett is): hogyan határozhatóak meg a prímszámok (olyan pozitív egészek, amelyeknek pontosan 2 osztójuk van: 1 és önmaguk). Az erre szolgáló egyik eljárást a görögök találták, ezért a fenti elnevezés, de ezt az algoritmust prímszitának is nevezik.

Tehát az eljárás (mintha a füzetben oldanánk meg): először is írjuk fel a számokat 2-től N-ig (az 1-et elhagyhatjuk, hiszen arról tudjuk, hogy nem prím), karikázzuk be a kettest, mert az prím. Húzzuk ki az előbb bekarikázott szám többszöröseit, hiszen azok nem lehetnek prímek, továbbá ha a bekarikázott szám négyzete nem nagyobb, mint az N, akkor karikázzuk be a következő számot, mert az is prím és az előzőhöz hasonlóan járjunk el most is. Ha azonban egy idő után eljutunk addig, hogy az utoljára bekarikázott szám négyzete nagyobb, mint N, akkor a még át nem húzott számok mindegyikét karikázzuk be, mert azok prímek.

Az algoritmus pszeudokódja:

Eljárás eratosztenesz_szitaja

Be: N

Ciklus i = 2-től N-ig    'Itt „írjuk fel a számokat a papírra”, vagyis feltöltünk egy tömböt

M(i) = i

Ciklus vége

Ciklus j = 2-től N-ig    'Itt hagyjuk el a nem prímeket

Ha M[ j ] > 0 Akkor    'Itt „húzzuk ki” a j-vel osztható számokat

Ciklus k = 2 * j-től N-ig Lépésköz j

M(k) = 0

Ciklus vége

Elágazás vége

Ciklus vége

Eljárás vége