Programozási tételek listákra

„Globális” feladat – körülmények, célok

Emlékeztetőül idézzük föl a lista fogalmát a csatolt prezentáció 3-13. diái alapján!
Építsünk föl nevekből listákat! (TLista=Lista(Szöveg))
Ezekre fogalmazzunk meg tételeken alapuló konkrét feladatokat! Majd algoritmizáljuk, és kódoljuk Pascalban őket!

Ilyen feladatokra gondolhat (remélem, Önnek merészebb a fantáziája):

1. Van-e olyan személy, akinek a neve hosszabb, mint 15 jel?
2. Ki az utolsó névsorszerint?
3. Válogassuk ki a „Péter” keresztnevűeket!

A megoldáshoz

A lényeg – tételek alprogramjainak algoritmusai

Készítse el a programozási tételek listás változatainak függvényeit!
Az alábbi tételeket (az itt szereplő szignatúrával) vegye számításba:

1. Eldöntés(l:TLista,t:TTulFv):Logikai
2. Keresés(l:TLista,t:TTulFv):TKeresett,
   ahol TKeresett=Rekord(vanE:Logikai,melyik:TElem)
3. Megszámolás(l:TLista,t:TTulFv)
4. MaximumKiválasztás(l:TLista,r:TRendFv):TLeg,
   ahol TLeg=Rekord(legelem:TElem; sorsz:Egész)
5. Kiválogatás(l:TLista,t:TTulFv):TLista
6. Egyesítés(l1,l2:TLista):TLista
7. Beillesztéses rendezés(l:TLista):TLista
   a beillesztéses rendezés elvét követve az l listából az eredmény listába rendezni
8. Összefuttatás(l1,l2:TLista):TLista

Mindenekelőtt gondolja meg, mik a listák típus-specifikus műveletei, specialitásai!
A listák mely specialitásai miatt kell újra gondolni a programozási tételek tömbökre alapozott algoritmusait?
Súgás...
1) nem állandó a listák elemszáma (akár 0 is lehet);
2) nem indexelhető, hanem csak az ún. aktuális elemmel lehet manipulálni; az aktuális elem kijelölése csak szekvenciálisan lehetséges;
3) a feldolgozás az utolsó elemig tarthat (ellenkező esetben hiba következik be), viszont az aktuális elem „utolsósága” lekérdezhető.

„Transzformálja” a tételek jól ismert algoritmusait, írja le a listás algoritmusokat!
Próbáljon átírási szabályt adni: Algoritmus_tömb→Algoritmus_lista!
Kiinduló pont lehet a tételek algoritmusaihoz...
Az előadás anyaga.

Ne feledje a legutóbbi gyakorlaton tanultakat se, külösen a függvény-típusról hallottakat! (Segítségül olvassa újra a dokumentum 11., 16. diáit!)
Örülnék, ha látnám az alábbiakat a programban:

Tipikus függvény-kellékek a tételekben – függvények paraméterként

A két, tételekben gyakorta előforduló 1- (Tulajdonság-függvény), ill. 2-változós (Rendezés) függvény „oszálya”, típusa:

  Típus
    TTulFv=Függvény(Konstans x:TElem):Logikai
    TRendFv=Függvény(Konstans x,y:TElem):Logikai
  ...
  [Konkrét tul-függvények TElem=Szöveg esetén:]
  Függvény Hosszabb15(Konstans x:TElem):Logikai
    ... [x hosszabb-e, mint 15 karakter]
  Függvény PéterE(Konstans x:TElem):Logikai
    ... [x-ben van-e "Péter"]
  [Tételek:]
  Függvény Eldöntés(Változó l:TLista,
                    Konstans t:TTulFv):Logikai
    [Eldöntés(l,t)=l-ben van-e t tulajdonságú elem]
  ...
  Változó
    t:TTulFv
    l:TLista
  ...
  t:=Hosszabb15; vanE:=Eldöntés(l,t)
  ...
  vanE:=Eldöntés(l,PéterE)

  Type
    TTulFv=Function(Const x:TElem):Boolean;
    TRendFv=Function(Const x,y:TElem):Boolean;
  ...
  {Konkrét tul-függvények TElem=String esetén:}
  Function Hosszabb15(Const x:TElem):Boolean;
    ... {x hosszabb-e, mint 15 karakter}
  Function PeterE(Const x:TElem):Boolean;
    ... {x-ben van-e "Peter"}
  [Tételek:]
  Function Eldontes(Var l:TLista,
                    Const t:TTulFv):Boolean
    {Eldontes(l,t)=l-ben van-e t tulajdonságú elem}
  ...
  Var
    t:TTulFv;
    l:TLista;
  ...
  t:=@Hosszabb15; vanE:=Eldontes(l,t);
  ...
  vanE:=Eldontes(l,@PeterE);

