Zárthelyi feladatok és megoldások

Programtervezés c. tárgyból


Programozás zárthelyi I.VI.                         2001.11.20/A 

Minden lap tetejére írja fel balra a feladat számát, jobbra a nevét és tankörét! Egy lapra csak egy feladat megoldását írja! A megoldásokban csak STANDARD PASCAL utasításokat, strukturált konstansokat és az assign elõre definiált eljárást használhatja. A megoldások során feltételezheti, hogy minden szükséges input adat az elõírt formátumban rendelkezésre áll. A bemeneti állományokat csak egyszer olvashatja be, és nem használhat munkaállományt. A feladatok helyes, mûködõképes megoldásával a feladatnál elérhetõ pontszám 70%-a szerezhetõ meg. A további 30% a nyelvi lehetõségek helyes alkalmazása és az algoritmusok eleganciája, ötletessége alapján szerezhetõ meg. Törekedjen a tiszta, strukturált megoldásokra! Szükség esetén alkalmazzon alprogramokat! Nem kell törekedni a trükkös megoldásokra, de a durva, ügyetlen módszereket kerülje!

1. feladat                                                  10p
Mit nyomtat a következő PASCAL program? Jelölje a szóközöket és soremelést is! Ne csak a végeredményt adja meg, hanem a jellemző adatstruktúrák értékeit ill. kapcsolatát is!

program namit(input, output);
type    poi = ^lanc;
        lanc = record
          a: integer;
          kov: poi
        end;
var     p, pe: poi;
        i: integer;
begin
        pe:= nil;
        for i:= 1 to 5 do begin
          new(p);
          if pe = nil then pe:= p;

          p^:= pe^; pe^.kov:= p; pe:= p;
          p^.a:= i;
        end;

        while p^.a > 0 do begin
          write(p^.a:3);
          p^.a:= pred(p^.a);
          p:= p^.kov;
        end;
        writeln;

end.



2. feladat                                                  10p
Írjon PASCAL függvényt, amely az alább definiált torpe_t típusra megvalósítja az ord függvény inverzét! Azaz, készítsen egy olyan függvényt, amely a paraméterként kapott sorszámból előállítja torpe_t megfelelő értékét!

type torpe_t = (szende, szundi, morgo, tudor, hapci, kuka, vidor);
function torp(s: integer): torpe_t;



3. feladat                                                  10p
Rajzolja le annak az állapotgépnek az állapot-átmeneti diagramját, vagy adja meg táblázatos formában, amely a standard inputról file végéig érkező szövegben megszámolja, hogy hány olyan csúcsos zárójelek közé zárt karaktersorozatot tartalmaz, amiben van @ jel!
Pl.: Ez nem jo, de <ez@ jo sorozat >. (5 p)
Valósítsa meg az állapotgépet! Az eredményt (sorozatok számát) a standard outputra írja ki! (5p)



4. feladat                                                  10p
Egy láncolt lista a következő elemeket tartalmazza:

type poi = ^lanc_elem;
  lanc_elem = record
  kulcs: integer;
  kov: poi
end;

A lista elején és a végén egy-egy strázsa elem van. A lista nem rendezett. Írjon PASCAL eljárást, amely a paraméterként kapott láncolt listáról leveszi (törli) az összes, a szintén paraméterként kapott kulcsnak (egész szám) megfelelő elemet! Definiálja az eljárást! (3 pont) Ügyeljen arra, hogy az eljárás akkor is jól működjön, ha a lánc üres ill. ha a törlés során szűnik meg minden eleme. A törölt elemeket az eljárás szabadítsa fel!



5. feladat                                                  20p
Egy elektronikus telefonközpont a következő formátumú naplót építi a hívásokról a HIV.DAT állományban:
   előfizető kapcsolási száma: 20 karakter
   hívott szám:                20 karakter
   kapcsolat időtartama:       valós szám (másodperc)
   díjzóna:                    egész szám
   dátum:                      11 karakter, (pl: 2000.11.21.)
   idő:                        8 karakter, (pl: 11:53:23)

Írjon PASCAL programot, amely kiírja azon előfizetők kapcsolási számát, akik 2001.11.20-án 17 és 18 óra között telefonáltak és a telefonszámukban van legalább 3 egymás után ismétlődő azonos számjegy. (pl. 85111456). A telefonszámok az állományban szóközök és egyéb elválasztók nélkül vannak tárolva. A 20 számjegynél rövidebb telefonszámok végén szóközök vannak.  
 


Megoldások I.VI.                          2001.11.20/A

1. feladat
A program elsõ ciklusa létrehoz egy gyûrüs láncot, amley öt elembõl áll. Ezek a mezõit a létrehozás sorrendjáben 1-tõl 5-ig tölti ki a for ciklus. Ezt követõen a while ciklus legutoljára felvett elemtõl kezdõdõen (melynek pointere az elsõ elemre mutat) elindul a gyûrûn, és minden rekord a mezõjét kiírja, majd csökkenti azt. A ciklusmag mindaddig tart amig az adott elem a mezõje nagyobb mint nulla. A program a következõ eredményt adja:

