Informatika gyűjtemény

Egy szinttel feljebb 2. óra

2004050607080910

NézetNyomtat

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;
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

Egy első próbálkozás, még objektumok nélkül