Kérdés: vajon miért „változik” az l lista az eldöntés tétel egyik bemenő paramétere?

1. Feladat

1. Algoritmizálja az eldöntés tételt a hagyományos tömbös módon, és tegye mellé a listás változatot!
   Ragaszkodjon a tételek szokásos előfeltételeihez, még abban az esetben is, ha az előadás él a „legalább 1 elemből áll” előfeltétellel!
2. Végezze el ugyanezt még legalább 2 tétellel a fent felsoroltak közül!
3. Fogalmazza meg az átírási szabályokat: Algoritmus_tömb→Algoritmus_lista!
4. Ha eddig nem tette volna, tegye az adott tételben –esetleg– szerepet kapó függvényt (relációt) is az alprogramok paraméterévé!

Kezdő lépések a kódoláshoz

A kódoláshoz rendelkezésre áll egy kész TElem (=String) lista-unit: Lista_Str_Unit.pas.
Exportált fogalmak (részlet):

• Type TElem=String – a lista elemtípusa
• Type TLista=... – a lista maga
• Procedure Ures(Var l:TLista)
• Function UresE(Const l:TLista):Boolean
• ...

A listás tételek algoritmusainak kipróbáláshoz felhasználhat egy listafeltöltést támogató unitot: Lista_Gen_Unit.pas.
Ebben három műveletet implementáltam könnyen kitalálható funkcióval:

1. Function ListaGeneralas(Const db:Integer):TLista
2. Procedure WriteListaAllapot(Const l:TLista; Const cim:String)
3. Procedure WriteLista(Const l:TLista; Const cim:String)

A unit épít a Randnev.inc inklúd-állományra, amelyben olyan rutinok vannak, melyekkel generálhatók pl. „véletlen” nevek, címek, telefonszámok.
A leglényegesebb exportált fogalmai:

• Const M=19
• Type TNev=String[M]
• Function RandomNev:TNev
• Function RandomCim:TNev
• Function RandomTel:TNev

2. Feladat

Mindenekelőtt ennek kipróblására írjon egy nyúlfarknyi programot (ListaProba.pas)!
E program célja kettős: 1) a Lista_Str_Unit helyességének ellenőrzése; 2) a Lista_Gen_Unit kipróbálása.
Az 1) feladatához célszerű kiindulni a fenti prezentációban szereplő axiómákból felhasználva a Lista_Gen_Unit-beli WriteListaAllapot eljárást.
Kiinduló pont lehet...
Lássa az én kezdeményemet: ListaProba.pas!

3. Feladat

Készítsen néhány tulajdonság-függvényt, amelyeket a tételek listás alprogramjait kipróbáló programban majd felhasznál!

• Function Hosszabb15(Const x:TElem):Boolean – x jeleinek száma több-e, mint 15
• Function PeterE(Const x:TElem):Boolean – x-ben van-e " Péter" szöveg

4. Feladat – „A Feladat”

Készítsen programot, amely az Ön által megfogalmazott feladatokat megoldja!

• Építsen a lista-generátorra! (Esetleg átalakíthatja, hogy ne (csak) neveket állítson elő.)
• Az egyes tételeket Pascal függvényként implementálja a programjában!

A legfontosabb kellékeket (köztük egy futásra kész program-mintát) egyben letöltheti: ListaUnitAlap.zip.
Figyelem: a Lista_Str_Unit.pas unit hivatkozik a Masolat.inc inklúdfájlra, amely ekészítése házi feladat!
A lefordíthatóság érdekében késítsen egy üres Masolat.inc nevű fájlt!