8. Programozási tételek felsoroló típusokra

8.

Programozási tételek felsoroló típusokra

Ha egy adatot elemi értékek csoportja reprezentál, akkor az adat feldolgozása ezen értékek feldolgozásából áll. Az ilyen adat típusának lényeges jellemzője, hogy az őt reprezentáló elemi értékeknek mi az egymáshoz való viszonya, a reprezentáció milyen jellegzetes belső szerkezettel rendelkezik. Számunkra különösen azok a típusok érdekesek, amelyek típusértékeit azonos típusú elemi értékek sokasága reprezentál. Ilyen például egy tömb, egy halmaz vagy egy sorozat. Ezeknek az úgynevezett gyűjteményeknek közös tulajdonsága, hogy a bennük tárolt elemi értékek egymás után felsorolhatók. Egy halmazból egymás után kivehetjük, egy sorozatnak vagy egy tömbnek végignézhetjük az elemeit. Éppen ezért az ilyen típusokat szokták felsorolhatónak (enumerable) vagy iteráltnak (iterált szerkezetűnek) nevezni. Felsorolni nemcsak iterált szerkezetű adatok elemeit lehet, hanem egy egész szám valódi osztóit, vagy két egész szám által meghatározott zárt intervallum egész számait. Ebből is látszik, hogy nagyon sokféle felsorolható adat van. A felsorolás tehát nem csak a felsorolhatósághoz kötődik. Általánosságban azt jelenti, hogy képesek vagyunk egy adatnak valamilyen értelemben vett első elemére ráállni, majd a soron következőre, meg tudjuk kérdezni, van-e egyáltalán első vagy soron következő elem, és lekérdezhetjük a felsorolás során éppen aktuális elemnek az értékét. A felsorolást végző műveletek nem ahhoz az adathoz tartoznak, amelynek elemeit felsoroljuk, legfeljebb csak támaszkodnak az adat műveleteire. Furcsa is lenne, ha egy egész szám (amelyiknek valódi osztóira vagyunk kíváncsiak) alapból rendelkezne ilyen („vedd az első valódi osztót”, „vedd a következő valódi osztót”, „van-e még valódi osztó”, „mi az éppen vizsgált valódi osztó”) műveletekkel. De egy egész intervallumnak is csak olyan műveletei vannak, amivel az intervallum határait tudjuk lekérdezni, az intervallum egész számainak felsorolásához már egy speciális objektumra, egy indexre van szükség. Ráadásul egy intervallum felsorolása többféle lehet (egyesével vagy kettesével; növekvő, esetleg csökkenő sorrendben), ezeket mind nem lehetne az intervallum típusműveleteivel leírni. A felsorolást végző műveleteket ezért mindig egy külön objektumhoz kötjük. Ha szükség van egy adat elemi érékeinek felsorolásra, akkor az adathoz hozzárendelünk egy ilyen felsoroló objektumot. Egy felsoroló objektum feldolgozása azt jelenti, hogy az általa felsorolt elemi értékeket valamilyen tevékenységnek vetjük alá. Ilyen tevékenység lehet ezen értékek összegzése, adott tulajdonságú értékek megszámolása vagy a legnagyobb elemi érték megkeresése, stb. Ezek ugyanolyan feladatok, amelyek megoldására korábban programozási tételeket vezettünk be, csakhogy azokat a tételeket intervallumon értelmezett függvényekre fogalmaztuk meg, most viszont ennél általánosabb, felsorolóra kimondott változatukra lenne szükség. Ezt az általánosítást azonban könnyű megtenni, hiszen egy intervallumhoz nem nehéz felsorolót rendelni, így a korábban bevezetett intervallumos tételeket egyszerűen átfogalmazhatjuk felsoroló objektumra. Először (8.1. alfejezet) a nevezetes típusszerkezeteket fogjuk megvizsgálni, de ezek között is a legnagyobb hangsúlyt az iterált szerkezetű, tehát felsorolható típusok bemutatására helyezzük. A 8.2. alfejezetben a felsoroló típus műveleteit fogjuk jellemezni, majd megadjuk egy felsoroló objektum általános feldolgozását végző algoritmus-sémát. A 8.3. alfejezetben

107

8. Programozási tételek felsoroló típusokra

nevezetes felsoroló típusokat mutatunk. A 8.4. alfejezetben a programozási tételeinket mondjuk ki felsoroló típusokra. 8.1.

Gyűjtemények

A programozási feladatok megoldásában leggyakrabban gyűjtemények elemi értékeit kell felsorolni és feldolgozni. Gyűjteményeknek azokat az iterált szerkezetű adatokat tekintjük, amelyek típusértékeit azonos típusú elemi értékek sokasága reprezentál. Vizsgáljunk meg most néhány nevezetes gyűjteményt. A halmaz (szerkezetű) típus típusértékeit egy-egy véges elemszámú 2E-beli elem (E-beli elemekből képzett halmaz) reprezentálja. Egy halmaz típusú objektumnak a típusműveletei a halmazok szokásos műveletei lesznek. Értelmezzük: halmaz ürességének vizsgálatát (h=, ahol h egy halmaz típusú értéket jelöl), halmaz egy elemének kiválasztását (e:h, ahol e egy elemi értéket hordozó segédváltozó), halmazból egy elem kivonását (h:=h–{e}), új elemnek a hozzáadását a halmazhoz (h:=h{e}). A típus-megvalósítás szempontjából egyáltalán nem közömbös, hogy itt a szokásos unió illetve kivonás műveletével van-e dolgunk, vagy a megkülönböztetett (diszjunkt) unió illetve megkülönböztetett kivonással. Ez utóbbiak esetén feltételezzük, hogy a művelet megváltoztatja a halmazt, azaz unió esetén bővül (mert a hozzáadandó elem új, még nincs benne a halmazban), kivonás esetén fogy (mert a kivonandó elem benne van a halmazban). Ezeknek a műveleteknek az implementálása egyszerűbb, mert nem kell ezen feltételeket külön ellenőrizniük, igaz, a feltétel nem teljesülése estén abortálnak. A halmaz típust a set(E) jelöli. Látjuk, hogy egy halmaz egy elemének kiválasztása (e:h) a nem-determinisztikus értékkiválasztással történik, amit ugyanazon halmazra egymás után alkalmazva nem fogjuk ugyanazt az elemet megkapni. Be lehet vezetni azonban a determinisztikus elemkiválasztás műveletét (e:=mem(h)), amelyet ha egy halmazra többször egymás után hajtjuk végre úgy, hogy közben a halmazt nem változtatjuk meg, akkor mindig ugyanazon elemét adja vissza a halmaznak. Az igazat megvallva, a halmaz szóba jöhető reprezentációi sokkal inkább támogatják ennek az elemkiválasztásnak a megvalósítását, mint a valóban véletlenszerű, nemdeterminisztikus értékkiválasztást. A sorozat (szerkezetű) típus típusértékeit egy-egy véges hosszú E*-beli elem (E-beli elemekből képzett sorozat) reprezentálja, típusműveletei pedig a sorozatokon értelmezhető műveletek. Jelöljön a t egy sorozat típusú objektumot, amelyet egy sorozat reprezentál. Most a teljesség igénye nélkül felsorolunk néhány típusműveletet, amelyeket a t-re szoktak bevezetni, és a t-t reprezentáló sorozaton értelmezhetőek. Ilyen egy sorozat hosszának lekérdezése (|t|), a sorozat valahányadik elemére indexeléssel történő hivatkozás (ti ahol az i indexnek 1 és a sorozat hossza közé kell esni), egy elem törlése egy sorozatból vagy egy új elem beszúrása. Magát a sorozat típust a seq(E) jelöli. Speciális sorozattípusokhoz jutunk, ha csak bizonyos típusműveleteket engedünk meg. Ilyen például a verem és a sor. A verem esetén csak a sorozat elejére szabad új elemet befűzni, a sornál pedig csak a sorozat végére. Mindkettő esetén megengedett művelet annak eldöntése, hogy a reprezentáló sorozat üres-e. Mindkettőnél ki lehet olvasni a sorozat első elemét, és azt el is lehet hagyni a sorozatból. A szekvenciális outputfájl (jelölése: outfile(E)) egyetlen műveletet enged meg: a sorozat végéhez új elem vagy elemekből képzett sorozat hozzáillesztését (jelölése: write(e) vagy write(<e1, … ,en>)). A szekvenciális inputfájlnak (jelölése: infile(E)) is egyetlen művelete van: a sorozat első elemének lefűzése, más szóval az

108

8.1. Gyűjtemények

