Sorozat érték típusú programozási tételek
A soron következő specifikációk és algoritmusok mind olyan típusfeladatokhoz kötődnek, amik igazán sűrűn előfordulhatnak a gyakorlatban. Meg kell keresni valamit, meg kell számlálni valamit egy gyűjteményben, stb. Jó, ha ezek megoldására vannak általános receptjeink, amiket könnyen aktualizálhatunk a konkrét feladat elvárásainak megfelelően. Éppen ezért ezeket a feladatokat elég absztraktul, általánosan fogjuk megfogalmazni, hogy minél több esetre rá lehessen húzni azokat egyszerű megfeleltetésekkel. Például ha képes vagyok egy „valamilyen” tulajdonságú elemet megtalálni egy „valamilyen” elemeket tartalmazó „valamilyen” struktúrájú gyűjteményben, akkor egy páros számot is meg fogok tudni keresni egy egészeket tartalmazó tömbben. Ez még nem a végállomás, a következő félévben, Programozás tárgyból még eggyel absztraktabb formában fogjuk a tételeket tanulni… aki meg B szakirányos lesz, annak progmódból még erre is rátesznek majd egy lapáttal… de túl lehet élni A következőkben tárgyalt tételek nagyon hasonló kaptafára készültek, közös bennük, hogy a bemenő adatuk mindig egy „sorozat” (a gyakorlatban ez tömb szokott lenni), általában külön bemenő változóként fel szoktuk tüntetni ennek a sorozatnak az elemszámát (ez összhangban van azzal, ahogy ezt ebben a félévben kódolni fogjuk), az eredmény pedig egy egyszerűbb érték lesz: egy szám, egy igaz-hamis érték, a bemeneti tömb egy eleme, netán annak az indexe… Nem feltétlen lesz minden tétel szóról szóra úgy leírva, mint az előadás-diákon. Pluszmínuszban elfogadok mindent, ami a tétel lényegét visszaadja. Pirossal jelölöm a tételeket magukat, feketével magyarázó szövegeket és példákat írtam. Összegzés Van egy sorozatunk, amiben valamilyen „összegezhető” típusú elemek vannak. Például egy tömb egész számokkal. A feladat az, hogy végezzük el ezt az összegzést. Például a [ 1, 2, 3 ] tömb esetén a 6-os számot szeretnénk válaszként előállítani. Persze nem feltétlenül csak tömbön lehet összegezni és az a bizonyos összegző művelet is lehet nyugodtan szorzás, vagy bármi más. Például lehetnek a bemeneti sorozatban stringek. Például: [ szereti, a, tik, a, meggyet ], szeretnénk ebből egy értelmes „mondatot” előállítani, tehát összefűzni (konkatenálni) a stringeket. Ezt a feladatot is ezzel a programozási tétellel szokás megoldani. Gyakorlatilag tetszőleges asszociatív, semleges elemes műveletvégzést rá lehet húzni erre a sémára, amikor nem számokat összegzünk (szummázunk – Σ), akkor szeretjük ezt a tételt úgy hívni, hogy „sorozatszámítás”. De a lényege ugyanaz.
Specifikáció: Be: ([
] )
Ki:
Ef:
Uf: ∑ [] Tehát van egy tömbünk, ami N elemből áll, N természetes szám, szóval legalább 0 (a tétel teljesen értelmesen működik 0 elemű tömbre is: 0-t ad vissza), a választ pedig S változóba fogjuk kapni, ami olyan típusú, mint a tömbelemek, hiszen a válasz a tömbelemek összege. Algoritmus:
[] Példa: Szorozzuk össze egy tömb elemeit! Be: ([
] )
Ki:
Ef:
Uf: ∏ []
[] A művelet és így az egységelem változott, ezen kívül minden ugyanaz.
Egy kicsit extrémebb példa sorozatszámításra: Döntsük el, hogy egy tömb minden eleme páros-e! Be: ([
] )
Ki:
Ef:
Uf: ⋀
( [ ])
( [ ]) Az ilyesfajta feladatokat hatékonysági okokból (na meg a józan paraszti eszünk sugallatára) az eldöntés tétellel fogjuk megoldani, de láthatjuk, hogy az összegzés, vagyis sorozatszámítás logikája is mennyire áll rá: fogunk egy kezdeti értéket (éselésnél ez az „igaz” érték, a felfele mutató nyíl ezt jelenti), majd a kimeneti változóba (L) folyamatosan ismételve a műveletet gyűjtjük a választ. Érdemes megfigyelni, hogy amikor a ciklus az I=K értéknél tart (ahol K valahol 1 és N között van), akkor K-ig már igaz az utófeltétel állítása: L akkor igaz, ha K-ig minden X[i] páros volt, és akkor hamis, ha K-ig legalább egy hamis volt. Ha K eléri N-t, akkor az utófeltétel is igazzá vált, a program leállhat. Azért itt fontos látni, hogy jócskán általánosabb ez a sorozatszámítás a sima mezei összegzésnél. Itt nemcsak a műveletet meg az egységelemet cseréltük le, hanem ellentétben az előző példával nem az X tömb elemein végeztük a műveletet, hanem egy függvényen (páros()), ami amúgy már az X tömb elemein van értelmezve. Ezzel összefüggésben az eredmény változónk (L) típusa se feltétlenül lesz azonos a bemeneti tömb elemeinek típusával, mivel a páros() függvény képe logikai értékekből áll, az eredmény változó is logikai lesz. Persze a sorozatszámításnál az se elvárás, hogy a tömbben egész számok legyenek.
Megszámolás Most azt kell megmondanunk, egy adott tömbben hány elemre igaz egy bizonyos igazhamis értéket felvevő tulajdonság. Az eredmény típusa itt garantáltan egy szám lesz, a tömb megint csak lehet üres (ekkor ez a szám 0), viszont van még egy logikai függvényünk valahol, egy „tulajdonság”, aminek a meglétét vizsgáljuk. Ez a függvény nem az állapottér része, hiszen nem egy be- vagy kimenő adat, amit változókkal meg tudnánk fogni, de azért valahol meg kell emlékezni róla, hogy létezik. Ezt így szoktuk megadni: Specifikáció: Adott:
Be: ([
]
)
Ki:
Ef:
Uf: ∑ ( [ ])
Ez egy feltételes összegzés, azaz akkor adom össze az „egyeket”, ha a feltétel a szumma alatt az aktuális elemre teljesül. Azaz, annyi egyest fog összeadni, ahány T tulajdonságú elem van, azaz meg fogja számlálni a T tulajdonságú elemeket. A „Valami” típus a tömb elemeinek típusa, ami tetszőleges. Persze, attól még hogy tetszőleges, a specifikációban előforduló összes „Valami” ugyanazt a valamit, ugyanazt a típust jelenti! Algoritmus:
( [ ])
Az algoritmus nem túl bonyolult, kiindulunk abból, hogy egy elemre se igaz a tulajdonság, aztán ha az I-edik elemre mégis igaz, akkor a számlálót növeljük. És ez így megy, amíg végig nem néztünk minden elemet. Egyébként ezt a tételt vissza lehet vezetni a sorozatszámításra.
Példa: Állapítsuk meg, hány darab három fejű van egy kastély sárkányai között! Be: ([ Ki:
Ef:
Uf: ∑ []
[]
]
)
Maximumkiválasztás A kérdés az, hogy egy rendezési relációval rendelkező típusú elemeket tartalmazó tömbnek mi a legnagyobb eleme a rendezési reláció szerint. Lehet úgy általánosítani, hogy mi a legkisebb eleme (igazából egy kacsacsőrt kell csak átírtni), valamint úgy, hogy nem a legnagyobb elemet adom vissza, hanem az indexét a tömbben. Esetleg mind az elemet, mind az indexet. Miért jó, ha az indexet adom vissza? Képzeljük el, hogy a tömbben emberek vannak, engem meg a legmagasabb ember neve érdekel. Ekkor lefuttatjuk a maximumkeresést magasság szerint, majd ha nem az indexszel, hanem a magassággal térünk vissza, abból már csak nehezen tudjuk visszakeresni a nevet. De ha az indexszel, akkor egyszerűen csak lekérdezzük a tömb annyiadik elemének a nevét. A következőkben épp ezért az indexszel visszatérős változatot adom meg: Specifikáció: Be: ]
([
)
Ki:
Ef:
Uf: [
]
[
]
[]
[
]
Na, itt van előfeltétel! Mert ezt a tételt csak olyan esetben lehet használni, amikor tudjuk biztosan, hogy van maximum. Mikor van maximum? Ha van legalább egy elem a tömbben. Ha viszont több maximum is van, akkor ez csak az egyikkel fog tudni visszatérni. A specifikáció ugyan ezt nem köti ki, de az alábbi megoldó program úgy működik, hogy a maximumérték első előfordulását őrzi meg maximumként. Az utófeltétel azt mondja ki, hogy a visszatérési sorszám legyen egy értelmes index ([1..N]-beli), és a tömb minden eleme legyen kisebb vagy egyenlő, mint ez az Ind indexű elem. Az egyenlőséget azért engedjük meg, mert egyrészt több maximum elem is lehet, másrészt, ha csak egy van, akkor is igaz az, hogy ő is benne van az [1..N] intervallumban, tehát az univerzális kvantor utáni i felveszi értékül Ind-et is. Innentől kezdve pedig nem mondhatjuk, hogy X[Ind] > X[i], hiszen lehet, hogy épp azonos a Ind és i.
[ ]
[
]
Az algoritmus először felteszi, hogy az első elem a helyes megoldás (ezért fontos az előfeltétel, hogy létezik ez az első elem), majd egyesével megvizsgálja a többit (ezért indul a ciklus 2-től), hogy esetleg nagyobb-e mint az eddigi maximum. A végén így Indben a legnagyobb elem indexe lesz. A példa legyen egy minimumkeresés. Adjuk meg az indexét és a magasságát is a legkisebb ugrifülesnek! Be: ]
([
)
Ki:
Ef:
Uf: [
] [ ]
[ ] [ ]
[
]
[
]
[
]
[]
Eldöntés Azt szeretnénk megtudni, van-e T tulajdonságú elem, de arra nem vagyunk kíváncsiak, ha van, melyik az, esetleg melyikek azok. Specifikáció: Adott:
Be: ]
([
)
Ki:
Ef:
Uf: (
[
]
( [ ]))
A T egy „Valami”-n értelmezett logikai függvény, a tömb elemtípusa pedig épp „Valami”, szóval végig tudjuk járni a tömböt, megvizsgálva, hogy az adott eleme rendelkezik-e T tulajdonsággal. Persze nem kell feltétlenül végigmenni. Azt szeretnénk tudni, van-e ilyen, az első találatnál meg is állhatunk, szóval elég addig menni, amíg még nincs meg az első T tulajdonságú. Ha végigmentünk sikertelenül, akkor hamis, ha valahol idő előtt „elakadtunk”, akkor igaz az eredmény. Éppen ezért ez a ciklus nem számlálós (for), hiszen nem garantált lépésszámszor fut le a ciklusmag, hanem egy feltétel beálltáig. Algoritmus: ( [ ])
A legvégén onnan tudjuk, hogy volt-e találat, hogy nem amiatt álltunk-e meg, mert I túlfutott N-en, hanem mert igaz lett a T tulajdonság az I-edik elemre. Érdemes még meggondolni mi a helyzet üres tömb esetén. I az elején felveszi az 1-es értéket, majd N=0 miatt be se lépünk a ciklusba. A végén mivel I>N, ezért Van hamis lesz, és valóban: ha üres a tömb, biztos nincs is benne T típusú elem.
Példa: Diogenész ókori görög filozófus fényes nappal kezében lámpással az utcát rótta, ugyanis „embert keresett”. Segítsünk neki eldönteni, hogy van-e. Be: ]
([
)
Ki:
Ef:
Uf: [ (
]
[ ])
(
[ ])
Meg lehet fordítani a gondolkodásmódot, és azt vizsgálni, vajon minden elemre igaz-e a tulajdonság. Ekkor a struktogram alakja hasonló lesz, csak most nem az első pozitív példánál, hanem az első cáfolatnál állunk meg. Példa: Igaz-e, hogy mindenki függ? Be: ]
([
)
Ki:
Ef:
Uf: [ (
]
(
[ ])
[ ])
Azért fordult a kacsacsőr az utolsó sorban, mert most nem akkor van „jó” ha megtaláltuk a példát, hanem akkor, ha nem találtuk meg az ellenpéldát. Azaz végigmentünk úgy a tömbön, hogy mindenki függött. Valamitől. Üres tömbnél igazzal fog visszatérni, ahogy ezt a matematikai logikában megszokhattuk.
Kiválasztás Tegyük fel, hogy van T tulajdonságú elem, válasszunk ki egy ilyet! Itt is azt a verziót adom meg, ami nem az elemmel, hanem az indexével tér vissza. Specifikáció: Adott:
Be: ]
([
)
Ki:
Ef: [
]
( [ ])
]
( [
])
Uf: [
Előfeltétel itt kiköti, hogy a tömb nem üres, és akad benne T tulajdonságú. Algoritmus: ( [ ])
Egyszerű algoritmus, kicsit furcsa, hogy nem ellenőrizzük, hogy mikor lépjük túl az intervallum felső határát, azaz mikor lesz I>N. Miért nem kell ezt ellenőrizni? Azért, mert az előfeltételben kikötöttük, hogy létezik olyan elem, amit itt keresünk… ezért biztosan tudjuk, hogy ez a ciklus még I=N+1 előtt valahol garantáltan megáll, ezt tehát nem kell külön vizsgálni. Példa: Tesi órán valamelyik gyerek betörte az iskola ablakát egy célt tévesztett focilabdával. Keressük meg a bűnöst… Be: ([ Ki:
]
)
Ef: [
]
[ ])
(
Uf: [ (
]
[
(
])
[ ])
Tudjuk, hogy ezek a kereső módszerek mindig az első T tulajdonságú elemet találják meg. Most csakazértis keressünk meg egy utolsó elemet. Példa: Keressük meg az utolsó mohikánt, ha tudjuk, hogy van ilyen! Az ötlet az, hogy a kiválasztás tételt úgy alakítjuk át, hogy nem előröl hátrafelé, hanem hátulról előrefelé fogunk haladni, amúgy mást nem változtatunk: Be: ]
([
)
Ki:
Ef: [
]
[]
Uf: [ [
]
[ ]
Tehát Csingacsguk után már nincs több mohikán. [ ]
] []
Keresés Az előző kettő tétel szupererejének ötvözetéből született. Adott egy tömb, nem tudjuk, hogy van-e benne T tulajdonságú elem, meg kéne vizsgálni, hogy van-e, és ha van, akkor vissza kéne térni az egyikkel. Amúgy ez az algoritmus, ahogy megszokhattuk, az első ilyennel fog. Következő félévben ez lesz majd a lineáris keresés, azért lineáris, mert potenciálisan egyesével végigmegy az egész tömbön, ezért műveletigénye (lépésszáma) a tömb méretével lineárisan arányos (lesz majd ennél hatékonyabb keresés is). Specifikáció: Adott:
Be: ]
([
)
Ki:
Ef:
Uf: (
[
]
( [ ]))
(
[
]
( [
]))
Tehát most két változóval térünk vissza, a Van mondja meg, hogy … van-e T tulajdonságú, és ha van, akkor az Ind mondja meg, hogy ki az. Ha nincs T tulajdonságú, akkor az Ind értéke nem érdekes, definiálatlan. Algoritmus: ( [ ])
A struktogram nem nehéz, előbb lefuttatunk egy eldöntést, majd ha arra jutottunk, hogy Van, akkor onnan végül is tudjuk, hogy ki a talált elem: az, ahol megállt az eldöntés ciklusa. Tehát az I.
Példa: Adott egy kamion, benne a rakomány. A rendőrség sajnos kifogyott már a cuccból, szóval segítsük a drogkereső kutya munkáját, mert már nagyon lapos a hangulat az őrsön. Be: ([
]
)
Ki:
Ef:
Uf: [ ( (
] (
[ ]))
( [
[ ])
]
(
[
]))
