Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2004-2005‎ > ‎

1. óra - Bemelegítés

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. ( f1=f2=1,fn=fn-1+fn-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 fi 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

Comments