olvasás művelete. Matematikai értelemben ezt egy olyan függvénnyel írhatjuk le, amely egy sorozat típusú objektumhoz (pontosabban az őt reprezentáló sorozathoz) három értéket rendel: az olvasás státuszát, a sorozat első elemét (ha van ilyen), és az első elemétől megfosztott sorozatot. Az olvasást az st,e,t:=read(t) értékadással, vagy rövidítve az st,e,t:read szimbólummal jelöljük. Itt az st az olvasás státuszát kapja. Ez egy speciális kételemű halmaznak (Státusz ={abnorm, norm}) az egyik eleme. Ha a t eredeti értéke egy üres sorozat volt, akkor az st változó az abnorm értéket veszi fel, különben a norm-ot. Ha a t-beli eredeti sorozat nem üres, akkor az e az eredeti sorozat első elemét, a t az eggyel rövidebb sorozatot veszi fel, egyébként a t-beli sorozat továbbra is üres marad, az e pedig definiálatlan. Sorozat szerkezetűnek tekinthetjük a vektor típust, vagy más néven egydimenziós tömböt. Ha eltekintünk egy pillanatra attól, hogy a vektorok tetszőlegesen indexelhetőek, akkor a vektort egy olyan sorozatnak tekinthetjük, amelynek az elemeire a sorszámuk alapján lehet közvetlenül hivatkozni, de a sorozat hossza (törléssel vagy beszúrással) nem változtatható meg. Egy vektor típusához azonban a fent vázolt sorozaton kívül azt az indextartományt is meg kell adni, amely alapján a vektor elemeit indexelhetjük. A vektor típus tehát valójában egy rögzített hosszúságú sorozatból és egy egész számból álló rekord, amelyben a sorozat tartalmazza a vektor elemeit, az egész szám pedig a sorozat első elemének indexét adja meg. A vektor típust a vec(E) jelöli. A vektor alsó és felső indexének lekérdezése is éppen úgy típusműveletnek tekinthető, mint a vektor adott indexű elemére való hivatkozás. Ha v egy vektor, i pedig egy indexe, akkor v[i] a vektor i indexű eleme, amit lekérdezhetünk vagy megváltoztathatunk, azaz állhat értékadás jobb vagy baloldalán. Általánosan a v vektor indextartományának elejét a v.lob, végét a v.hib kifejezések adják meg. Ha azonban a vektor típusra az általános vec(E) jelölés helyett továbbra is a korábban bevezetett E m..n jelölést alkalmazzuk, akkor az indextartományra egyszerűen az m és n segítségével hivatkozhatunk. Világosan kell azonban látni, hogy itt az m és az n a vektor egyedi tulajdonságai, és nem attól független adatok. A kétdimenziós tömbtípus, azaz a mátrix típus modellünkben vektorok vektoraként fogalmazható meg könnyen. Ennek megfelelően a t mátrix i-edik sorának j-edik elemére a t[i][j] hivatkozik (ezt rövidebben t[i,j]-vel is jelölhetjük), az i-edik sorra a t[i], az első sor indexére a t.lob, az utolsóéra a t.hib, az i-edik sor első elemének indexére a t[i].lob, az utolsó elem indexére a t[i].hib. A mátrix típust a matrix(E) jelöli. (Ezek a műveletek általánosítható a kettőnél több dimenziós tömbtípusokra is.) Speciális, de a leggyakrabban alkalmazott mátrix az, amelynek sorai egyforma hosszúak és ugyanazzal az indextartománnyal indexeltek. Ezt jelöli az E l ..nk ..m , ahol a sorokat az [l..n] intervallum, egy sor elemeit pedig a [k..m] intervallum indexeli. Ha k=1 és l=1, akkor az E nm jelölést is használjuk és ilyenkor n*m-es mátrixokról (sorok száma n, oszlopok száma m) beszélünk. Könyvünkben megengedettnek tekintjük mindazokat a típusokat, amelyeket megengedett típusokból az itt bemutatott típusszerkezetek segítségével készíthetünk.

109


8.2.

Felsoroló típus specifikációja

Most általánosan jellemezzük az olyan objektumokat (ezeket hívjuk majd röviden felsorolónak), amelyek segítségével egy felsorolható adatnak (vektornak, halmaznak, szekvenciális inputfájlnak, valódi osztóit felkínáló természetes számnak) az elemeit egymás után elő lehet állítani. Egy felsoroló objektum1 (enumerator) véges sok elemi érték felsorolását teszi lehetővé azáltal, hogy rendelkezik a felsorolást végző műveletekkel: rá tud állni a felsorolandó értékek közül az elsőre vagy a soron következőre, meg tudja mutatni, hogy tart-e még a felsorolás és vissza tudja adni a felsorolás során érintett aktuális értéket. Ha egy típus ezeket a műveleteket biztosítja, azaz felsoroló definiálására képes, akkor azt felsoroló (enumerator) típusnak nevezzük. Egy t felsoroló típusú objektumra definíció szerint négy műveletet vezetünk be. A felsorolást mindig azzal kezdjük, hogy a felsorolót a felsorolás során először érintett elemi értékre – feltéve, hogy van ilyen – állítjuk. Ezt általánosan a t:=First(t) értékadás valósítja meg, amit a továbbiakban t.First()2-tel jelölünk. Minden további, tehát soron következő elemre a t.Next() művelet (amely a t:=Next(t) rövidített jelölése) segítségével tudunk ráállni. Vegyük észre, hogy mindkettő művelet megváltoztatja a t felsoroló állapotát. A t.Current() művelet a felsorolás alatt kijelölt aktuális elem értéket adja meg. A t.End() a felsorolás során mindaddig hamis értéket ad vissza, amíg van kijelölt aktuális elem, a felsorolás végét viszont igaz visszaadott értékkel jelzi. Ez a két utóbbi művelet nem változtathatja meg a felsoroló állapotát. Fontos kritérium, hogy a felsorolás vége véges lépésben (a t.Next() véges sok végrehajtása után) bekövetkezzék. A felsoroló műveletek hatását általában nem definiáljuk minden esetre. Például nem-definiált az, hogy a t.First() végrehajtása előtt (tehát a felsorolás kezdete előtt) illetve a t.End() igazra váltása után (azaz a felsorolás befejezése után) mi a hatása a t.Next(), a t.Current() és a t.End() műveleteknek. Általában nem definiált az sem, hogy mi történjen akkor, ha a t.First() műveletet a felsorolás közben ismételten végrehajtjuk. Minden olyan típust felsorolónak nevezünk, amely megfelel a felsoroló típusspecifikációnak, azaz implementálja a First(), Next(), End() és Current() műveleteket. A felsoroló (enumerator) típust enor(E)-vel jelöljük, ahol az E a felsorolt elemi értékek típusa. Ezt a jelölés alkalmazhatjuk a típus értékhalmazára is. Egy felsoroló objektum hátterében mindig elemi értékeknek azon véges hosszú sorozatát látjuk, amelynek elemeit sorban, egymás után be tudjuk járni, fel tudjuk sorolni. Ezért specifikációs jelölésként megengedjük, hogy egy t felsoroló által felsorolható elemi értékre úgy hivatkozzunk, mint egy véges sorozat elemeire: a ti a felsorolás során i-edikként felsorolt elemi érték, ahol i az 1 és a felsorolt elemek száma (jelöljük ezt t-vel) közé eső egész szám. Hangsúlyozzuk, hogy a felsorolható elemek száma definíció szerint véges. Ezzel tulajdonképpen egy absztrakt 25 1 Amikor a felsorolható adat egy gyűjtemény (iterált), akkor a felsoroló objektumot szokták bejárónak vagy iterátornak is nevezni, míg maga a felsorolható gyűjtemény a bejárható, azaz iterálható adat. 2 A műveletek jelölésére az objektum orientált stílust használjuk: t.First() a t felsorolóra vonatkozó First() műveletet jelöli.

110

8.2. Felsoroló típus specifikációja

