Zárthelyi feladatok és megoldások

Programozás c. tárgyból


Programozás zárthelyi I.INF.                         1999.11.25/B 

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:= [vidor];
        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):5);
          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ó végzõ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 100 elemû valós tömb elemei olyan kupacot alkotnak-e, amelyben a nagyobb 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..100] OF REAL;
FUNCTION KUPACE_E(N: INTEGER; A: VEC_T): BOOLEAN;


4. feladat                                                  10p
Készítsen PASCAL eljárást, amely a paraméterként kapott két, maximum 198 karakter hosszú 5-ös számrendszerbeli pozitív egész számot (S1, S2) kivonja (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õ! Feltételezheti, hogy S1 >= S2;
TYPE SZAM_T = ARRAY [1..200] OF CHAR;
PROCEDURE KIVON(S1, S2: SZAM_T; VAR E: SZAN_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:    15 karakter
hívott fél azonosítója:  15 karakter
a hívás kódja:            1 karakter (H: hivatalos, M: magán)
beszélgetés díja:        maximum 10 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 kezdõdik. Írjon Pascal programot, amely a HIVAS.TXT állományt feldolgozva, a hívó fél azonosítója szerint csökkenõ sorrendben, azon belül hónaponkénti bontásban kiírja az 1998-ban kezdeményezett magán (M) 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 3000! A megengedett mûveleti jelek összeadás (+), kivonás (-), szorzás (*), egészrész képzése (/). Tételezze fel, hogy a mûveleti jelek azonos precedenciájúak.
 
 


Megoldások I.INF.                          1999.11.25/B 

1. feladat
A banya halmaz tipusú változó kezeti értéke vidor, a torpe váltózóé pedig hapci, amit a while ciklusban a banya halmazból midig kivonunk, amig a halmaz ki nem ürül. Így a ciklus 3-szor fut le, és közben kialakít egy láncot. A lánc 4 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) iró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, mivel az utolsó elem pointere az elsõre (p1) mutat. A második wilr ciklus ezen a gyûrûn megy körbe, amig valamelyik elem torpe mezõje el nem éri a morgo értéket. Minden lépésben a cilus 5 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û negyedik 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
    1    2    3    4
    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;
if vizsgal(mintak, ablak) then sz:= sz + 1;
writeln(sz);
A file végén újból kell vizsgálnunk, az esetleges file végi szó miatt. (a szó mögött azonnal végetér  a file)
(Az alporgramok specifikációit megjegyzésekkel adtuk meg a programban.)

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 (programn 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 else
      a[ABLAK_H]:= ' ';           { eof volt }
end;

{ vizsgal spec:
  A parameterként kapott minták tömböt összehasonlítja az ablakkal.
  Bemenet: minták tömb,
           ablak,
           mintak 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 { amig 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 }
    if vizsgal(mintak, ablak) then sz:= sz+1;  { file végén levõ szó miatt }
    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 levelemek automatikusan kupacot alkotnak.

function kupac_e(n: integer; a:vec_t): 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 kisebb, 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 karatketesesen 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.

procedure kivon(s1, s2: szam_t; VAR e: szam_t);
const RADIX = 5;                      { számrendszer }
var n1, n2,                           { két szám hossza }
    i1, i2,                           { indexváltozók }
    b: integer;                       { alulcsordulás }
    c: char;                          { segédváltozó }

{ hossz:
  Megállapítja a szám hosszát.
  Bemenet: szám
  Kimenet: hossz (függvény érték)
}
function hossz(s: szam_t): integer;
var i: integer;
begin
    i:= 1;                            { cilusváltozó }
    while s[i] <> ' ' do i:= i + 1;     { megkeresi a a szóközt }
    hossz:= i-1;
end;

{ cvon:
  Kivon két RADIX számrendszerû karakert, kezeli az alulcsordulást
  Bemenet: a két karakter
           elõzõ digitrõl az alulcsordulas
  Kimenet: eredmény karakter (függveny érték)
           alulcsordulás
}
function cvon(c1, c2: char; var b: integer): char;
var r: integer;
begin
    r:= ord(c1) - ord(c2) - b;          { ez az int eredmény }
    if (r < 0) then begin             { alulcsordult ? }
      r:= r + RADIX;                  { kiszámítjuk az uj értéket }
      b:= 1;                          { jelezzük az alulcsordulást }
    end else
      b:= 0;                          { nincs alulcsordulás }
    cvon:= chr(r+ord('0'));           { eredmény karakteresen }
end;

begin
    n1:= hossz(s1); n2:= hossz(s2);   { megvan a két hossz }
    b:= 0;                            { kezdetben nincs alulcsordulás }
    i2:= n2;                          { 2. szám indexe }
    for i1:= n1 downto 1 do begin       { elsõ hosszab, vagy egyenlõ }
      if i2 >= 1 then c:= s2[i2]        { vesszük a következõ karatert }
      else c:= '0'; i2:= i2 - 1;        { ha elfogyna a másik, akkor 0 }
      e[i1]:= cvon(s1[i1], c, b);       { kivonás karakterenként }
    end;
    e[n1+1]:= ' ';                    { lazáró szokoz }
    i1:= 1;                           { van az elejen 0 ? }
    while (e[i1] = '0') and (i1 < n1) do i1:= i1 + 1;
    for i2:= i1 to n1+1 do e[i2-i1+1]:= e[i2]; { 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 stárzsa 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 feltetelnek megfelelô adatokat tároljuk.

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

program feladat_5;
type azon_t = packed array [1..15] of char; { azonosító típus }
type lanc_poi = ^lanc;
     lanc = record                     { lánc elem a hívó összsí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 starzsa.
  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 rekordnak
  megfelelõ adatokat.
  Bemenet: megnyitott file
           inp típusú rekord
  Kimenet: beolvasott adatok a parameterként adott rekordban
}
procedure beolvas(var f: text; var r: inp);
var ch: char;
    i: integer;

{ deci:
  Integerré alakít egy karaktersorzatot. 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 kovetkezõ 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 érjuk }
      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 = 'M') and (adat.ev = 1998) then { ha megfelell, 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 megfelell a 12+3*4 kifejezésnek. Ezzel a jelöléssel könnyen elõállítható számájegyek é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õt 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 3000-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 = 3000;     { ezt kell eloá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;              { muveleti jel }
    i: integer;             { index }
    res, op2: val_t;        { eredmeny, es op2 }

{ szam:
  Decimalis szamot alakit at karakteres fomabol.
  Bemenet: s - szamot tartalkmazo karaktertomb
           p - szam elso jegyenek indexe
  Kimenet: szam erteke (fuggveny ertek)
           p - a szam veget jelento nem decimalis szamjegy 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;                     { elso indextol }
    ok:= true;                 { eddig meg jo }
    res:= szam(s, i);          { elso szam }
    while i < 2*DIGMAX-1 do begin  { amig el nem erjuk a kifejezes veget }
      muv:= s[i];              { muvelet }
      i:= i + 1;               { itt kezdodik a kov. szam }
      case muv of              { elvegezzuk a muveletet }
'+': res:= res + szam(s, i);
'-': res:= res - szam(s, i);
'*': res:= res * szam(s, i);
'/': begin             { az osztasnal bajok lehetnek }
               op2:= szam(s, i);
               if op2 <> 0 then res:= res div op2
               else ok:= false; { nullaval osztunk ! }
             end
      end;
    end;
    kiertekel:= res;           { vegeredmeny }
end;

{ novel:
  Veszi a kovetkezo muveleit jelet (' ',+,-,*,/)
}
function novel(ch: char): char;
begin
    case ch of
      ' ': novel:= '+';
      '+': novel:= '-';
      '-': novel:= '*';
      '*': novel:= '/';
      '/': novel:= ' '
    end;
end;

{ kiir:
  Kiirja a kifejezest
}
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:
  Beolvasas a teszteleshez
}
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 muveleti jelek es a szamjegyek permutaciojanak
  eloallitasaval megprobalja kihozni a kivant eredmenyt.
  Bemenet: p - hanyadik poziciora probalunk
}
procedure probal(p: integer);
var ok: boolean;
begin
    repeat
      if kiertekel(v, ok) = EREDMENY then
        if ok then kiir(v);    { van egy eredmeny, kiirjuk }
      v[p]:= novel(v[p]);      { vesszuk a kovetkezo muveleit jelet }
      if (p < 2*DIGMAX-2) then { ha meg nem ert a vegere, }
        probal(p+2);           { megprobalja a kovetkezo helyen }
    until v[p] = ' ';          { amig ujra el nem jutiunk a szokozig }
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.