Zárthelyi feladatok és megoldások

Programozás alapjai I. c. tárgyból


Programozás zárthelyi I.INF.                         1999.11.25/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! A 6. feladat megoldása csak azoknak kötelezõ, akik jelezték, hogy megajánlott jegyet szeretnének korábbi tanulmányaik alapján.

Megszerezetõ pontszám: 60+10p. Minimális pontszám az elégségeshez: 29p

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ô változó értékeket is!

program namit(input, output);
type  torpe_t = (hapci, tudor, vidor, szende, szundi, morgo, kuka, hofeherke);
        banya_t = set of torpe_t;
        poi = ^lanc;
        lanc = record
          torpe: torpe_t;
          kov:   poi
        end;
var  &nbspbanya: banya_t; torpe: torpe_t;
        p1, p2: poi;
begin
        new(p1); p2:= p1; torpe:= hapci;
        banya:= [szende];
        while banya <> [] do begin
          p2^.torpe:= torpe;
          new(p2^.kov); p2:= p2^.kov;
          banya:= banya - [torpe]; torpe:= succ(torpe);
        end;
        p2^.torpe:= torpe; p2^.kov:= p1;
        while p1^.torpe < morgo do begin
          write(ord(p1^.torpe):3);
          if p1 = p2 then writeln;
          p1^.torpe:= succ(p1^.torpe);
          p1:= p1^.kov;
        end;
        writeln('''');
end.



2. feladat                                                  10p
Írjon PASCAL programot, amely megszámolja, hogy a standard bemeneten file végéig érkezõ szövegben hány szó kezdõdik cs, sz, dz, zs, ly, ny, ty, vagy gy betûvel! Szónak tekintünk minden betûvel kezdõdõ alfanumerikus karaktersorozatot.


3. feladat                                                  10p
Írjon PASCAL függvényt, amely eldönti, hogy a paraméterként kapott maximum 200 elemû valós tömb elemei olyan kupacot alkotnak-e, amelyben a kisebb elem van felül! A függvény paraméterként kapja a tömbben levõ elemek számát és a tömböt.
TYPE VEC_T = ARRAY [1..200] OF REAL;
FUNCTION KUPACE_E(A: VEC_T; N: INTEGER): BOOLEAN;


4. feladat                                                  10p
Készítsen PASCAL eljárást, amely a paraméterként kapott két, maximum 298 karakter hosszú 3-as számrendszerbeli pozitív egész számot (S1, S2) összeadja (S1-S2), és az eredményt a szintén paraméterként kapott E tömbben adja vissza. Az S1 ill. S2 bemenõ paraméterként kapott tömbben a két szám balra igazítva helyezkedik el, és a szám végét egy szóköz karakter jelzi. Az eredményt is hasonló formátumban állítsa elõ!
TYPE SZAM_T = ARRAY [1..300] OF CHAR;
PROCEDURE KIVON(S1, S2: SZAM_T; VAR E: SZAM_T);


5. feladat                                                  20p
Az egyetemi telefonközpont minden beszélgetésrõl a következõ adatokat írja a HIVAS.TXT nevû szöveges állományba:

hívó fél azonosítója:    13 karakter
hívott fél azonosítója:  13 karakter
a hívás kódja:            1 karakter (H: hivatalos, M: magán)
beszélgetés díja:        maximum 11 pozíciós valós szám (Ft)
dátum:                   11 karakter, (pl: 1999.11.25.)
idõ:                     8 karakter, (pl: 11:53:23)

Az egyes információs mezõket egy-egy szóköz választja el egymástól, és minden hívás adata külön sorban, sor elején ezdõdik. Írjon Pascal programot, amely a HIVAS.TXT állományt feldolgozva, a hívó fél azonosítója szerint növekvõ sorrendben, azon belül hónaponkénti bontásban kiírja az 1999-ben kezdeményezett hivatalos (H) hívások havidíját, és összesített díját! A feladatot dinamikus adatszerkezet használatával oldja meg! 



6. (jutalom) feladat                                  20p
Készítsen PASCAL programot, amely a standard inputról beolvas 10 decimális számjegyet! A számjegyek beolvasási sorrendjét megtartva a program állítsa elõ az összes olyan mûveletsort (a számjegyek közé tetszõleges helyre mûveleti jelet téve), amely eredménye 1999! A megengedett mûveleti jelek összeadás (+), kivonás (-), szorzás (*), maradékrész képzése (%). Tételezze fel, hogy a mûveleti jelek azonos precedenciájúak.
 
 


Megoldások I.INF.                          1999.11.25/A 

1. feladat
A banya halmaz íipusú változó kezeti értéke szende, a torpe változóé pedig hapci, amit a while ciklusban a banya halmazból midig kivonunk, amíg a halmaz ki nem ürül. Így a ciklus 4-szer fut le, és közben kialakít egy láncot. A lánc 5 elemû mert a ciklus elindulása elõtt is kialakul egy elem. Az elemek torpe mezõjébe a torpe váltózó egyes értékei (hapci, tudor, vidor, szende, szundi) íródik be. Az utóbbi érték a ciklus lefutása után íródik be és ekkor a lánc egy gyûrûvé alakul át, mivel az utolsó elem pointere az elsõre (p1) mutat. A második while ciklus ezen a gyûrûn megy körbe, amig valamelyik elem torpe mezõje el nem éri a morgo értéket. Minden ciklusban 3 mezõszélességre kiíródik az aktuális elem torpe mezõjének sorszáma, majd növekszik az érték. A gyûrû ötödik elemét elérve minden ciklusban soremelés is történik. A ciklus lefutása után egy aposztróf és egy soremelés íródik ki. A program a következô eredményt adja:

  0  1  2  3  4
  1  2  3  4'



2. feladat
Megoldási elv: egy "ablakot" húzunk (léptetünk) végig az állományon,  melyet minden lépésben összehasonlítunk a várt mintákkal, esetünkben ez nem más mint a megadott kettõsbetû+szóköz. Az "ablakban" minden nem alfanumerikus karatert szóközre cserelünk.
Algoritmus vázlat:
mintak_es_a_szamlalo_inicialialasa;
while leptet(ablak) do
  if vizsgal(mintak, ablak) then sz:= sz + 1;
writeln(sz);
(Az alporgramok specifikációit a megjegyzések tartalmazák.)

program feladat_2;
const
    MINTA_N = 8;                 { a minták száma }
    ABLAK_H = 3;                 { a minta hossza, amit keresunk }
type
    ablak_t = packed array [1..ABLAK_H] of char;  { ablak típusa }
    mintak_t = array [1..MINTA_N] of ablak_t;     { minták tömbtípusa }
var ablak: ablak_t;              { ablak változója }
    mintak: mintak_t;            { minták tömbje }
    sz: integer;                 { számláló }

{ leptet specifikáció:
  Az ablakot egy karaterrel tovabblépteti. Minden nem alfanumerikus
    karatert szóközzel helyettesít (file végét is).
  Bemenet: standard input
           minta hossza (program szinten konstans)
  Kimenet: pameterként kapott ablak
           logikai erték: true, ha nem volt file vége
}
function leptet(var a: ablak_t): boolean;
var i: integer;             { ciklusváltozó }
begin
    leptet:= false;
    for i:= 1 to ABLAK_H-1 do a[i]:= a[i+1];   { léptet }
    if not eof then begin
      leptet:= true;        { nem file vége }
      read(a[ABLAK_H]);     { új karakter }
      if not (a[ABLAK_H] in ['A'..'z','a'..'z','0'..'9']) then
      a[ABLAK_H]:= ' ';     { nem alfanumerikus }
    end
end;

{ vizsgal spec:
  A parameterként kapott minták tömböt összehasonlítja az ablakkal.
  Bemenet: minták tömb,
           ablak,
           minták száma és hossza (program szinten konstans)
  Kimenet: logikai érték
}
function vizsgal(m: mintak_t; a:ablak_t): boolean;
var i: integer;             { ciklusváltozó }
    ok: boolean;
begin
    i:= 1; ok:= false;
    while (i <= MINTA_N) and not ok do begin { amíg nem talál, vagy el nem fogy }
      ok:= m[i] = a;        { összehasonlít }
      i:= i + 1;            { következõ minta }
    end;
    vizsgal:= ok;           { eredmény }
end;

begin
    mintak[1]:= ' cs'; mintak[2]:= ' sz'; mintak[3]:= ' dz';
    mintak[4]:= ' zs'; mintak[5]:= ' ly'; mintak[6]:= ' ny';
    mintak[7]:= ' ty'; mintak[8]:= ' gy';
    sz:= 0; ablak:= '   ';    { inicializál }
    while leptet(ablak) do
      if vizsgal(mintak, ablak) then sz:= sz+1; { számolunk, ha kell }
    writeln(sz, ' darab ilyen karaktersorozat volt.');
end.



3. feladat{ 3. feladat }
Végigmegyünk az elemeken, és megvizsgáljuk, hogy minden elemre teljesül-e a feltétel. Elegendõ csak a feléig vizsgaálni, hiszen a kupac definiciója szerint a levélelemek automatikusan kupacot alkotnak.

function kupac_e(a:vec_t; n: integer): boolean;
var i: integer;
begin
    kupac_e:= true;                         { feltetelezzük, hogy jó }
    for i:= 1 to n div 2 do begin
      if a[i] > a[2*i] then kupac_e:= false;{ ha a gyerekétõl nagyobb, akkor nem kupac }
      if 2*i+1 <= n then if a[i] > a[2*i+1] then kupac_e:= false;
    end;
end;



4. feladat { feladat 4 }
A feladat specifikációjából adódóan csak karaktetesesen végezhetõ el mûvelet, mivel sem egész, sem valós típusban nem tudjuk a megadott számokat tárolni. A megoldást egy kicsit bonyolítja, hogy a számok balra tömörítettek, és eltérõ hosszúságúak lehetnek. Ezért elõször mindkét számot jobbra toljuk (ez megtehetõ, mert értékparaméterként veszük át), és közben kiegészítjük bevezetõ nullákkal, majd a végeredménybõl ezeket eltávolítjuk.

procedure osszead(s1, s2: szam_t; VAR e: szam_t);
const RADIX = 3;                   { számrendszer }
      LEN = 300;                   { szám hossza + 1 }
var i: integer;                    { indexváltozó }
    c: integer;                    { túlcsordulás }

{ jobbra:
  Jobbra tolja a számot, és bevezetõ nullákkal egészíti ki.
  Bemenet: szám
  Kimenet: szám
}
procedure jobbra(var s: szam_t);
var i, j: integer;
begin
    i:= 1;
    while s[i] <> ' ' do i:= i + 1;{ megkeresi a szóközt }
    j:= LEN;
    while i >= 1 do begin          { másol }
      s[j]:= s[i]; i:= i - 1; j:= j - 1;
    end;
    while j >= 1 do begin
      s[j]:= '0'; j:= j - 1;
    end;
end;

{ balra:
  Balra tolja a számot. A bevezetõ nullákat eldobja.
  Bemenet: szám
  Kimenet: szám
}
procedure balra(var s: szam_t);
var i, l: integer;
begin
    l:= 1;
    while s[l] = '0' do l:= l + 1;  { megkeresi az elsõ nem nulla számjegyet }
    if s[l] = ' ' then l:= l - 1;   { ha nulla lenne az eredmény }
    for i:= l to LEN do             { másol }
      s[i-l+1]:= s[i];
end;

{ cad:
  Összead két RADIX számrendszerû karakert, kezeli a túlcsordulást
  Bemenet: a két karakter
           elõzõ digitrõl az áthozat
  Kimenet: eredmény karakter (függvényérték)
           túlcsordulás
}
function cad(c1, c2: char; var b: integer): char;
var r: integer;
begin
    r:= ord(c1) + ord(c2) + b - 2*ord('0'); { ez az int eredmény }
    if (r >= RADIX) then begin     { túlcsordult ? }
      r:= r - RADIX;               { kiszámítjuk az uj értéket }
      b:= 1;                       { jelezzük a túlcsordulast }
    end else
      b:= 0;                       { nincs túlcsordulás }
    cad:= chr(r+ord('0'));         { eredmény karakteresen }
end;

begin
    jobbra(s1); jobbra(s2);
    c:= 0;                         { kezdetben nincs túlcsordulás }
    for i:= LEN-1 downto 1 do begin  { midket szám pontosan LEN-1 digites }
     e[i]:= cad(s1[i], s2[i], c);  { összeadás karakterenként }
    end;
    e[LEN]:= ' ';
    balra(e);                      { eltüntetjuk a bevezetõ nullákat }
end;



5. feladat
A feladatot egy egyszerû hívó azonosító szerint rendezett lánccal oldjuk meg. Minden elemben 12 hónap adatait tároljuk, és folyamatosan frissítjük. A lánc végén strázsa van, az új elem beszúrását a "beszúrunk elé úgy, hogy mögé szúrunk be" trükkel valósítjuk meg. A láncon már csak a bemeneti feltételnek megfelelô adatokat tároljuk.

      -> azonosító -> azonosító -> azonosító ->  ... azonosító

program feladat_5;
type azon_t = packed array [1..13] of char; { azonosító típus }
     lanc_poi = ^lanc;
     lanc = record                   { lánc elem a hívó összesített adataihoz }
       hivo: azon_t;                 { hívo azonosító }
       szla: array [1..12] of real;  { hónapok gyûjtõi }
       kov:  lanc_poi                { következõ elem mutatója }
     end;
     inp = record                    { beolvasás rekordja }
       hivo: azon_t;                 { azonositó }
       dij:  real;                   { hívás díja }
       kod:  char;                   { kód }
       ev:   integer;                { év }
       ho:   integer;                { hó }
     end;
var kezdo:  lanc_poi;                { kezdõ pointer }
    be:     text;                    { file változó }
    adat:   inp;                     { rekord a beolvasához }

{ lancol:
  Hívó azonositó szerint épít egy láncot. A lánc végén van a strázsa.
  A díjakat a megfelelõ hónaphoz akkumulálja.
  Bemenet: pointer a láncra,
           beolasott adatok
  Kimenet: epül a lánc
}
procedure lancol(p: lanc_poi; r: inp);
var i: integer;
    uj: lanc_poi;
begin
    while (p^.kov <> nil) and (p^.hivo < r.hivo) do p:= p^.kov; { keres }
    if (p^.kov = nil) or (p^.hivo <> r.hivo) then begin
      new(uj);                         { új elemet veszünk fel }
      uj^:= p^;
      p^.kov:= uj;
      for i:= 1 to 12 do p^.szla[i]:= 0.0;   { nullázzzuk gyûjtõket }
      p^.hivo:= r.hivo;                { beírjuk a hívo azonosítoját }
    end;
    p^.szla[r.ho]:= p^.szla[r.ho] + r.dij;   { akkumuláljuk a számlát }
end;

{ beolvas:
  Beolvassa a bemeneti formátumnak megfelelõ állományból az inp rekord
  adatait.
  Bemenet: megnyitott file
           inp típusú rekord
  Kimenet: beolvasott adatok a paraméterként adott rekordban
}
procedure beolvas(var f: text; var r: inp);
var ch: char;
    i: integer;

{ deci:
  Integerré alakít egy karaktersorozatot. Végjel minden ami nem szám.
  Bemenet: megnyitott file
  Kimenet: függveny értek
}
function deci(var f: text): integer;
var ch: char;
    n: integer;
begin
    n:= 0;                          { kezedtben nulla }
    read(f, ch);                    { következõ karakter }
    while ch in ['0'..'9'] do begin  { amíg decimális számjegy }
      n:= n * 10 + ord(ch) - ord('0'); { vesszük a következõ együtthatót }
      read(f, ch);                  { következõ karakter }
    end;
    deci:= n;                       { végeredmény }
end;

begin
    for i:= 1 to 15 do read(f, r.hivo[i]);{ hivó azonositó }
    for i:= 1 to 15+2 do read(f, ch);     { ez nem kell, eldobjuk }
    read(f, r.kod, r.dij, ch);            { jöhet a kód, es a díj }
    r.ev:= deci(f);                       { év }
    r.ho:= deci(f);                       { hó }
    readln(f);                            { sorvégéig eldobjuk }
end;

{ kiir:
  Kiírja a felépített láncot. Közben kiszámolja az éves díjat is.
}
procedure kiir(p: lanc_poi);
var sum: real;
    i: integer;
begin
    while (p^.kov <> nil) do begin    { amíg a strázsát el nem érjük }
      write(p^.hivo:20);              { ez a hívó azonosítója }
      sum:= 0.0;                      { ez lesz az összesítõ }
      for i:= 1 to 12 do begin        { mind a 12 hónapra }
        sum:= sum + p^.szla[i];       { összesitunk }
        write(p^.szla[i]:8:1);        { kiírjuk }
      end;
      writeln(sum:8:1);               { összeg, soremelés }
      p:= p^.kov;                     { kövekezõ elemre }
    end;
end;

begin
  new(kezdo); kezdo^.kov:= nil;       { strázsa }
  assign(be, 'HIVAS.TXT');            { file }
  reset(be);
  while not eof(be) do begin          { a file végéig }
    beolvas(be, adat);                { beolvasunk }
    if (adat.kod = 'H') and (adat.ev = 1999) then { ha megfelel, láncol }
      lancol(kezdo, adat);
  end;
  kiir(kezdo);                        { kiír }
end.



6. feladat
Az egyes számjegyek között a feladat szerint vagy nem áll semmi, vagy a négy mûveleti jelek egyike. Jelöljük a mûveleti jeleket a megfelelõ karakterrel, és a semmi mûveletet pedig a szóközzel! Ekkor pl az: 1 2+3*4 kifejezés megfelel a 12+3*4 kifejezésnek. Ezzel a jelöléssel könnyen elõállítható a számejegyek és a mûveleti jelek segítségével kialakítható összes kifejezés, hiszen csupán a számjegyek közé tehetõ 5 mûveleti jel permutációját kell elõállítni. A feladat megoldásához elõállítjuk a fenti kifejezéseket és mindegyiket kiértékeljük egy olyan kiértékelõ segítségével amely a számjegyek közötti szóközt figyelmen kívül hagyja. Ha a kifejezés értéke  megfelel a kívánt 1999-es értéknek, akkor az elõállított kifejezést kiírjuk. Megjegyezzük, hogy így több, formailag azonos megoldást is ki fogunk írni, de ezt a feladat nem korlátozta.

program feladat6;
const DIGMAX = 10;        { digitek száma }
      EREDMENY = 1999;    { ezt kell elõállítani }
type str_t = array [1..2*DIGMAX-1] of char; { kifejezés típusa }
     val_t = longint;     { érték típusa azért longint, hogy ki tudjuk probálni }

var v: str_t;             { itt állitjuk elõ a kifejezest }

{ kiertekel:
  Kiertekeli a kifejezest
  Bemenet: s - kifejezes
  kimenet: kifejezes erteke (fuggveny ertek)
           ok - true, ha a kifejezes ervenyes (nem volt nullaval osztas)
}
function kiertekel(s: str_t; var ok: boolean): val_t;
var muv: char;             { mûveleti jel }
    i: integer;            { index }
    res, op2: val_t;       { eredmeny, es op2 }

{ szam:
  Decimalis szamot alak1ít át karakteres fomábol.
  Bemenet: s - számot tartalmazó karaktertömb
           p - szám elsõ jegyenek indexe
  Kimenet: szám értéke (függvényérték)
           p - a szam végét jelentõ nem decimális számjegy karakter
}
function szam(s: str_t; var p:integer): val_t;
var r: val_t;
begin
    r:= 0;
    while (p <= 2*DIGMAX-1) and (s[p] in ['0'..'9',' ']) do begin
      if s[p] <> ' ' then
        r:= r * 10 + ord(s[p]) - ord('0');
      p:= p + 1;
    end;
    szam:= r;
end;

begin
    i:= 1;                    { elsõ indextól }
    ok:= true;                { eddig meg jó }
    res:= szam(s, i);         { elsõ szám }
    while i < 2*DIGMAX-1 do begin  { amíg el nem érjük a kifejezés végét }
      muv:= s[i];             { mûvelet }
      i:= i + 1;              { itt kezdõdik a kov. szám }
      case muv of             { elvegezzük a mûveletet }
        '+': res:= res + szam(s, i);
        '-': res:= res - szam(s, i);
        '*': res:= res * szam(s, i);
        '%': begin            { az osztásnál bajok lehetnek }
               op2:= szam(s, i);
               if op2 <> 0 then res:= res mod op2
               else ok:= false; { nullával osztunk ! }
             end
      end;
    end;
    kiertekel:= res;          { végeredmény }
end;

{ novel:
  Veszi a következõ mûvelei jelet (' ',+,-,*,%)
}
function novel(ch: char): char;
begin
    case ch of
      ' ': novel:= '+';
      '+': novel:= '-';
      '-': novel:= '*';
      '*': novel:= '%';
      '%': novel:= ' '
    end;
end;

{ kiir:
  Kiírja a kifejezést
}
procedure kiir(v: str_t);
var i: integer;
begin
    for i:= 1 to 2*DIGMAX-1 do
      if v[i] <> ' ' then write(v[i]);
    writeln(' = ', EREDMENY);
end;

{ beolvas:
  Beolvasás a teszteléshez
}
procedure beolvas(var v: str_t);
var i: integer;
begin
    writeln('Kerek ', DIGMAX, ' szamjegyet!');
    for i:= 1 to 2*DIGMAX-1 do
      if odd(i) then read(v[i]) else v[i]:= ' ';
end;

{ probal:
  Rekurziv rutin, ami a mûveleti jelek permutációjának
  elõáll1tásával megpróbálja kihozni a kívánt eredmenyt.
  Bemenet: p - hanyadik pozicióra probálunk
}
procedure probal(p: integer);
var ok: boolean;
begin
    repeat
      if kiertekel(v, ok) = EREDMENY then
        if ok then kiir(v);    { van egy eredmény, kiírjuk }
      v[p]:= novel(v[p]);     { vesszük a következõ muveleti jelet }
      if (p < 2*DIGMAX-2) then { ha még nem ért a végére, }
        probal(p+2);          { megprobálja a következõ helyen }
    until v[p] = ' ';         { amíg újra el nem jutunk a szóközig }
end;

begin
    beolvas(v);
    probal(2);
end.


Szeberényi Imre
© BME Irányítástechnika és Informatika Tanszék
Utolsó módosítás: 1999.12.07.