megvalósítást is adtunk a felsoroló típusnak: a felsorolókat a felsorolandó elemi értékek sorozata reprezentálja, a felsorolás műveleteit ezen a sorozat bejárásával implementáljuk. A felsoroló típus konkrét reprezentációjában mindig megjelenik valamilyen hivatkozás arra az adatra, amelyet felsorolni kívánunk. Ez lehet egyetlen természetes szám, ha annak az osztóit kell előállítani, lehet egy vektor, szekvenciális inputfájl, halmaz, esetleg multiplicitásos halmaz (zsák), ha ezek elemeinek felsorolása a cél, vagy akár egy gráf, amelynek a csúcsait valamilyen stratégiával be kell járni, hogy az ott tárolt értékekhez hozzájussunk. A reprezentáció ezen az érték-szolgáltató adaton kívül még tartalmazhat egyéb, a felsorolást segítő komponenseket is. A felsorolás során mindig van egy aktuális elemi érték, amelyet az adott pillanatban lekérdezhetünk. Egy vektor elemeinek felsorolásánál ehhez elég egy indexváltozó, egy szekvenciális inputfájl esetében a legutoljára kiolvasott elemet kell tárolni illetve, azt, hogy sikeres volt-e a legutolsó olvasás, az egész szám osztóinak felsorolásakor például a legutoljára megadott osztót. Egy felsoroló által visszaadott értékeket rendszerint valahogyan feldolgozzuk. Ez a feldolgozás igen változatos lehet; jelöljük ezt most általánosan az F(e)-vel, amely egy e elemi értéken végzett tetszőleges tevékenységet takar. Nem szorul különösebb magyarázatra, hogy a felsorolásra épülő feldolgozást az alábbi algoritmus-séma végzi el. Megjegyezzük, hogy mivel a felsorolható elemek száma véges, ezért ez a feldolgozás véges lépésben garantáltan befejeződik.

t.First() t.End() F( t.Current() ) t.Next()

8.3.

Nevezetes felsorolók

Az alábbiakban megvizsgálunk néhány fontos felsoroló típust, olyat, amelynek reprezentációja valamilyen nevezetes – egy kivételével – iterált típusra épül. Vizsgálatainknak fontos része lesz, hogy megmutatjuk egy-egy konkrét felsoroló típusú objektum esetén azt az általános feldolgozást végző algoritmus-sémát, amellyel be lehet járni a felsorolt értékeket. Természetesen minden esetben ki fogunk térni arra, hogy a vizsgált típus hogyan feleltethető meg a felsoroló típusspecifikációnak, azaz mi a felsorolást biztosító First(), Next(), End() és Current() műveletek implementációja. Tekintsük először az egész-intervallumot felsoroló típust. Itt egy [m..n] intervallum elemeinek klasszikus, m-től n-ig egyesével történő felsorolására gondolunk. Természetesen ennek mintájára lehet definiálni a fordított sorrendű vagy a kettesével növekedő felsorolót is. Az egész számok intervallumát nem tekintjük iterált szerkezetűnek, hiszen a reprezentációjához elég az intervallum két végpontját megadni, műveletei pedig ezeket az intervallumhatárokat kérdezik le. Ugyanakkor mindig fel lehet sorolni az intervallumba eső számokat. Az egész-intervallumra épülő felsoroló típus attól különleges számunkra, hogy a

111


korábban bevezetett programozási tételeinket is az egész számok egy intervallumára fogalmaztuk meg, amelyeket ennek közvetítésével más felsoroló típusú objektumokra is ki tudunk majd terjeszteni. A felsoroló típus egy típusértékét egy [m..n] intervallum két végpontja (m és n) és az intervallum elemeinek felsorolását segítő egész értékű indexváltozó (i) reprezentálja. Az i változó az [m..n] intervallum aktuálisan kijelölt elemét tartalmazza, azaz implementálja a Current() függvényt. A First() műveletet az i:=m értékadás, a Next() műveletet az i:=i+1 értékadás váltja ki. Az i>n helyettesíti az End() függvényt. (A First() művelet itt ismételten is kiadható, és mindig újraindítja a felsorolást, mind a négy művelet bármikor, a felsoroláson kívül is terminál.) Könnyű végiggondolni, hogy miként lehetne az intervallumot fordított sorrendben ( i:=n, i:=i-1, i<m), vagy kettesével növekedően (i:=m, i:=i+2, i>n) felsorolni. Ezek alapján a felsoroló objektum feldolgozását végző általános algoritmus-sémából előállítható az egész-intervallum normál sorrendű feldolgozását végző algoritmus, amelyet számlálós ciklus formájában is megadhatunk.

i:=m

i := m .. n

i n

F(i)

F(i) i:=i+1 Magától értetődően lehet sorozatot felsoroló típust készíteni. (Itt is a klasszikus, elejétől a végéig tartó bejárásra gondolunk, megjegyezve, hogy más bejárások is vannak.) A reprezentáció ilyenkor egy sorozat típusú adat (s) mellett még egy indexváltozót (i) is tartalmaz. A sorozat normális (elejétől végéig történő) bejárása során az i egész típusú indexváltozót az 1 .. s intervallumon kell végig vezetni éppen úgy, ahogy ezt az előbb láttuk. Ekkor az si-t tekinthetjük az Current() kifejezésnek, az i:=1 a First() művelet lesz, az i:=i+1 a Next() művelet megfelelője, az i>s pedig az End() kifejezéssel egyenértékű. (A First() művelet ismételten is kiadható, és mindig újraindítja a felsorolást, a Next() és End() bármikor befejeződik, de a Current()csak a felsoroláson alatt terminál.) Ezek alapján az s sorozat elemeinek elejétől végéig történő felsorolását végző programot az alábbi két alakban írhatjuk fel. i:=1

i :=1 .. s

is

F(si)

F(si) i:=i+1 A vektort (klasszikusan) felsoroló típus a sorozatokétól csak abban különbözik, hogy itt nem egy sorozat, hanem egy v vektor bejárása a cél. A bejáráshoz használt indexváltozót

112

8.3. Nevezetes felsorolók

(jelöljük ezt most is i-vel) a bejárandó v vektor indextartományán (jelöljük ezt [m..n]-nel) kell végigvezetünk, és az aktuális értékre a v[i] formában hivatkoznunk. Ennek értelmében az v[i]t tekinthetjük a Current() műveletnek, az i:=m tulajdonképpen a First() művelet lesz, az i:=i+1 a Next() művelet megfelelője, az i>n pedig a End() kifejezéssel egyenértékű. (A First() művelet ismételten is kiadható, és mindig újraindítja a felsorolást, a Next() és End() bármikor befejeződik, de a Current()csak a felsoroláson alatt terminál.) Egy vektor elemeinek feldolgozását az intervallumhoz hasonlóan kétféleképpen írjuk fel:

i:=m

i :=m .. n

i n

F(v[i])

F(v[i]) i:=i+1 Egy vektoroknak (akárcsak a korábban látott intervallumnak és sorozatnak) nemcsak egyféle bejárása lehetséges. Megengedett rájuk például a visszafelé haladó bejárás, vagy a kettesével történő bejárás is. Sőt valójában mindenféle bejárást értelmezhetünk rájuk. (Könyvünkben úgy tekintünk a vektor indextartományára, mint egy egész intervallumra. A vektor típus fogalma azonban általánosítható úgy, hogy indextartományát egy felsoroló objektum írja le. Ilyenkor a vektort felsoroló objektum műveletei megegyeznek az ő indextartományát felsoroló objektum műveleteivel egyet kivéve: a Current() műveletet a v[i.Current()] implementálja, ahol i az indextartomány elemeit felsoroló objektumot jelöli.) Mivel a mátrix vektorok vektora, ezért nem meglepő, hogy mátrixot (sorfolytonosan) felsoroló típust is lehet készíteni. Ez a mátrix esetén az egyik leggyakrabban alkalmazott felsorolás, amikor először az első sor elemeit, azt követően a másodikat, és így tovább, végül az utolsó sort járjuk be. Egy a jelű n*m-es mátrix (azaz téglalap-mátrix, ahol minden sor egyformán m hosszú) ilyen sorfolytonos bejárásánál a mátrixot felfoghatjuk egy n*m elemű v vektornak, ahol minden 1 és n*m közé eső k egész számra a v[k] = a[((k-1) div m) +1, ((k-1) mod m) +1]. Ezek után a bejárást a vektoroknál bemutatott módon végezhetjük. Egyszerűsödik a fenti képlet, ha a vektor és a mátrix indextartományait egyaránt 0-tól kezdődően indexeljük. Ilyenkor v[k] = a[k div m, k mod m], ahol a k a 0..n*m-1 intervallumot futja be. A mátrix elemeinek sorfolytonos bejárása így igen egyszerű lesz, bár nem ez az általánosan ismert módszer.

