Hogyan lehet az euklideszi algoritmust C#-ban megcsinálni?

Ugyanazzal a módszerrel, mint minden más nyelv esetén.

1) fogod az algoritmus pszeudó leírását

2) fogod az adott nyelv szintaxisát

3) átírod 1)-et 2) alapján

Hol akadtál el?

És most mennyibe telik felcserélni a kettő számot? XD

LOL

ha fordítva nem jó cseréltesd vissza...

Gondolkodj egy kicsit.

(Opp, lassú voltam)

De ez a csere úgy látom magából az algoritmusból következik.

A következetesen megírt eukideszi algoritmus ,,magától'', ,,sajét logikájából adódóan'' ezt az esetet is jól kezeli, tehát nem szabadna 0-t adnia. Úgy direkt külön nem kell a megcserélést mint valami külön ,,kivételvizsgálatot'' ,,hozzátenni'' a programhoz. Most kipróbáltam a dolgot C-ben:

int eucl(int a, int b)

{

. . . int r;

. . . r = a % b;

. . . while (r != 0)

. . . {

. . . . . . a = b;

. . . . . . b = r;

. . . . . . r = a % b;

. . . }

. . . return b;

}

Ez a kód azt fejezi ki:

Elosztjuk maradékosan a-t a b-vel. Ha a maradék (r) nem nulla,

akkor újra végrehajtjuk a maradékos osztás olyan szereposztással, hogy immár az eredetileg osztóként szereplő b-t osztjuk most az előbb kapott maradékként kapott r-rel. (Tehát lényegében a szerepcsere: a helyébe b, és b helyébe r). Mindezt addig csináljuk, amíg a maradék 0 nem lesz. Az eredmény pedig az utolsó nemnulla maradék. Ezt lényegében úgy kapjuk meg, hogy addig csináljuk, amíg a maradék 0 nem lesz, és az ekkor aktuális osztó (b) az ,,előző menet'' során épp a maradék (r) szerepét töltötte be, tehát ez az utolsó nemnulla maradék.

Pl eucl (6, 4) hívása esetén:

a | b | r

6 | 4 | 2

4 | 2 | 0

Látjuk, hogy itt a 2 az utolsó nem-nulla maradék, amit akár a táblázat utolsó előtti sorából is kiolvashatnánk, de ezt akár úgy is kiolvashatnánk, hogy lemegyünk a táblázat utolsó soráig (ahol a maradék 0), és ott kiolvassuk b értékét, ami ,,ugyanaz'' a 2, mintha a táblázat utolsó előtti sorából olvastuk volna ki az r értékét.

No akkor most nézzük meg, mi van, ha megpróbáljuk ,,becsapni'' az algoritmust, és olyan esetet adunk neki amit Te is írsz, vagyis hogy most legyen a < b, pl:

eucl(4, 6):

a | b | r

4 | 6 | 4

6 | 4 | 2

4 | 2 | 0

A lényeg a második sor: az algoritmus mintegy ,,mellékhatásként'' magától megcserélte a két argumentumot, hiszen:

4-ben a 6 megvan 0-szor (hiszen ha már 1-szer venném, az túl sok lenne), marad maga a 4

4 % 6 = 4

A lényeg az, hogy mi történik, amikor a > b számokkal próbálom ki? Nézzük meg eucl(6, 4)-re! (Azt persze ):

int eucl(int a, int b)

{

. . while (b != 0)

. . {

. . . . int r = a % b;

. . . . a = b;

. . . . b = r;

. . }

. . return a;

}

Ez már jól kezeli az olyan ,,elfajuló'' ,,0-val osztós'' esetekekt is, mint pl.

eucl(12, 0) = 12

eucl(0, 0) = 0

Az előző változat ezekre hibaüzenetet adott (ott a második szám nem lehetett 0, az arra volt érzékeny). Ez a másik változat ezt az esetet ,,automatikusan'', ,,a számelméleti alapgondolat alaplogikájából fakadóan'' jól kezeli, és számelméletileg helyes válaszokat ad. Egy kicsit nehéz látni, hogy miért is működik egyáltalán ez a második változat, a futási táblázatokat kell néhány egyszerű példára elkészíteni, és abból lehet látni.