Példaprogramok és zh példák

Programozás alapjai I. ill.
Programtervezés I. tárgyhoz

Példaprogramok

A tárgy egyik célkitûzése, hogy általánosan alkalmazható algoritmusokat mustasson be. Az itt közölt példaprogramok az elôadásokon ill. gyakorlatokon elhangzott algoritmusokhoz kapcsolódó Pascal nyelvû programok. A programok írásakor igyekeztünk kerülni a standard Pascal-tól eltérô utasítások használatát, azonban esetenként ettôl eltértünk. Ennek oka az, hogy mûködô, kipróbálható programokat szeretnénk bemutatni, így kénytelenek voltunk alkalmazkodni egy ma elterjedten használt implementációhoz, a Turbo Pascal-hoz. Az alábbi táblázatból a kiválasztott programok forráskódban letölthetôk, illetve a megfelelô ikonra kattintva rövid magyarázó leírásuk megtekinthetô.

Egyszerûbb példaprogramok:

atlag1.pas Megadott számú valós szám átlagát számolja. Az adatokat a standard bemenetrõl olvassa.
atlag2.pas Standard bementrõl valós számokat olvas be file végéig. Kiszámítja a számok átlagát. Feltételezzük, hogy a számok összege nem fér el egy real értékben.
olvas.pas Numerikus adatok beolvasási változatai és gondjai.
crtunit.pas

Miért NE használjuk a CRT UNIT-ot, avagy miért ideges minden laborvezetõ a USES CRT láttán?

minmax.pas A standard bementrõl olvasott számok közül kiválasztja a legnagyobbat és a legkisebbet.
lnko.pas Két egész legnagyobb közös osztója.
ly.pas Standard bemenetrõl olvasott szövegben megszámolja az ly és az lly karaktersorozatokat
mpaspelda.zip   A fenti programok zipelve

Összetettebb példák:

szotagol.pas Állapotgéppel megoldott szótagoló program.
A magyar helyesírás formai szabályai alapján szótagol.
fordit.pas Szöveges állomány sorainak fordított sorrendben
történô kiíratása.
binfa.pas Bináris fa építés és keresés a fában.
bfa.pas   B-tree építés és keresés a fában.
hanoi.pas   "Hanoi tornyai" probléma rekurzív megoldása
perm.pas   Permutáció rekurcióval
nyolckir.pas   "Nyolc királynô" probléma egy megoldása
back-track algoritmussal.
labirint.pas   Labirintus bejárás back-track algoritmussal.
kupac.pas   Kupac rendezés, és tárolás tömbben.
sort.pas   Nagy méretû állományok rendezése
("kétszalagos" rendezés).
paspelda.zip   A fenti programok zipelve

atlag1.pas

Megadott számú valós számot olvas be, és kiszámítja a számok átlagát.

program atlag1;
var n: integer;              
{ adatok száma }
    
i: integer;              { ciklusváltozó }
    sum: real;
                             { összeg } 
    x: real;                                  { aktuális adat } 
begin
  
sum:= 0;                   { részösszeg = 0} 
  readln(n);
                { beolvassuk az adatok számát} 
  for i:= 1 to n do
begin
    readln(x);               
{ beolvassuk a következõ adatot }
 
    sum:= sum + x;
  end;
  writeln(sum/n:8:2);        
{ kiírjuk a végeredményt 8 helyiértékre és 2 tizedesjegyre }
end.


atlag2.pas

File végéig valós számokat olvas be, és kiszámítja a számok átlagát.
Feltételezzük, hogy a számok összege nem fér el egy valós típusban.
Ezért nem lehet a számok összegét képezni, majd osztani a darabszámmal.

Megoldás: (a1 + a2 + a3 + ... + an)/n = (a1 + a2 + a3 ... + an-1)/(n-1) * (n-1)/n + an/n

program atlag2;
var n: integer;              
{ adatok száma }
    atlag: real;
                         { átlag } 
    x: real;                                  { aktuális adat } 
begin
  atlag:
= 0;                 { pillanatnyi átlag = 0} 
  n