k := 0 .. n*m-1 F(a[k div m, k mod m]) Mivel a mátrix egy kétdimenziós szerkezetű típus, ezért a bejárásához az előbb bemutatott módszerrel szemben két indexváltozót szoktak használni. (Más szóval a mátrix

113


bejárót egy mátrix és két indexváltozó reprezentálja.) Sorfolytonos bejárásnál az egyiket a mátrix sorai közötti bejárásra, a másikat az aktuális sor elemeinek a bejárására használjuk. A bejárás során a[i,j] lesz a Current(). Először a a[1,1]-re kell lépni, így a First() műveletet az i,j:=1,1 implementálja. A soron következő mátrixelemre egy elágazással léphetünk rá. Ha a j bejáró még nem érte el az aktuális sor végét, akkor azt kell eggyel megnövelni. Ellenkező esetben az i bejárót növeljük meg eggyel, hogy a következő sorra lépjünk, a j bejárót pedig a sor elejére állítjuk. Összességében tehát az IF(j<m: j:=j+1; j=m: i,j:=i+1,1) elágazás implementálja a Next() műveletet. Az End() kifejezést az i>n helyettesíti. (Ez a megoldás könnyen általánosítható nem téglalap-mátrixra is, ahol a sorok eltérő hosszúak és eltérő indexelésűek.)

i,j:=1,1 i n F( a[i,j] ) j<m j:=j+1

i,j:=i+1,1

Ennek a megoldásnak a gyakorlatban jobban ismert változata az alábbi kétciklusos algoritmus. Itt az i,j:=1,1 értékadást (First()) a két egymásba ágyazott ciklus inicializáló lépése végzi el. A Next() műveletet megvalósító elágazás feltétele (jm) a belső ciklus ciklusfeltétele lesz, a belső ciklus ciklusmagja pedig a megfelelő programág (j:=j+1). Az elágazás másik ága a belső ciklus befejeződése után (tehát j>m esetben) hajtódik végre: először a külső ciklus magjának végén az i:=i+1, majd a ciklusmag ismételt futtatásának elején, a belső ciklus indexváltozójának inicializálása (j:=1) során történik meg. Természetesen ezt a két egymásba ágyazott ciklust számlálásos ciklusként érdemes leírni. A továbbiakban mi is többnyire ezt a változatot fogjuk használni. Meg lehet mutatni, hogy ez ekvivalens az előbbi változattal.

i :=1 .. n j :=1 .. m F( a[i,j] ) A szekvenciális inputfájl felsoroló típusa egy szekvenciális inputfájllal (f), az abból legutoljára kiolvasott elemi értékkel (df), és az utolsó olvasás státuszával (sf) reprezentál egy bejárót. A szekvenciális inputfájl felsorolása csak az elejétől végéig történő olvasással lehetséges, ezért az sf, df, f : read művelet implementálja a First() és a Next() műveleteket, a Current() a df értékét adja vissza, az End() pedig az sf=abnorm vizsgálat értékével azonos. Minden művelet bármikor alkalmazható.

114

8.3. Nevezetes felsorolók

sf, df, f : read sf=norm F(df) sf, df, f : read A First() műveletet az először kiadott sf,df,f:read művelet váltja ki. Ez az aktuális elemet a df segédváltozóba teszi, így a Current() helyett közvetlenül a df értékét lehet használni. A read művelet mindig értelmezett, de a bejárást nem lehet ismételten elindítani vele. Az ismételten kiadott sf,df,f:read művelet ugyanis már az f.Next() művelettel egyenértékű. Az f.End() az olvasás sikerességét mutató sf státuszváltozó vizsgálatával helyettesíthető. (Mind a négy művelet minden esetben, a felsoroláson kívül is terminál.) A halmazt felsoroló típus reprezentációjában egy a felsorolandó elemeket tartalmazó h halmaz szerepel. Ha a h=, akkor a halmaz bejárása nem lehetséges vagy nem folytatható – ez lesz tehát az End() művelet. Ha a h, akkor könnyen kiválaszthatjuk felsorolás számára a halmaznak akár az első, akár soron következő elemét. Természetesen az elemek halmazbeli sorrendjéről nem beszélhetünk, csak a felsorolás sorrendjéről. Ez az elemkiválasztás elvégezhető a nem-determinisztikus e:h értékkiválasztással éppen úgy, mint a halmazokra korábban bevezetett determinisztikus elemkiválasztás (e:=mem(h)). Mi ez utóbbit fogjuk a Current() művelet megvalósítására felhasználni azért, hogy amikor a halmaz bejárása során tovább akarunk majd lépni, akkor éppen ezt, a felsorolás során előbb kiválasztott elemet tudjuk majd kivenni a halmazból. Ehhez pedig pontosan ugyanúgy kell tudnunk megismételni az elemkiválasztást. A Next() művelet ugyanis nem lesz más, mint a mem(h) elemnek a h halmazból való eltávolítása, azaz a h:=h–{mem(h)}. Ennek az elemkivonásnak az implementációja egyszerűbb, mint egy tetszőleges elem kivonásáé, mert itt mindig csak olyan elemet veszünk el a h halmazból, amely biztosan szerepel benne, ezért ezt külön nem kell vizsgálni. A Next() művelet is (akárcsak a Current()) csak a bejárás alatt – azaz amíg az End() hamis – alkalmazható. Láthatjuk azonban, hogy sem az End(), sem a Current(), sem a Next() művelet alkalmazásához nem kell semmilyen előkészületet tenni, azaz a felsorolást elindító First() művelet halmazok bejárása esetén az üres (semmit sem csináló) program lesz. Ezen megjegyzéseknek megfelelően a halmaz elemeinek feldolgozását az alábbi algoritmus végzi el: h F(mem(e)) h := h – {mem(e)}

115


8.4.

Programozási tételek általánosítása

A programozási tételeinket korábban az egész számok intervallumára fogalmaztuk meg, ahol egy intervallumon értelmezett függvénynek értékeit kellett feldolgozni. Ennek során bejártuk, felsoroltuk az intervallum elemeit, és mindig az aktuális egész számhoz tartozó függvényértéket vizsgáltuk meg. Az egész számok intervallumához – mint azt láttuk – elkészíthető egy klasszikus sorrendű felsoroló, amely éppen úgy képes az intervallumot bejárni, ahogy azt az intervallumos programozási tételekben láttuk.. Ennek alapján általánosíthatjuk a programozási tételeinket bármilyen más felsoroló típusra is. A feladatokat ilyenkor nem intervallumon értelmezett függvényekre, hanem egy felsorolóra, pontosabban a felsoroló által felsorolt értékeken értelmezett függvényekre mondjuk ki. A megoldó programokban az intervallumot befutó i helyett a Current(), az i:=m értékadás helyett a First(), az i:=i+1 értékadás helyett a Next(), és az i≤n feltétel helyett az End() művelet használjuk. Az általános tételekre aztán bármelyik konkrét felsorolóra megfogalmazott összegzés, számlálás, maximum vagy adott tulajdonságú elem keresése visszavezethető. Ezek között természetesen az intervallumon értelmezett függvényekkel megfogalmazott feladatok is, tehát minden eddig megszerzett feladat-megoldási tapasztalatunk megmarad. A programozási tételek ehhez hasonló általánosításaival egyszer-egyszer már korábban is találkoztunk. Már korábban is oldottunk meg olyan feladatokat, ahol nem intervallumon értelmezett függvényre, hanem vektorra alkalmaztuk a tételeinket. Ezt eddig azzal magyaráztuk, hogy a vektor felfogható egy táblázattal megadott egész intervallumon értelmezett függvénynek. Most már egy másik magyarázatunk is van. Az intervallum és a vektor rokon típusok: mindkettőhöz készíthető felsoroló. Egy felsorolóra megfogalmazott összegzés, számlálás, maximum vagy adott tulajdonságú elem keresés során pedig mindegy, hogy egy intervallumon értelmezett függvény értékeit kell-e sorban megvizsgálni vagy egy vektornak az elemeit, hiszen ezeket az értékeket úgyis a felsorolás állítja elő. Az alábbiakban bemutatott általános programozási tételekben nem közvetlenül a felsorolt elemeket dolgozzuk fel (adjuk össze, számoljuk meg, stb.), hanem az elemekhez hozzárendelt értékeket. Ezeket bizonyos tételeknél (pl. összegzés, maximum kiválasztás) egy f:E→H függvény (ez sokszor lehet az identitás), másoknál (pl. számlálás, keresés) egy :E→L logikai függvény jelöli ki. amely a felsorolt értékekhez rendeli a feldolgozás alapját képező értékeket. Ennek következtében a feldolgozás során általában nem a t.Current() értékeket, hanem az f(t.Current()) vagy (t.Current()) értékeket kell vizsgálni. A maximum kiválasztásnál, a feltételes maximum keresésnél, a kiválasztásnál és a lineáris keresésnél célszerű bevezetni egy-egy új specifikációs jelölést. Mind a négy esetben megadjuk ugyan az utófeltétel eredeti formuláját is, amelyről azonban látszik, hogy a visszavezetés szempontjából sok lényegtelen elemet tartalmaz. Ezért indokolt a rövidített jelölések használata.

116

8.4. Programozási tételek általánosítása

