Hogyan lehet az euklideszi algoritmust C#-ban megcsinálni?
Ezek persze mind C példák voltak, a C# nyelvet én nem ismerem!
Még egy algoritmus, amit kipróbáltam (nem tömör, és nem is szép, és biztos nem is ez az, ami a ,,nagykönyvben'' van, de lehet, hogy élőszóval könnyen megérthető, szóval ezt is leírom):
int eucl_didactic(int a, int b)
{
. . if (b != 0)
. . {
. . . . int r = a % b;
. . . . while (r != 0)
. . . . {
. . . . . . a = b;
. . . . . . b = r;
. . . . . . r = a % b;
. . . . }
. . . . return b;
. . }
. . . . else
. . . . . . return a;
}
A két szám közül az elsőt megpróbáljuk maradékoan elsztani a másodikkal, persze csak akkor, ha a második szám nem nulla, mert ha a második szám épp 0, akkor persze nem oszthatunkk 0-val (maradékosan sem). Ebben az esetben az első szám lesz a megfelelő eredmény:
(12, 0) = 12
(3, 1) = 3
(0, 0) = 0
Ha a második szám nem nulla, akkor nyugodtan ugyanazt csináljuk, mint amit a legeslegelső algiritmusváltozatnál írtam: végrehajthatjuk a maradékos osztást: az elsőt maradékosan osztjuk a másodikkal, kapunk egy maradékot, utána meg jön a ciklus: minden egyes menetben újabb maradékos osztásokat hajtunk végre, rendre ,,új szerepkiosztással'': minden egyes új menet maradékos osztása során az előző maradékos osztás során az osztó szerepét betöltött b fogja betölteni az új osztandó szerepét (,,a régi b lesz az új a'), és az előző osztásnál kapott maradék (r) fogja betölteni új osztó szerepét. Tehát minden egyes osztási menetben a helyére b-t írunk, b helyére pedig az előző menet r maradékát.
A legelső algoritmusnál mutatott futási táblázatoknál látott módon megkeressük a legeslegutolsó nem-nulla maradékot: addig pörgetjük a ciklust, amíg a maradék 0 nem lesz, és ekkor az ,,utolsó b'' változóban épp ugyanazt az érték található, mint ami az utolsó (vagyis 0) maradék előtti maradék volt (vagyis az utolsó nemnulla maradék).
Az utolsó nemnulla maradék pedig épp a kívánt eredmény (a legnagyobb közös osztó), ezt tehát visszaadjuk a hívónak.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!