:= 0;                     { adatok száma }
  while not eof do begin     { amíg nincs file vége}
    readln(x);               
{ beolvassuk a következõ adatot }
 
    n:= n + 1;               { növeljük a darabszámot } 
    atlag:= atlag * ((n-1)/n + x / n;
  end;
  writeln(atlag);
end.


olvas.pas

Numerikus adatok (integer, real) beolvasásánál a read a bevezetõ szóközöket, soremelés jeleket figyelmen kívül hagyja. Ez lehetõvé teszi, hogy az ilyen adatok akár egy sorban, vagy akár soronként helyezkedjenek el. Ehhez semmi különlegeset nem kell tenni, csupán a read standard eljárást kell használni. Pl. 10 adat beolvasása egy tömbbe a következõ kódrészlettel történhet:

  for i:= 1 to 10 do     { amíg nincs file vége}
    read(a[i]);          
{ beolvassuk a következõ adatot }

Ekkor a számok közé tetszõleges számú szóközt, tabulátort, vagy soremelést is tehetünk.

Más a helyzet, ha file végéig szeretnénk beolvasni. Ekkor ugyanis fontos, hogy az utolsó adat beolvasása után a beolvasó ciklus leálljon. Ha viszont van még egy soremelés a legutolsó adat után, akkor nem fogja az EOF függvény jelezni a file végét, és így esetleg elindul egy újabb beolvasási ciklus. A következõ programrészletben pl. a while ciklus többször is lefuthat, mint ahány adatunk van.

  n:= 0;                     { adatok száma }
  while not eof do begin     { amíg nincs file vége}
    read(x);                 
{ beolvassuk a következõ adatot }
 
    n:= n + 1;               { növeljük a darabszámot } 
  end;

A probléma abból fakad, hogy az utolsó numerikus adat beolvasása után a read olvasó pointere az adat utáni soremelésre mutat, amire az EOF függvény nem jelez file végét (jogosan). Ha readln-t használunk, akkor az eldobja ezeket a karaktereket a sor végéig, de ekkor egy sorba csak egy adatot írhatunk, hiszen a readln a maradék adatokat is eldobná.
A probléma megoldását az jelentheti, hogy csak akkor hajtsunk végre readln-t, ha a sorban már nincs több adat. Erre mutat példát az alábbi kódrészlet:

  n:= 0;                     { adatok száma }
  while not eof do begin     { amíg nincs file vége}
    read(x);                 
{ beolvassuk a következõ adatot }
 
    n:= n + 1;               { növeljük a darabszámot } 
    if eoln then readln;     
{ ha sor végén vagyunk, akkor eldobjuk a maradék részt }
 
  end;

Ha az if utasítást while ciklusra cseréljük, akkor akár több üres sor is lehet a bemenõ adatsor végén.


minmax.pas

File végéig valós számokat olvas be, melyek közül kiválasztja a legnagyobb és legkisebb értéket.

Az összehasonlítás alapján történõ kiválasztásnál mindig ügyelni kell arra, hogy az összehasonlításokat csak a tényleges adatokkal végezzük el, és még a legelsõ hasonlításhoz se használjunk valamilyen, a programba beépített, a programozó által feltételezett adatot. Rendszerint hibás az a megoldás, amely a legelsõ összehasonlítást valamilyen feltételezett értékkel végzi el. (Ha kimegyünk a piacra a legnagyobb dinnyét megvásárolni, általában nem viszünk magunkkal egy saját dinnyét, hanem a piacon megtalálható dinnyéket hasonlítjuk össze.)

A fentiek miatt az alábbi megoldásban a legelsõ beolvasás után nem történik összehasonlítás, csupán eltároljuk az adatot, hogy a következõ beolvasás után ez az eltárolt adat képezze az összehasonlítás alapját. A legelsõ olvasás tényét egy logikai változóban tartjuk nyilván, így csak egy helyen történik beolvasás a programban:

program minmax;
var elso: boolean;          
{ jelzi, hogy ez a legelsõ szám }
    min, max: real;          
{ pillanatnyi legkisebb és legnagyobb }
    x: real;                
{ aktuális adat }
begin
  elso:= true;              
{ elsõ adat következik }
  while not eof do begin    
{ amíg nincs file vége }
    readln(x);              
{ beolvassuk a következõ adatot }
    if elso then begin      
{ legelsõ adat jön }
      min:= x;              
{ ez lesz a pillanatnyi legkisebb }
      max:= x;              
{ es a pillanatnyi legnagyobb is }
      elso:= false;          
{ bejött az elsõ szám }
    end else begin
      if x < min then        
{ ha az új adat kisebb a mimimumtól }
        min:= x;            
{ ez lesz az új minimum }
      if x > max then        
{ ha nagyobb a maximumtól }
        max:= x;            
{ ez lesz az új maximum }
    end
  end;
  writeln('Min:', min:8:3, '  Max:', max:8:3);
end.

Hasonlóan jó megoldáshoz jutottunk volna akkor is, ha legelsõ beolvasás a fõ ciklus elõtt történt volna meg, de ekkor fel kellett volna tételeznünk, hogy legalább egy adat van, vagy a ezt a beolvasást is feltételes blokkba kellett volna tenni. Ennek megfelelõ programrészlet a következõ:

  if not eof then readln(min); { legelsõ adat jön }
  max:= min;                 
{ ez lesz a pillanatnyi legkisebb és legnagyobb }

  while not eof do begin     { amíg nincs file vége }
    readln(x);              
{ beolvassuk a következõ adatot }
    if x < min then          { ha az új adat kisebb a mimimumtól }
      min:= x;            
  { ez lesz az új minimum }
    if x > max then          
{ ha nagyobb a maximumtól }
      max:= x;            
  { ez lesz az új maximum }
  end;


crtunit.pas

Általában minden rossz szokás sokkal gyorsabban terjed, mint a jó. Így van ez a CRT UNIT használatával is.

Nem vonom kétségbe, hogy a CRT UNIT szolgáltatásai nagyon hasznosak egy képernyõ-orientált alkalmazásban, de

  1. Nem szabványos.
    Általában igaz, hogy minden programozási nyelvet úgy igyekszünk tanítani, hogy az ne kötõdjön az adott hardver vagy szoftver környezethez, ugyanis ezek gyorsabban változnak, mint a programozási nyelvek.
  2. Megváltoztatja a standard input/output értelmezését és mûködését.
    A CRT UNIT használata (csupán a betöltése is) megváltoztatja a standard input/output értelmezését. A standard input ill. output lényegéhez hozzá tartozik, hogy az nem feltétlen a billentyûzet ill. a képernyõ. Ez a gyakorlatban azt jelenti, hogy az alapértelmezés szerinti hozzárendelést az input/output átirányítással meg lehet változtatni. A CRT UNIT viszont ezt a hozzárendelést "kõbe vési", igaz cserébe hatékony hozzáférést biztosít a PC képernyõjéhez, és billentyûzetéhez.
    CRT UNIT-ot használó program standard kimenetét ill. bemenetét nem lehet átirányítani sõt az EOF függvény sem figyeli többé a file végét, bár ez utóbbit a checkEOF:= TRUE utasítással utólag be lehet kapcsolni.
  3. Olyanok is használják, akiknek rendszerint fogalmuk sincs róla, hogy mit csinál, és csodálkozva, sokszor felháborodva veszik észre, hogy az standard input/outputra elmondottak "nem mûködnek".

A fentiek miatt a CRT UNIT használata kerülendõ.


lnko.pas

Beolvas két egész számot, és kiszámítja a legnagyobb közös osztójukat az ún. euklideszi algoritmussal.

program lnko;
var x, y: integer;          
{ a két szám tárolására}
begin
  readln(x, y);              
{ beolvassa a kát egész éretéket }
  write('LNKO(', x, ',', y, ')=');    
{ bemenõ adatok kiírása }
  while x <> y do begin
    if x > y then x:= x - y
    else y:= y - x;
  end;
  writeln(x);                
{ eredmény kiírása }
end.


ly.pas

A program a standard inputról file végéig olvasott szövegben megszámolja az ly ill. az lly karaktersorozatokat.

A megoldást egy olyan állapotgéppel képzeljük el, amelynek három állapota van:

Az állapotgép a bejövô karakterek típusa és az aktuális állapot alapján változtatja az állapotát és valamilyen tevékenységet végez. A bejövô karakterek a következôk lehetnek:

Az állapotgépet következô állapottáblával írhatjuk le: (a táblában pirossal jelöltük a következô állapotot, feketével az állapotváltozáshoz tartozó tevékenységet)  

állapot / típus l y egyéb
alap ljott
alap alap
ljott lljott alap/
+1
alap
lljott lljott alap/
+2
alap

A tevékenységek a következôk:

A szótagoló programot megvalósító pszeudó kód:

all:= alap;
sz:= sz + 1;

while not eof do begin
  read(ch);
  ch és all alapján az állapot változtatása ill. a tevékenység végrehajtása;
end;
write(sz);
 

A fentiek alapján a teljes program:

program ly;
var sz: integer;
    ch: char;
 
  all: (alap, ljott, lljott);            { állapotváltozó }
begin
    all:= alap;
    
sz:= 0;
    while not eof do begin

      read(ch);
      case all of
        alap:
          if ch = 'l' then all:= ljott;

        ljott:
          if ch = 'l' then
            all:= lljott
          else if ch = 'y' then begin
            all:= alap;
            sz:= sz + 1;
          end else
            all:= alap;

        lljott:
          if ch = 'y' then begin
            all:= alap;
            sz:= sz + 2;
          end else if ch <> 'l' then
            all:= alap;
      end;
    end;
    writeln('ly-ok szama:', sz);

end;


szotagol.pas

A program a standard inputról beolvasott szöveget a következô szabályok alapján szótagokra bontva kiírja a standard outputra:

A megoldást egy olyan állapotgéppel képzeljük el, amelnyek három állapota van:

Az állapotgép a bejövô karakterek típusa és az aktuális állapot alapján változtatja az állapotát és valamilyen tevékenységet végez. A bejövô karakterek a következôk lehetnek:

Az állapotgépet következô állapottáblávál írhatjuk le: (a táblában pirossal jelöltük a következô állapotot, feketével az állapotváltozáshoz tartozó tevékenységet)

állapot / típus mgh msg egyéb
alap smgh/
put ch
alap/
put ch
alap/
put ch
smgh smgh/
put -, put ch
smsh/
x = ch
alap/
put ch
smsh smgh/
put -, put x, put ch
smsh/
put x, x = ch
alap/
put x, put ch

A tevékenységek a következôk:

A szótagoló programot megvalósító pszeudó kód:

stat:= alap;
while not eof do begin
  read(ch;
  tipus:= ch típusa;
  típus es stat alapján a táblázat végrehajtása;
end;
if stat = smsh then
  write(x);


Az állapotgépet megvalósító programrészlet elsô változata:

case tipus of
  mgh:                   
{ magánhangzó jött }
    begin
      if stat <> alap then begin
        write('-');
        if stat = smsh then
          write(x);      
{ kiírja a tárolt karaktert }
      end;
      write(ch);
      stat:= smgh;       
{ a következô állapot smgh }
    end;
  msh:                   
{ mássalhangzó jött }
    if stat = alap then
      write(ch)          
{ maradunk alap állapotban }
    else begin
      if stat = smsh then
        write(x);
      x:= ch;            
{ tárolás }
      stat:= smsh        { a következô állapot smsh }
    end;
  egyeb:
    begin
      if stat = smsh then
        write(x);        
{ kiírja a tárolt karaktert }
      write(ch);
    end
end;

A típust a következô kódrészlettel határozhatjuk meg:

if not ((ch >= 'A') and (ch <= 'Z') or
        (ch >= 'a') and (ch <= 'z')) then     
{ nem betû }
  tipus:= egyeb
else if (ch = 'A') or (ch = 'E') or (ch = 'O') or
        (ch = 'U') or (ch = 'I') or (ch = 'a') or
        (ch = 'e') or (ch = 'o') or (ch = 'u') or (ch = 'i') then
  tipus:= mgh                                 
{ magánhangzó }
else
  tipus:= msh;                                
{ mássalhangzó }


Halmaz alalmazásával a típus meghatározásának kódrészlete így módosul:

if not (ch in ['A'..'Z','a'..'z']) then       { nem betû }
  tipus:= egyeb
else if ch in ['A','E','O','U','I','a','e','o','u','i'] then
  tipus:= mgh                                 
{ magánhangzó }
else
  tipus:= msh;                                
{ mássalhangzó }

Vegyük észre, hogy az állapottábla két fajta információt tartalmaz:

  1. a következô állapotot
  2. az állapotváltáskor végrehajtandó tevékenységet

Ezek az elôzô állapottól és a bejövô karakter típusától függnek. Ha az állapottábla információit egy-egy kétdimenziós tömbbe helyeznénk, akkor egyszerû indexeléssel megkaphatnánk a következô állapotot, és egy másik táblából pedig megállapíthatnánk a végrehajtandó tevékenységet. Ez utóbbihoz kódoljuk le a tevékenyzégeket. Mivel 3 állapotunk van, és a bejövô karakternek is 3 típusa lehet, így legfeljebb 3x3=9 különbözô tevékenységünk lehet. Jelen esetben azonban ettôl kevesebb, csak 6 van. Ezek kódolását jelöltük korábban zöld színnel a tevékenységek leírásánál.

Ha fetételezzük, hogy a következô állapot a kovstat, a végrahajtandó tevékenység pedig az akció tömbben van eltárolva, akkor a programunk állapotgépet megvalósító részlete így egyszerûsödhet:

case akcio[stat,tipus] of
  pc: write(ch);
  pkc: write('-', ch);
  pkxc: write('-', x, ch);
  xc: x:= ch;
  pxxc: begin write(x); x:= ch end;
  pxc: write(x,ch);
end;
stat:= kovstat[stat, tipus];

A végleges porgramkódban kihasználtuk a Turbo Pascal strukturált konstans lehetóségét. Így az akció és kovstat tömböket megfelelôen feltöltött konstans tömbökkel valósítottuk meg. Ez a megoldás hatékonyabb, mint a standard Pascal adta futásközbeni feltöltési lehetôség.


fordit.pas

A program egy egyszerû példa a láncolt lista építésére. A program a standard inputról sorokat olvas be, azokat egy láncolt adatszerkezetben tárolja, majd fordított sorrendben visszaírja a standard outputra. A sorok tárolásához egy sor_rec típusú rekordot használunk, amelyben maximum 80 karakter, a tényleges sorhossz és egy pointer van a következô rekordra.

const LEN = 80;                         { maximális sorhossz }
type sor = array [1..LEN] of char;      { tipus a sor tárolásához }
poi = ^sor_rec;
sor_rec = record
  asor: sor;                            
{ a sor karakterei }
  hossz: 0..LEN;                        { a tényleges sor hossza }
  kovs: poi                             { következô rekord pointere }
end;

A lánc építése úgy történik, hogy a legelôször beolvasott sor van a lánc végén, a legutoljára beolvasott sor pedig a lánc elején:

utolso:= nil;                           { a lista kezdetben üres }
while not eof do begin
  new(p);                               
{ felvesszük az uj elemet }
  beolvas(p);                           
{ beolvas }
  p^.kovs:= utolso;                     { befûzzük a listába }
  utolso:= p;                           { erre fog mutatni az utolsó }
end;


binfa.pas

A program szavakat olvas be a standard inputról. Ezeket bináris fában tárolja, majd rendezve kírja a standard outputra. Az adatszerkezet jobb megértése érdekében a fát karakteres formában ki is "rajzolja" (90 fokkal elforgatva). A fa egy elemének tárolásához a következô adatszerkezetet használjuk:

const stringh = 6;                      { szavak maximális hossza }
type str = array [1..stringh] of char;  { tároló a szavaknak }
mut=^fa_elem;                           { fa_elem mutató }
fa_elem=record                          { a fa egy eleme }
  aszo:str;                             { a tárolt szó }
  szaml:integer;                        { hányszor fordult elô ez a szó }
  jobb,bal:mut                          { bal és jobb mutatók }
end;

A fa építése a faepit eljárással történik, ami paraméterként kapja a fa gyökerére mutató pointert, és a felveendô új szót. Ha a paraméterként kapott pointer NIL értékû, akkor felvesz egy új fa_elem típusú rekordot és ebben tárolja a kapott szót. Az újonnan felvett elem pointerét (címét) a VAR paraméterátadás mechanizmusával visszaadja az eljárás hívójának. Ha a paraméterként kapott pointer nem NIL értékû, akkor az eljárás rekurzívan hívja önmagát.

procedure faepit(var p:mut; szo:str);   { szó elhelyezése a p részfában }
begin
  if p = nil then begin
    new(p);                             
{ uj elem }
    with p^ do begin
      aszo:= szo;                       
{ a szó beírása }
      szaml:= 1;                        { számláló = 1 }
      bal:= nil; jobb:= nil             { pointerek = nil }
    end
  end else if szo < p^.aszo then
    faepit(p^.bal, szo)                 
{ bal részfában tovább }
  else if szo > p^.aszo then
    faepit(p^.jobb, szo)                
{ jobb részfában tovább }
  else
    p^.szaml:= p^.szaml+1               
{ ua. a szó jött }
end;

Az így felépített fában a binker függvénnyel lehet egy szót megkeresni. A teljes fa tartalmának rendezett kiíratásához pedig a fakiir eljárást használjuk. Ez utóbbi eljárás az építô eljáráshoz hasonlóan rekurzív. Mivel az építés során mindig a bal ágon helyeztük el a kisebb (alfabetikusan rendezve) szavakat, ezért a legkisebb szó a legbaloldalibb ágon van. Így fakiir eljárás is a legbaloldalibb elem kiirásával kezdi a kiírást (addig megy balra, amig csak tud). Ezt követôen egy lépest teszünk jobbra, de innen megint addig megyünk balra, amig csak lehet. Figyeljük meg, hogy mindig csak balvisszatérés után van kiirás. Jobb oldalról való visszatéréskor nincs.

procedure fakiir(p: mut);               { p részfa bejárása és kiírás }
begin
  if p <> nil then begin                
{ ha a mutató nem nil }
    fakiir(p^.bal);                     { balra amíg csak lehet }
    writeln(p^.aszo,': ',p^.szaml);     { balvisszatérés után kiírás }
  
 fakiir(p^.jobb);                    { majd egy lépés jobbra }
  end;
end;


hanoi.pas

A program Hanoi tornyairól szóló legendán alapuló logikai játék megoldását adja. A legenda szerint Hanoi egyik temploma elôtt három oszlop állt. Az egyik rézbôl, a másik ezüstbôl, a harmadik pedig aranyból volt. A rézoszlopon száz lyukas korongot raktak egymásra, úgy hogy a korongok átmérôje alulról felfelé haladva egyre csökkent. Egy öreg szerzetes azt a feladatot kapta, hogy a korongokból álló tornyot a rézoszlopról vigye át az aranyoszlopra, de úgy, hogy egyszerre csak egy korongot vihet, és soha nem tehet nagyobb korongot kisebbre. A legenda szerint a szerzetes hamar megértette, hogy munkájában fel kell használnia az ezüstoszlopot. Leült és tervet készítet, miszerint a feladatot három lépesben meg tudja csinálni:

  1. Átviszem a rézoszlopon levô, 99 korongból álló tornyot az ezüstoszlopra.
  2. Átviszem az utolsó, legnagyobb korongot a rézoszlopról az aranyoszlopra.
  3. Végül átviszem az ezüstoszlopon levô, 99 korongból álló tornyot az aranyoszlopra.

A terven rágódva a szerzetes rájött, hogy az 1. es 3. lépésben leírt feladatokat nehezebb végrehajtani, ezért úgy döntött, hogy ezt a munkát legöregebb tanítványával fogja elvégeztetni. Tanítványával közölte tervét és a feladat megoldását nyújtó algoritmust:

Módszer arra, hogy hogyan vigyünk át N korongból álló tornyot az egyik oszlopról a másikra a harmadik oszlop felhasználásával:

  1. Abban az esetben, ha a torony egynél több korongból áll, bízd meg a legöregebb tanítványodat, hogy a szóban forgó torony felsô N-1 korongját vigye át az elsô oszklopról a harmadikra, miközben a második oszlopot használhatja.
  2. Vidd át magad az elsô oszlopon maradt egyetlen korongot a másodikra.
  3. Abban az esetben, ha a torony egynél több korongból áll, bízd meg a legöregebb tanítványodat, hogy a szóban forgó torony felsô N-1 korongját vigye át a harmadik oszklopról a másodikra, miközben az elsô oszlopot használhatja.

A szerzetes algoritmusát Pascal-ban úgy írtuk meg, hogy az oszlopokat A, B, C betûvel, illetve forras, cél és seged azonosítokkal jelöltük, a korongokat pedig a sorszámukkal azonosítjuk (a nagyobb korong száma nagyobb). A torony nevû eljárás N korong magasságú torony átrakasát végzi a 'forras' oszlopról a 'cel' oszlopra úgy, hogy közben a 'seged' oszlopot hasznalhatjuk:

procedure torony(n: integer; forras, cel, seged: char);
begin
  if n > 1 then                  
{ ha több mint 1 korong van }
    torony(n-1,forras,seged,cel);{ n-1-et a 'tanítvány' átrak a seged-re }
  writeln(forras,'->',cel);      { helyére rakjuk az utolsó korongot}
  if n > 1 then                  { ha több mint 1 korong van }
    torony(n-1,seged,cel,forras);{ 'tanítvány' a seged-rôl a helyére tesz }
end;

Az eredeti algorimus kis módosításával a torony eljárást rövidebben is felírhatjuk, igaz ekkor egy szinttel mélyebb rekurzióhoz jutunk, ami azonban a végrehajtási idô szempontjából nem eredményez jelentôs vátozást:

procedure torony(n: integer; forras, cel, seged: char);
begin
  if n > 0 then begin           
{ ha van korong }
    torony(n-1,forras,seged,cel);{ n-1-et a 'tanítvány' átrak a seged-re }
    writeln(forras,'->',cel);    { helyére rakjuk az utolsó korongot}
    torony(n-1,seged,cel,forras);{ 'tanítvány' a seged-rôl a helyére tesz }
  end
end;


Zárthelyi példák

A zárthelyikre való felkészüléshez bemutatunk néhány teljes feladatsort és azok megoldását. A feladatok megoldásához 100 perc áll rendelkezésre. A megoldáshoz csak egy saját kézzel írt A4-es méretû puska hasnzálható. A feladatsorok között informatika szak számára és villamos szak számára készített feladatok egyaránt vannak (elsô betû: i = informatika, v = villamos). Általában elmondható, hogy az informatika szakos feladatok némileg nehezebbek.

i951123a, i951123b, i951211p
v951123a, v951123b, v951123c, v951211p
v961128a, v961128b, v961128c,

i991125a,
i991125b,
v991123a, v991123b, v991123b, v991123d
v001121a.doc, v001121b.doc, v001204a.doc, v010103a.doc
v011120a.doc, v011120b.doc, v011120c.doc, v011120d.doc, v011120a
v031125a.doc, v031125b.doc,
v031218a.doc

A fenti állománynevekben a .tx8 kiterjesztés CWI kódot, a .doc kiterjesztés WORD dokumentumot, a .meg kiterjesztés pedig a CWI vagy ASCII kódban levõ megoldásokat jelöli. A kiterjesztés nélküli nevek html formátumú dokumentumokat taraknak, melyek a feladatot és a megoldást is tartalmazzák. A feladatlapok és a megoldások tömörítve is elérhetôk paszh.zip.


Tantárgy adatlap és követelmények


Szeberényi Imre
© BME  Irányítástechnika és Informatika Tanszék
Utolsó módosítás:2004-01-08