Informatika gyűjtemény

Egy szinttel feljebb 1. óra

2004050607080910

NézetNyomtat

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