••5••1••2••3••4••4«

Ahol a szóközöket • a soremelést pedig « jelöli. A feladat teljes megoldásához meg kellett adni jellemzõ adatstruktúrák kapcsolatait is, amit legegyszerûben a gyûrûs lánc lerajzolásával lehet megadni.


2. feladat
Megoldási elv: ciklussal, vagy case utasítással elõállítjuk a paraméternek megfelelõ sorszámú értékét a torpe_t típusnak. Tudni kell, hogy a felsorolás típus elsõ elemének sorszáma nulla, bár az alábbi megoldásban ezt nem hasznátuk ki: (Hibakezelésre - olyan sorszmám, amihez nicsn törpe- nincs szükség, mert a feladatlap fejléce egyértelmûen definiálja, hogy minden feladat input adata helyes.)

type torpe_t = (szende, szundi, morgo, tudor, hapci, kuka, vidor);

function torp(s: integer): torpe_t;
var i: torpe_t;
begin
    i:= szende;
    while ord(i) <> s do i:= succ(i);
    torp:= i;
end;


3. feladat
Három állapot megkülönböztetésére van szükség: alap, nyit, kukac.
Az állapotgép táblázatos formában:

állapot/ch < > @ egyéb
alap nyit alap alap alap
nyit nyit alap kukac nyit
kukac kukac alap/sz:=sz+1 kukac kukac

Állapotgép megvalósítása:

program feladat3;
var all: (alap, nyit, kukac);
     ch: char;
     sz: integer;
begin
     sz:= 0;
     all:= alap;
     while not eof do begin
       read(ch);
       case all of
         alap: if ch = '<' then all:= nyit;
         nyit: if ch = '@' then all:= kukac
               else if ch = '>' then all:= alap;
        kukac: if ch = '>' then begin sz:= sz + 1; all:= alap; end;
       end;
     end;
     writeln(sz);
end.



4. feladat { feladat 4 }
A lánc elején van strázsa, így nem kell a láncra mutató pointert változtatni. Ezért az eljárásnak elegendõ értékparaméterben átadni a kezdõ pointert. A megoldás azonban nem használja ki, hogy a lánc elején van strázsa, mert a másolós módszer miatt az elsõ elem mindig megmarad. (Ez mindig használható, ha legalább egy strázsa van.)

type poi = ^lanc_elem;
     lanc_elem = record
       kulcs: integer;
       kov: poi
     end;

procedure torol(p: poi; k: integer);
var sp: poi;
begin
     p:= p^.kov;
     while p^.kov <> nil do begin
       if p^.kulcs = k then begin
         sp:= p^.kov;
         p^:= sp^;
         dispose(sp);
       end else
         p:= p^.kov;
     end;
end;



5. feladat
A feladat megoldásához az input állományt végig kell olvasni, és a beolvasott adat alapján azonnal kiírható az eredmény, így tárolásra nincs szükség. Tárolni csak akkor kellene, ha a feladat megtiltaná, hogy egy telefonszámot többször is kiírjunk. A megfelelõ idõpont kiválasztásához a szur függvényt, a feltételeknek megfelelõ telefonszám felismeréséhez pedig az ismet függvényt használjuk. Így a fõprogram egy egyszerû ciklus.

program telefon;
type szam_t = packed array [1..20] of char;
    dat_t = packed array [1..11] of char;
    tim_t = packed array [1..8] of char;
    inp_t = record
      ksz: szam_t;
      hsz: szam_t;
      ido: real;
     zona: integer;
      dat: dat_t;
      tim: tim_t
    end;

var be: file of inp_t;
    rec: inp_t;

function szur(r: inp_t): boolean;
begin
    szur:= (r.dat = '2001.11.20.') and
          ((r.tim[1] = '1') and (r.tim[2] = '7')
            or (r.tim = '18:00:00'))
end;

function ismet(sz: szam_t): boolean;
var i: integer;
    len: integer;
    szj: char;
begin
    len:= 0; szj:= sz[1];
    i:= 1; ismet:= false;
    while (i <= 20) and (sz[i] <> ' ') do begin
      if szj = sz[i] then begin
        
len:= len + 1;
        if len >= 3 then ismet:= true;
      end else begin        
        szj:= sz[i]; len:= 1;
      end;
      i:= i + 1;
    end;
end;

begin
    assign(be, 'hiv.dat');
    reset(be);
    while not eof(be) do begin
      read(be, rec);
      if szur(rec) then
        if ismet(rec.ksz) then writeln(rec.ksz);
    end;
end.


Szeberényi Imre
© BME  Irányítástechnika és Informatika Tanszék
Utolsó módosítás:2001-11-21