Összegzés Feladat: Adott egy enor(E) felsoroló típusú t objektum és egy f:E→H függvény. A H halmazon értelmezzük az összeadás asszociatív, baloldali nullelemes műveletét. Határozzuk t

meg a függvénynek a t elemeihez rendelt értékeinek összegét, azaz a  f (t i ) kifejezés i 1

értékét! (Üres objektum esetén az összeg értéke definíció szerint a nullelem: 0). Algoritmus: Specifikáció: s := 0

A = ( t:enor(E), s:N ) Ef = ( t=t’ )

t.First()

t'

t.End()

Uf = (s =  f (t i, ) )

s := s + f(t.Current())

i 1

t.Next() Számlálás Feladat: Adott egy enor(E) felsoroló típusú t objektum és egy :EL feltétel. Határozzuk meg, hogy a felsoroló objektum elemi értékei közül hányra teljesül a feltétel. Specifikáció:

Algoritmus: c:=0

A = ( t:enor(E), c:N ) Ef = ( t=t’) t'

Uf = ( c   1 ) i 1

 ( ti, )

t.First() t.End()

( t.Current() ) c:=c+1

SKIP t.Next()

117


Maximum kiválasztás Feladat: Adott egy enor(E) felsoroló típusú t objektum és egy f:E→H függvény. A H halmazon definiáltunk egy teljes rendezési relációt. Feltesszük, hogy t nem üres. Határozzuk meg az f függvénynek a t elemeihez rendelt értékei között a maximálisat. Specifikáció:

Algoritmus: t.First()

A = ( t:enor(E), max:H, elem:E ) Ef = ( t=t’  t>0 ) Uf = (max = f(elem) =

max, elem:= f(t.Current()), t.Current() t.Next()

t'

= max f (t i, )  elem t’)

t.End()

i 1

t'

, i

= (max, elem = max f (t ) ) i 1

f(t.Current())>max max, elem:= f(t.Current()), t.Current()

SKIP

