2. óra
Továbbra is nagy egészekkel foglalkozunk. Elkezdjük a nagypontosságú aritmetikát megvalósító modul megírását. A következő feladat csak kiinduló pont, több szakkör alatt áll össze a megoldás.
Feladat
A megoldás matematikája
Első észrevétel
Ha $T~|~t_1+X$ és $T~|~t_2+X$, akkor $T~|~(t_1+X)-(t_2+X)=t_1-t_2$. Ebből következik, hogy van felső korlát T-re, értelmes a kérdés.
Második észrevétel
Ha $T~|~t_1-t_2$ és $T~|~t_2-t_3$, akkor $T~|~(t_1-t_2)+(t_2-t_3)=t_1-t_3$. Ebből következik, hogy a maximális T a szomszédos $t_i$-k különbségének legnagyobb közös osztója.
Tehát amire szükségünk van...
Ki kell tudnunk számolni tehát nagy számok legnagyobb közös osztóját. Ismert, hogy a prímfelbontáson alapuló algoritmus nagy egészekre nem elég gyors, ezért az euklideszi algoritmussal dolgozunk. El kell tudnunk végezni az alapműveleteket nagy számokon.
Nagy számok ábrázolása
A nagy számok számjegyeit (tízes számrendszer) egy tömbben tároljuk, és feljegyezzük még azt, hogy hány jegyű a szám.
Pascal példa
type nagyszam = record
jegy : array[0..100] of byte;
h : byte;
end;
jegy : array[0..100] of byte;
h : byte;
end;
A jegy[0] az egyesek helyén álló jegy, a jegy[1] a tízesek helyén álló, és így tovább. Az utolsó jegy indexe h-1.
Első lépések egy nagypontosságú aritmetikai modul megvalósítása felé
Érdemes végiggondolni, milyen metódusokra lesz szükségünk.
Konstruktorok
- Nagy egész létrehozása 32-bites vagy 64-bites egészből
- Nagy egész létrehozása karakterláncból
Megjelenítés
- Nagy egész kiírása képernyőre
Relációk
- Nagy egész összehasonlítása 0-val
- Két nagy egész összehasonlítása
Operátorok
- összeadás
- kivonás
- szorzás
- maradékos osztás