1.óra - Bemelegítés
Elmélet
A programozási környezet kiválasztása
Programjaink hatékonyságát két szempont szerint vizsgáljuk: memóriaigény és futási idő. Általában igaz, hogy több memóriát felhasználva gyorsabb programokat lehet írni, illetve memóriát lehet megsprórolni, ha lemondunk a gyorsaságról.
Egy versenyen mérlegelni kell, hogy melyik szempontot mennyire érvényesítjük a megoldó algoritmus tervezésekor. A programozási környezet (és nem a nyelv!!!) megválasztása meghatározza, hogy milyen erőforráskorlátozások mellett kell dolgoznunk. Pascal programozóknak célszerű a Delphi környezetet választani a Borland/Turbo Pascal helyett, mert így a futási idejű verem (runtime stack) 1 MB lehet, míg TP/BP-ben csak 64K a megengedett méret, továbbá nem kell 64K-ba beférnie globális változóinknak. (A Delphi védett módban futó 32 bites alkalmazást fordít, a Pascal valós módban futó 16 bitest.)
A stack mérete akkor kritikus, amikor rekurzív módon oldunk meg egy feladatot. (És ilyet gyakran fogunk csinálni.) A statikus adatterület méretétől függően nagy tömbök is használhatók, és látni fogjuk, hogy ez gyorsabb programot eredményezhet.
Jó alternatíva a Free Pascal, illetve a linuxos GNU C, de ezek sajnos nem használhatók a NTSZ versenyen.
A delphi környzet használata
A Delphiből csak annyit használunk, hogy 32bites kódót fordít.
File->New->Other->Console application
Hasznos beállítások:
Range checking [x]
Overflow cheking [x]
Stack frames [x]
Pentium-safe FDIV [x]
Természetesen tesztelés után kikapcsoljuk ezeket, hiszen a futásidejű ellenőrzések lassítják a programot.
Rekurzív programok hatékonysága
Egy rekurzív program elemzésekor a rekurzíó maximális mélységét és a rekurzív hívások számát kell becsülnünk.
Első példánk a Fibonacci sorozat elemeinek kiszámításáról szól. (
$f_1 = f_2 = 1, f_n = f_{n-1} + f_{n-2}$, ha $n > 2$.)
Naív megoldásunk a következő:
Fibonacci(n)
Ha n < 3 akkor Fibonacci := 1
különben Fibonacci := Fibonacci(n-1) + Fibonacci(n-2)
Elágazás vége
Eljárás vége
Kis gondolkozás után rájövünk, hogy megoldásunk használhatatlan, ha $n > 50$. A probléma az, hogy majdnem minden $f_i$ elemet többször is (sokszor) kiszámolunk. (Hányszor?) A baj orvosolható: feljegyezzük azokat az értékeket, melyeket már kiszámoltunk, és ha újra szükség van rájuk, egyszerűen kimásoljuk a feljegyzett értéket.
A feljegyzéses módszer
A javított változat egy globális cache (gyorsítótár) tömböt használ, a cache tömb minden eleme kezdetben 0.
Fibonacci(n)
Ha cache[n] = 0 akkor
Ha n < 3 akkor cache[n] := 1
különben cache[n] := fib(n-1) + fib(n-2)
Elágazás vége
Elágazás vége
Fibonacci := cache[n]
Eljárás vége
Jegyezzük meg, hogy az $n$. Fibonacci szám $n-2$ összeadással előállítható, tehát a rekurzív megoldás még a második változatban sem a leggyorsabb megoldás, csak illusztráció a feljegyzéses módszerhez.
Feladatok