t.Next() Feltételes maximum keresés Feladat: Adott egy enor(E) felsoroló típus t objektum és egy f:E→H függvény. A H halmazon definiáltunk egy teljes rendezési relációt. Adott továbbá egy :HL feltétel. Határozzuk meg t azon elemeihez rendelt f szerinti értékek között a maximálisat, amelyek kielégítik a  feltételt. Specifikáció: A = ( t:enor(E), l:L, max:H, elem:E ) Ef = ( t=t’) Uf = ((l= i[1.. t’]: (t’i) )  (l  elem t’  (elem)  max=f(elem)  t'

i[1.. t’]: ((t’i)  f(t’i)  max) ) ) = (l, max, elem = max f (t i, ) ) i 1

 ( ti' )

Algoritmus: l:= hamis; t.First() t.End() (t.Current())

(t.Current())  l

SKIP

f(t.Current())>max max, elem:= f(t.Current()), t.Current()

( t.Current())  l l, max, elem := SKIP

t.Next()

118

igaz, f(t.Current()), t.Current()

8.4. Programozási tételek általánosítása

Kiválasztás Feladat: Adott egy enor(E) felsoroló típusú t objektum és egy :EL feltétel. Keressük a t bejárása során az első olyan elemi értéket, amely kielégíti a :EL feltételt, ha tudjuk, hogy biztosan van ilyen. Specifikáció: A = ( t:enor(E), elem:E ) Ef = ( t=t’  i[1.. t]: (ti) ) Uf = (i[1.. t’]: elem  ti,  (elem) 

Algoritmus: t.First() (t.Current())

j[1..i-1]: ( t i, )  t = t’[i+1.. t’]) )= = ( elem , t  select  (t i' ) )

t.Next() elem:=t.Current()

i 1

Lineáris keresés Feladat: Adott egy enor(E) felsoroló típusú t objektum és egy :EL feltétel. Keressük a t bejárása során az első olyan elemi értéket, amely kielégíti a :EL feltételt. Specifikáció: A = ( t:enor(E), l:L, elem:E ) Ef = ( t=t’) Uf = ( (l=i[1.. t’]:(ti))  (l  i[1.. t’]: elem  ti,  (elem)

Algoritmus: l := hamis; t.First() l  t.End() elem := t.Current()

 j[1..i-1]: ( t ))  t = t’[i+1.. t’]) )= , i

l := (elem) t.Next()

t'

= ( l , elem , t  search  (t ) ) i 1

' i

Rekurzív függvény helyettesítési értéke Feladat: Adott egy enor(E) felsoroló típusú t objektum és egy f:ZH k-ad rendű 1 bázisú rekurzív függvény (k pozitív egész szám) úgy, hogy f(i) = h(ti, f(i–1), ... ,f(i–k) ) ahol i≥1 és a f egy E×HkH függvény, továbbá f(m–1)=em–1, ... , f(m–k)= em–k, ahol em-1, ... , em–k H-beli értékek. Számítsuk ki az f függvény t helyen felvett értékét! Specifikáció: A = ( t:enor(E), y:H ) Ef = ( t=t’ ) Uf = ( y=f(t’) )

Algoritmus: y, y1, ... , yk–1 := em–1, em–2, ... , em–k ; t.First() t.End() y, y1, y2,... , yk–1 := h(t.Current(), y, y1, ... , yk–1), y, y1, ... , yk–2 t.Next()

119


A programozási tételek alkalmazásakor – ha körültekintően járunk el – szabad az algoritmuson hatékonyságot javító módosításokat tenni. Ilyen például az, amikor ahelyett, hogy sokszor egymás után lekérdezzük a t.Current() értékét, azt annak első lekérdezésénél egy segédváltozóba elmentjük. A maximum-kiválasztás illetve feltételes maximum keresés esetén a feldolgozás eredményei között szerepel mind a megtalált maximális érték, mind az az elem, amelyhez a maximális érték tartozik. Konkrét esetekben azonban nincs mindig mindkettőre szükség. Indexelhető gyűjtemények (vektor, sorozat) esetén azonban az elem helyett elég megadni annak indexét. Olyan esetekben, ahol a f függvény identitás, azaz egy elem és annak értéke megegyezik, a maximális elem és maximális érték közül elég csak az egyiket nyilvántartani az algoritmusban. Kiválasztásoknál nem kell a felsoroló által szolgáltatott értéksorozatnak végesnek lennie, hiszen ez a tétel más módon garantálja a feldolgozás véges lépésben történő leállását. A lineáris keresésnél és kiválasztásnál az eredmények között szerepel maga a felsoroló is. Ennek az oka az, hogy ennél a két tételnél korábban is leállhat a feldolgozás, mint hogy a felsorolás véget érne, és ekkor maradnak még fel nem sorolt (fel nem dolgozott) elemek. Ezeket az elemeket további feldolgozásnak lehet alávetni, ha a felsorolót tovább használjuk. Felhívjuk azonban a figyelmet arra, hogy egy már korábban használt felsorolóval dolgozunk tovább, akkor nem szabad a First() művelettel újraindítani a felsorolást. A specifikációban egy ilyen folytatólagos felsorolásra úgy fogunk utalni, hogy a feldolgozás szimbóluma alatt szereplő i=1 helyére csak az i-t írjuk. Nevezetes felsorolók esetén a specifikációs jelölés módosulhat úgy, hogy abban a felsorolót az őt reprezentáló elemekkel helyettesítjük. Például egy x szekvenciális inputfájlon folyó feldolgozásnál, ahol a fájl bejárását az sx, dx, x:read művelet végezzük, a felsorolót az sx, dx, x hármas reprezentálja. Amikor egy keresés vagy a kiválasztás úgy áll le, hogy az sx=norm, akkor a dx mutatja az aktuális, még fel nem dolgozott elemet, az x pedig az összes többi feldolgozatlan elemet. Tehát a további feldolgozásra váró már „megkezdett” felsoroló, ami a feldolgozás eredményi között szerepel, az sx, dx, x hármasa lesz. x'

l, elem, sx, dx, x  search  ( x' i ) i 1

illetve elem , sx, dx, x  select  ( x'i ) i 1

Egy h halmaz felsorolóját maga a h halmaz reprezentálja. A keresés vagy kiválasztás esetén a feldolgozatlan elemek a halmazban maradnak: l, elem, h  search  (e) eh '

illetve

elem , h  select  (e) eh '

Mind a fájl, mind a halmaz esetében a felsorolandó adat folyamatosan változik (elfogy) a bejárás során. Más a helyzet például egy vektor bejárásánál. Egy m..n intervallumon értelmezett v vektor feldolgozása esetén maga a vektor nem változik (v=v’), csak a bejárás helyét jelző i index. A feldolgozás eredményénél, ha szükségünk van arra, hogy hol állt le a felsorolás, elég ezt feltüntetni: v

l ,elem ,i  search  ( v [ i ]) i m

120

illetve

elem , i  select  (v[i]) i m

8.5. Visszavezetés nevezetes felsorolókkal

Visszavezetés nevezetes felsorolókkal

8.5.

A most bevezetett tételek segítségével egyszerűvé válik az olyan feladatok megoldása, amelyek felsorolt értékek összegzését, megszámolását, maximum-kiválasztását vagy keresését írják elő. Ha a feladat specifikációjában rámutatunk arra, hogy milyen felsorolóra vonatkozik a feladat (hogyan kell implementálni a First(), Next(), End() és Current() műveleteket) és milyen programozási tétel alapján kell a felsorolt értékeket feldolgozni (mi helyettesíti az adott programozási tételben szereplő függvényt, függvényeket), akkor visszavezetéssel megkaphatjuk a megoldást. Ráadásul ha az alkalmazott felsorolás a 8.3 alfejezetben részletesen tárgyalt nevezetes felsorolók egyike, akkor nagyon egyszerű lesz a dolgunk. Most ez utóbbi esetre mutatunk néhány példát, amellyel azt kívánjuk illusztrálni, hogy a fentiekkel milyen erős eszközt kaptunk a módszeres programtervezés számára. (Azon feladatok megoldásával, amelyek megoldásához egyedi módon kell a felsorolót megtervezni, a következő fejezetben foglalkozunk.) Először nagyon egyszerű, a visszavezetés technikáját bemutató feladatokat oldunk meg. Négy feladatban halmazok illetve szekvenciális inputfájl feldolgozásáról, és a számlálás, maximum-kiválasztás, keresés és kiválasztás tételeinek alkalmazásáról lesz szó. Utána két mátrixos feladat megoldása következik. A mátrix „kétdimenziós bejárása” érdekes tanulságokkal szolgál a maximum-kiválasztás és a lineáris keresés alkalmazása esetén. Végül az úgynevezett elemenkénti feldolgozásokra, az összegzés tételének speciális alkalmazásaira mutatunk példákat. Itt az összegzés eredménye is egy gyűjtemény, az összeadás művelete e gyűjteménybe történő új elem beírása. 8.1. Példa. Egy halmaz egész számokat tartalmaz. Keressük meg a halmaz maximális elemét! A feladat specifikációjának felírása nem jelent problémát. Az utófeltételből látszik, hogy itt egy halmaz elemeinek felsorolására épített maximum-kiválasztásról van szó. A = ( h:set(Z), max:Z ) Ef = ( h=h’) Uf = ( Ef  max = max e ) eh

Ebben a specifikációban azonban nem jelenik még meg explicit módon a felsoroló. Alakítsuk át úgy a specifikációt, hogy annak állapotterében a halmaz helyett, a halmaz elemeit felsoroló objektum jelenjen meg. Ebben az átfogalmazásban már nem lényeges, hogy egy halmaz felsorolásáról van szó, hiszen a feladatot egy általános felsorolóra fogalmazzuk meg: A = ( t:enor(Z), max:Z ) Ef = ( t=t’) t'

Uf = ( Ef  max = max t i, ) i 1

Az általános maximum-kiválasztás programozási tételére való visszavezetés most már formálisan történik: az általános specifikáció és az itt látható specifikáció néhány, jól

121


körülhatárolható ponton tér csak el. A felsoroló egész számokat állít elő, a feldolgozást végző függvény pedig az egész számokon értelmezett identitás. E=H=Z f(e) = e (eZ) Az identitás miatt a feldolgozásnak itt a konkrét esetben csak egy eredménye (max) van, hiszen a megtalált maximális értékű elem és annak értéke egy és ugyanaz. Ennek megfelelően átalakítva alkalmazhatjuk az általános algoritmust:

t.First() max:= t.Current() t.Next() t.End() t.Current()>max max:=t.Current()

SKIP

t.Next() Ezek után foglalkozunk a felsoroló műveletekkel. A h halmaz felsorolása ismert (lásd 8.3 alfejezet), így a műveletek implementációja adott: First() ~ SKIP, End() ~ h=, Current() ~ mem(h), Next() ~ h:=h-{mem(h)}. Ezek alapján elkészíthető a feladatot megoldó program végső változata. Ebben egy segédváltozót vezettünk be annak érdekében, hogy ne kelljen a mem(h)-t ugyanarra a h-ra többször egymás után végrehajtani. max:= mem(h) h:=h-{max} h e:= mem(h) e>max max:= e

SKIP

h:=h-{e} A gyakorlatban természetesen nem kell ennyire részletesen dokumentálni a visszavezetés lépéseit. A fenti gondolatmenetből elegendő csak a feladat eredeti specifikációját, a felsoroló típusának megnevezését (itt: halmaz felsoroló), a visszavezetés analógiáját (itt: maximum-kiválasztás és f(e )~ e), és végül a végleges algoritmust leírni.

122


8.2. Példa. Számoljuk meg egy halmazbeli szavak között, hogy hány ’a’ betűvel kezdődő van! A feladat specifikációja egyszerű: A = ( h:set(k*), db:N ) Ef = ( h=h’) Uf = ( db  1 ) szóh ' szó1  'a '

Ez visszavezethető a számlálás programozási tételére halmaz felsorolóval, ahol a számlálás feltétele az aktuális elem (szó) első betűjének megfelelő vizsgálata. A mem(h) (aktuális szó) értékének ideiglenes tárolására a szó segédváltozót vezetjük be.

db:= 0 h szó:= mem(h) szó1=’a’ db:= db+1

SKIP

h:=h-{szó} 8.3. Példa. Egy szekvenciális inputfájl egész számokat tartalmaz. Keressük meg az első nem-negatív elemét! A = (f:infile(Z), l:L, e:Z) Ef = ( f=f’) f'

Uf = ( l , e  search ( f 'i  0) ) i 1

A feladatot szekvenciális inputfájl bejárása feletti általános lineáris keresésre vezetjük vissza, ahol a keresett feltétel a vizsgált fájlbeli elem nem-negatív tulajdonsága. A 8.3 alfejezetből tudjuk, hogy szekvenciális inputfájlok esetén a felsorolót az sf, df, f értékhármas reprezentálja, ahol sf az f-re vonatkozó olvasás státusza, df a kiolvasott elem. A felsoroló First() és Next() műveleteit az sf, df, f : read implementálja, a Current() kifejezést a df, a End()-et pedig az sf=norm. l:=hamis;

sf, df, f : read

l  sf=norm e:= df l:= df ≥ 0 sf, df, f : read

123


8.4. Példa. Keressük meg egy szekvenciális inputfájlban található szöveg első szavának kezdetét, azaz lépjük át (olvassuk ki) egy szöveg elején levő szóközöket, és ha van nemszóköz is benne, akkor az első ilyen kiolvasása után álljunk meg! Ezt a feladatot a kiválasztás programozási tételére vezethetjük vissza, ugyanis vagy az első nem szóköz karaktert kell megtalálnunk, vagy ha ilyen nincs, akkor a fájl végét; ez az összetett feltétel biztosan teljesül. Az eredmény tehát egyrészt az sf és df, másrészt a megolvasott szekvenciális inputfájl lesz, azaz sf, df, f. A specifikáció meglehetősen körülményes a megoldó algoritmushoz képest. A = (f:infile(K), df: K, sf:Státusz) Ef = ( f=f’) Uf = ( sf , df , f  select (i  f '  f 'i ' ' ) ) i 1

sf, df, f : read sf=norm  df=’ ’ sf, df, f : read Kétdimenziós jellegénél fogva a mátrixokra értelmezett maximum-kiválasztás és lineáris keresés is érdekes tanulságokkal jár. 8.5. Példa. Adjuk meg egy egész elemű mátrix egyik maximális elemét és annak indexeit! Specifikáljuk először a feladatot! Feltesszük, hogy a mátrixnak n darab sora és m darab oszlopa van, és mindkettő értéke legalább egy (ez utóbbi kell ahhoz, hogy a maximum kiválasztás értelmes legyen). A = (a:Zn×m, max:Z, ind:N, jnd:N)) Ef = ( a=a’  n>0  m>0 ) n ,m

Uf = ( a=a’  ind [1 .. n]  jnd [1 .. m]  max = a[ind,jnd] = max a[i, j ] ) = i 1, j 1

n ,m

= (a=a’  max, ind, jnd = max a[i, j ] ) i 1, j 1

A specifikációból látható, hogy itt a mátrix elemeit kell bejárni és egyik maximális elemét megtalálni. Úgy gondoljuk, nem szorul külön magyarázatra a specifikációban használt, csak mátrixokra alkalmazható dupla indexváltozós maximum-kiválasztásnak a jele. Ha ötvözzük a felsoroló típusra megfogalmazott maximum kiválasztás algoritmusát azzal, hogyan lehet a First(), Next(), End() és Current() műveleteket mátrixok elemeinek bejárásánál implementálni (ezt a 8.3. alfejezetben többféleképpen is megoldottuk), akkor megkapjuk a feladat megoldását. Mivel a legismertebb a két leszámlálásos ciklusra írt változat, ezért mi is ezt adjuk meg. Ez a változat rendelkezik egy apró hibával az a[1,1]-et kétszer is megvizsgálja: először a kezdeti értékek beállításánál, majd a ciklusmag első lefutása során. Ezt a hibát ebben a változatban csak úgy lehetne korrigálni, ha a ciklusmagba beletennénk egy plusz elágazást,

124


amely i=1 és j=1 esetben megtiltaná az összehasonlítást, de ettől a program hatékonysága rosszabb lenne a jelenlegi változatnál.

ind, jnd, max:=1, 1, a[1,1] i :=1 .. n j :=1 .. m a[i,j]>max ind, jnd, max:=i, j, a[i,j]

SKIP

Megjegyezzük, hogy egy a mátrix elemeire közvetlenül megfogalmazott feladatot – mint amilyen ez is – át lehetne fogalmazni úgy, hogy az a mátrix soraira vonatkozzon. Például a maximális értéket kereshetjük a mátrix sorainak maximális elemei között. Ekkor a feladat egymásba ágyazott intervallumos programozási tételekre is visszavezethető. 8.6. Példa. Keressünk egy egész elemű mátrixban egy páros számot és adjuk meg annak indexeit! A = (a:Zn×m, l:L, ind:N, jnd:N)) Ef = ( a=a’) Uf = ( a=a’  (l = i[1 .. n]  j[1 .. m]: 2a[ind,jnd])  (l → ind [1 .. n]  jnd [1 .. m]  2a[ind,jnd])) ) n,m

= ( a=a’  ( l , ind , jnd  search (2 a[i, j ]) ) i 1, j 1

Itt is bevezettünk egy speciális mátrixos jelölést a lineáris keresésre. Ezzel egyrészt a kétdimenziós bejárásra utalunk, másrészt arra, hogy a keresésnek három eredménye van: egy logikai érték, és annak igaz értéke esetén a megtalált elem sor- és oszlopindexe. Ehhez illeszkedve a megoldásnak is a két-ciklusos változatát adjuk meg.

l, i:=hamis, 1

l  i≤ n j:=1

l  j≤m l, ind, jnd := 2a[i,j], i, j j:=j+1 i:=i+1 Egy felsoroló típusú adat feldolgozásának egy fontos csoportja az, amikor a kimenő adat is elemi értékek gyűjteménye (például halmaz, sorozat, vektor vagy szekvenciális outputfájl). Amikor a bemenő felsoroló adat aktuális elemét feldolgozzuk, e feldolgozás eredményeként

125


kapott új elemmel vagy elemekkel kibővítjük a kimenő adatot (halmazhoz hozzáuniózunk, sorozathoz hozzáfűzünk, stb.). Mivel a kimenő adat megváltoztatása (az unió, hozzáfűzés, stb.) egy baloldali egységelemes asszociatív művelet, ezen feladatok megoldását az összegzés programozási tételére vezethetjük vissza. Ha egy ilyen feladatra még az is igaz, hogy a bemenő adat egy elemének feldolgozása nem függ más tényezőtől (nem függ a bemenő adat többi elemétől vagy a kimenő adattól) csak magától a feldolgozandó elemtől, azaz a bemenő adat feldolgozása annak felsorolására épül, akkor a feladatot elemenként feldolgozhatónak, a megoldását elemenkénti feldolgozásnak nevezzük. (Létezik az elemenkénti feldolgozásnak egy ennél még szigorúbb értelmezése is, amely szerint az eddig felsorolt feltételeken túl annak is teljesülnie kell, hogy egy-egy elem feldolgozásának eredménye a kimenő adatot többi elemétől se függjön, azaz az eredménnyel a kimenő adatot annak többi elemétől függetlenül lehessen bővíteni.) Az elemenként feldolgozható feladat-osztályhoz tartozik az adatfeldolgozás számos alapfeladata: a másolás, a kiválogatás, a szétválogatás, stb. Oldjunk meg először két „szigorúan” elemenként feldolgozható feladatot, majd egy nem szigorú elemenkénti feldolgozásra, utána egy nem elemenkénti feldolgozásra is mutatunk példát. Utoljára egy olyan elemenkénti feldolgozásról lesz szó, ahol egy bemeneti gyűjteményből három kimeneti gyűjteményt kell egyszerre előállítani. 8.7. Példa. Másoljunk át egy karaktereket tartalmazó szekvenciális inputfájlt egy outputfájlba úgy, hogy minden karaktert megduplázunk! A = (x:infile(K), y:outfile(K)) Ef = ( x=x’) x'

Uf = ( y    x'i , x'i  ) i 1

Az utófeltételben használt  művelet az összefűzés (konkatenáció) jele. Ez egy asszociatív művelet, amelynek az üres sorozat az egységeleme. Ezért a feladat az összegzés programozási tételére visszavezethető úgy, hogy a feldolgozás egy szekvenciális inputfájlra, annak nevezetes bejárására épül. A szekvenciális outputfájlhoz a write művelettel lehet hozzáfűzni egy újabb sorozatot, azaz egy y := y  értékadást az y:write() implementál.

y:=<> sx,dx,x:read sx = norm y:write() sx,dx,x:read Látjuk, hogy az elemenkénti feldolgozható feladatok egy bemenő adat-elemhez nem feltétlenül csak egy kimenő adat-elemet állítanak elő, ugyanakkor nagyon gyakoriak azok a feladatok (ilyen a következő), amelyek a bemenő adat egy eleméhez vagy egy új elemet, vagy semmit sem rendelnek. 126


8.8. Példa. Válogassuk ki egy egész számokat tartalmazó halmazból a páros számokat, és helyezzük el őket egy másik halmazba! A feladat egy halmaz bejárásán értelmezett „összegzés”, ahol a feldolgozás f:Z2Z függvénye egy páros számhoz a számot tartalmazó egy elemű halmazt, páratlan számhoz az üres halmazt rendeli. A = (x:set(Z), y:set(Z)) Ef = ( x=x’) Uf = ( y  U {e} ) ex ' e páros

A programban szereplő y:=yf(e) értékadást egy elágazás valósítja meg. y:= x e:=mem(h) e páros y:=y{e}

SKIP

x:=x–{e} Megjegyezzük, hogy a szigorú elemenkénti feldolgozás következtében az y:=y{e}értékadás implementációja itt egyszerűbb, mint általában. Ugyanis biztosak lehetünk abban, hogy az e elem még nincs az y halmazban, ezért ezt nem is kell külön vizsgálni. Az elem-unió műveletének tehát ugyanúgy az egyszerűsített változatával dolgozhatunk itt, mint az x:=x–{e} elemkivonás esetében, ahol meg azt nem kell ellenőrizni, hogy az e elem tényleg benne van-e az x halmazban. 8.9. Példa. Másoljuk át egy egész számokat tartalmazó vektorból egy halmazba az elemek 7-tel vett osztási maradékait! A feladat egy vektor szokásos bejárásán értelmezett „összegzés”, ahol a feldolgozás függvénye az adott elemnek 7-tel vett osztási maradékát állítja elő, amelyet az eredmény halmazhoz kell uniózni. Ennek a lépésnek a hatása nem független az eredmény halmaz tartalmától, hiszen ha az újonnan hozzáadandó maradék már szerepel a halmazban, akkor a halmaz nem fog megváltozni. Ez a feladat tehát egy nem szigorú értelemben vett elemenkénti feldolgozás.

127


A = (x: Zn, y:set(Z)) Ef = ( x=x’) n

Uf = ( y  U{xi mod 7} ) i 1

y:= i:= 1 .. n y:=y{xi mod 7} Látható, hogy az y:=y{xi mod 7}művelet eredménye az y korábbi tartalmától függ: egy halmazban egy elem csak egyszer szerepelhet, ezért ha az xi szám osztási maradéka már szerepel y-ban, akkor a művelet nem változtatja meg y-t. Az  művelet ezért itt nem megkülönböztetett, mint az előző megoldásnál. (Érdekes viszont, hogy ha ugyanez a feladat az eredményt egy sorozatba tenné, akkor már szigorúan elemenként feldolgozhatóvá válna, hiszen sorozatoknál megengedjük, hogy abban ugyanaz az érték többször is előfordulhasson, így ugyanazt a maradékot többször is elhelyezhetjük.) Nem elemenként feldolgozható a következő feladat, ahol a feldolgozás alapjául szolgáló szekvenciális inputfájlból egy rekurzív függvény által előállított értékeket fűzünk egy outputfájlba. A rekurzív függvény értéke ugyanis természeténél fogva az előző értékeire támaszkodik. A megoldás előállítása viszont nem különbözik az előző feladatok megoldásaitól. 8.10. Példa. Másoljuk át a karaktereket egy szekvenciális inputfájlból egy outputfájlba úgy, hogy ott, ahol több szóköz követte egymást, csak egyetlen szóközt tartunk meg! A = (x:infile(K), y:outfile(K)) Ef = ( x=x’) x'

Uf = ( y   f 1 (i ) ) = ( y   f1 (i) ) i 1

x'

Az utófeltételben használt f1 függvény az x’ sorozat i-edik karakterét változtatás nélkül adja vissza, ha az nem szóköz, vagy olyan szóköz, ami közvetlenül egy nem-szóköz után áll. Ez a függvény az egyik komponense az f:[0..x’K*  L rekurzív függvénynek:

i  [1.. x ' ] : ( x 'i , hamis )  f (i )   (' ' , igaz )  ( , igaz ) 

ha ha ha

x 'i  ' ' x'i ' '  f 2 (i  1) x 'i ' '  f 2 (i  1)

f (0 )  ( , hamis ) A rekurzív függvényt közvetlenül a szekvenciális inputfájlból olvasott elemre is megfogalmazhatjuk: megmutatja, milyen sorozattá kell azt az elemet átalakítani. A megoldást egy olyan összegzésre (konkatenációra) vezetjük vissza, ahol egy szekvenciális inputfájl elemeit kell felsorolni, ezen elemeket egy rekurzív függvénnyel sorozattá alakítani, majd a

128


sorozatot az outputfájlba befűzni. A ciklusmagban megjelenő rekurzív függvényt a korábban (6.2 alfejezet) látott technikával bontjuk ki.

y, l:=<>, hamis

sx,dx,x:read

sx = norm dx’ ’

dx=’ ’  l

dx=’ ’  l

y:write(’ ’)

y:write(dx)

SKIP

l:= dx=’ ’ sx,dx,x:read A következő példa újra egy „szigorúan” elemenként feldolgozható feladat lesz, amelynek az a sajátossága, hogy ugyanazon a gyűjteményen több, egymástól független feldolgozást kell elvégezni. Az ilyen feladat teljesen önálló részfeladatokra bontható, majd a részmegoldásokat a közös gyűjtemény bejárására egyetlen ciklusba lehet összevonni. 8.11. Példa. Válogassunk szét egy szekvenciális inputfájlban rögzített bűnügyi nyilvántartásból egy sorozatba, egy outputfájlba, egy halmazba és egy vektorba a gyanúsítottakat aszerint, hogy az illető 180 cm-nél magasabb-e és barna hajú, vagy fekete hajú és 60 kg-nál könnyebb, vagy fekete hajú és nincs alibije! Az állapottérnek egy szekvenciális inputfájl a bemenő adata, a kimenő adatai pedig egy szekvenciális outputfájl, egy halmaz és egy vektor. Az állapottér a vektorról csak annyit mond, hogy az egy kellően hosszú véges sorozat, és majd az utófeltétel fogja a vektor első n elemét jellemezni. A specifikációban jól elkülönül a feladat három önállóan is megoldható része. A = (x:infile(Ember), y: outfile(Ember), z: set(Ember), v: Ember*, n:Z)) Ember=rec(név:K*,mag:N;súly:N,haj: K*,alibi:L) Ef = ( x=x’) Uf = ( y 

x'



i 1 x 'i .mag 180  x 'i .haj 'barna'

 x' i   z 

x'

U{x' } i

 v[1..n] 

i 1 x 'i . súly 60  x 'i .haj ' fekete '

x'



i 1 x 'i .haj ' fekete '  x 'i .alibi

 x'i  )

y:=<> sx,dx,x:read

z:= sx,dx,x:read

n:=0 sx,dx,x:read

sx = norm

sx = norm

sx = norm

dx.mag>180  dx.haj=’barna’

dx.súly<60  dx.haj=’fekete’

dx.haj=’fekete’ dx.alibi

y :write(dx) SKIP

z:=z{dx} SKIP

v[++n]:=dx SKIP

sx,dx,x:read

sx,dx,x:read

sx,dx,x:read

129


Összevonva: y:=<>; z:=; n:=0 sx,dx,x:read sx = norm dx.mag>180  dx.haj=’barna’ y:write(dx)

SKIP

dx.súly<60  dx.haj=’fekete’ z:=z{dx}

SKIP

dx.haj=’fekete’ dx.alibi n:=n+1; v[n]:=dx

SKIP

sx,dx,x:read A megoldás csak akkor hatékony, ha a szekvenciális inputfájl elemeit egyszer járjuk be. A három különálló megoldásból úgy készítettük el a feladat teljes megoldását, hogy a részfeladatokat megoldó ciklusokat egyetlen ciklusba vontuk össze (lásd 6.3 alfejezetbeli program-átalakításokat), és így a szekvenciális inputfájl minden elemét annyi szempont szerint dolgozunk fel, ahány kimenő adat van

130

8.6. Feladatok

8.6.

Feladatok

8.1.

Adott az egész számokat tartalmazó x vektor. Válogassuk ki az y sorozatba a vektor pozitív elemeit!

8.2.

Egy szekvenciális fájlban egy bank számlatulajdonosait tartjuk nyilván (azonosító, összeg) párok formájában. Adjuk meg annak az azonosítóját, akinek nincs tartozása, de a legkisebb a számlaegyenlege!

8.3.

Egy szekvenciális fájlban minden átutalási betétszámla tulajdonosáról nyilvántartjuk a nevét, címét, azonosítóját, és számlaegyenlegét (negatív, ha tartozik; pozitív, ha követel). Készítsünk két listát: írjuk ki egy output fájlba a hátralékkal rendelkezők, egy másikba a túlfizetéssel rendelkezők nevét és címét!

8.4.

Egy szekvenciális inputfájlban egyes kaktuszfajtákról ismerünk néhány adatot: név, őshaza, virágszín, méret. Válogassuk ki egy szekvenciális outputfájlba a mexikói, egy másikba a piros virágú, egy harmadikba a mexikói és piros virágú kaktuszokat!

8.5.

Egy kirándulás során bejárt útvonalon adott távolságonként mértük a tengerszint feletti magasságot (pozitív szám), és ezen értékeket egy szekvenciális inputfájlban rögzítettük. Azt az értéket, amelyik nagyobb az összes előzőnél, küszöbnek hívjuk. Hány küszöbbel találkoztunk a kirándulás során?

8.6.

Adott egy egész számokat tartalmazó szekvenciális inputfájl. Ha a fájl tartalmaz pozitív elemet, akkor keressük meg a fájl legnagyobb, különben a legkisebb elemét!

8.7.

Egy szekvenciális inputfájl (megengedett művelet: read) egy vállalat dolgozóinak adatait tartalmazza: név, munka típus (fizikai, adminisztratív, vezető), havi bér, család nagysága, túlóraszám. Válasszuk ki azoknak a fizikai dolgozóknak a nevét, akiknél a túlóraszám meghaladja a 20-at, és családtagok száma nagyobb 4-nél; adjuk meg a fizikai, adminisztratív, vezető beosztású dolgozók átlagos havi bérét!

8.8.

Az x szekvenciális inputfájl (megengedett művelet: read) egy vállalat dolgozóiról a következő adatokat tartalmazza: azonosító szám, vezető beosztásban van-e, legmagasabb iskolai végzettsége (1 ~ 8 általános, 2 ~ érettségi, 3 ~ főiskola, 4 ~ egyetem). Válasszuk ki a z sorozatban azoknak a dolgozóknak az adatait, akik vezető beosztásban vannak, de nem érettségiztek, és keressük meg a vezető beosztású legmagasabb iskolai végzettséggel rendelkező dolgozót is!

8.9.

Adott két vektorban egy angol-latin szótár: az egyik vektor i-edik eleme tartalmazza a másik vektor i-edik elemének jelentését. Válogassuk ki egy vektorba azokat az angol szavakat, amelyek szóalakja megegyezik a latin megfelelőjével.

8.10. Alakítsunk át egy magyar nyelvű szöveget távirati stílusúra!

131

8. Programozási tételek felsoroló típusokra

Recommend Documents