A program készítésének lépései
Amikor programot készítünk, akkor a program elkészítése az alábbi részfeladatokból áll:
1. Specifikáció = feladat meghatározása, mit kell megoldani?
2. Tervezés = hogyan kell a feladatot megoldani?
3. Kódolás = számítógépes megvalósítás, melynek eredménye a program.
4. Tesztelés = a program helyes működésének vizsgálata.
5. Hibakeresés, javítás (ha szükséges, akkor változtatás a 2.,3. pontnál).
6. Hatékonyság = minőség vizsgálat: gyorsabbá, kevesebb erőforrást használóvá alakítás.
7. Dokumentálás = Fejlesztői és felhasználói dokumentáció készítés.
A dokumentálás két elemét érdemes lenne még részekre bontani, de ez a tankönyv elsősor-
ban az első három ponttal foglalkozik, tekintsük át, hogy mit is jelentenek ezek!
Specifikáció (a feladat specifikációja)
A specifikáció (meghatározás) a következő összetevőkből áll:
1. A feladat szövege.
2. A bemenő adatok elnevezése (hogyan hivatkozunk majd rá), értékhalmaza (milyen
értékeket vehet fel).
3. A kimenő adatok elnevezése (amit eredményként várunk), értékhalmaza.
4. A bemenő adatokra vonatkozó előfeltétel (milyen megszorításnak kell megfelelnie).
5. A kimenő adatokra vonatkozó utófeltétel. Itt fogalmazzuk meg, hogy a bemenő ada-
tokból hogyan „keletkeznek” a kimenő adatok.
6. Fogalmak definíciója (az előző pontokban használat fogalmak meghatározása).
A specifikáció minden pontját matematikai eszközrendszerrel illik megadni, de ebben a
könyvben az egyszerűség kedvéért szövegesen fogom megadni.
Algoritmizálás (tervezés)
Az algoritmus egy feladat véges számú lépésre bontott megoldása. A lépések elemi műve-
letek (véges sok van belőlük), melyek utasítások formájában írhatók le, tehát található hoz-
zá olyan gép, ami végrehajtja. Az algoritmus lépései elemi tevékenységek (a végrehajtó
érti, vagy meg kell tanítani rá – ez újabb algoritmus).
Az algoritmusok legfontosabb jellemzője:
1. Egyértelmű: ugyanazon bemenő adatok esetén mindig ugyanazt a választ adja.
2. Véges számú lépésből áll: leírásuk véges hosszúságú szöveggel lehetséges. Termé-
szetesen ez nem jelenti azt, hogy a futása is véges idejű, bár erre törekszünk.
3. Általános: a bemenő adatokra megfogalmazott feltételeknek eleget tevő értékekre
eredményt ad.
2.1. Algoritmusok leírása
Az algoritmusokat szöveges, vagy rajzos eszközökkel adhatjuk meg. A teljesség igénye
nélkül vegyünk sorra néhányat!
2.1.1. Algoritmusok szöveges leírása
Az algoritmusok szöveges leírását minden diák használta már. Válasszunk egy egyszerű
matematika feladatot: Számold ki a háromszög területét, ha adott az egyik oldala és a hoz-
zá tartozó magasság!
Jelöljük az oldalt a-val, a magasságot m-mel, a területet t-vel. Ekkor a feladat megoldása
az alábbi képlet alkalmazását (kiszámítását) jelenti:
t=a*m/2
A kiszámítás menete (algoritmusa) szövegesen:
1. Szükségünk van a és m értékére (ezek az úgynevezett bemenő adatok), megkérdez-
zük azokat.
2. A t értéke legyen az a*m/2 műveletsor eredménye.
3. Közöljük az eredményt (ezt nevezzük kimenetnek).
Készíts algoritmust a következő számkitaláló játékra! Gondolj egy egész számot 0 és 100
között, és jelöld ezt g-vel. Aki ki akarja találni a számot, a következő módszer szerint jár
el:
A játékos mond egy számot (jelöljük ezt x-szel), te pedig megmondod, hogy a gondolt
szám ennél nagyobb, vagy kisebb. Ezt mindaddig ismétlitek, amíg a kérdező kitalálja a
gondolt számot!
A fenti játék algoritmusa szövegesen az alábbi:
1. Gondolj egy számot (ezt nevezem g-nek)!
2. Kérdezd meg társad tippjét!
3. Az általa mondott szám legyen x.
4. Hasonlítsd össze a két számot!
5. Ha g>x, akkor mondd: „A gondolt szám nagyobb.”
6. Ha g<x, akkor mondd: „A gondolt szám kisebb.”
7. Ha g=x, akkor mondd: „Eltaláltad.”
8. Ismételd a 2. ponttól addig, amíg g=x nem teljesül!
4
Ez az algoritmus már szinte minden lényeges algoritmus alapelemet tartalmaz. Tanulmá-
nyaink során strukturált programokat szeretnénk írni. Strukturált programnak nevezzük
azt a programot, mely csak az alábbi strukturált algoritmikus szerkezeteket tartalmazza:
− szekvencia,
− elágazás,
− ciklus.
A strukturált programok előnyeinek, illetve a nem strukturált programok hátrányainak is-
mertetése túlmutat eme könyv keretein, elégedjünk meg azzal, hogy a „jó” programok ké-
szítése érdekében mi mindig strukturáltat fogunk készíteni.
A programok alapelemei szövegesen
Most ismertetem, hogy az algoritmusok szöveges leírása során milyen elemeket szeretnék
felhasználni.
Egymásutániság (szekvencia)
Az utasítások egymás utáni végrehajtása.
Elágazás (szelekció) többféle lehet:
− Egy műveletsort csak egy feltétel teljesülésekor kell végrehajtani (ilyen van a pél-
dában). Szokták ezt feltételes utasításnak is nevezni.
− Két műveletsor közül az egyiket akkor kell végrehajtani amikor a feltétel igaz, míg
a másikat akkor, ha a feltétel hamis. Például: Ha süt a Nap strandra megyünk, ha
nem, akkor moziba. Ezt nevezzük kétágú elágazásnak, esetleg röviden elágazás-
nak. Az előző típus is felfogható úgy, hogy hamis feltétel esetén nem tartalmaz uta-
sítást az elágazás (pontosabban üres utasítást tartalmaz).
− Kettőnél több műveletsor közül kell választani, általában egy kifejezés kiértékelése
alapján. Például: Ha a Balaton vízmélysége kisebb, mint 1 méter, akkor pancsolunk
benne, ha a vízmélység 1 és 2 m közötti, akkor úszunk, ha mélyebb, mint két méter,
akkor nem megyünk be. Ezt nevezik többágú, vagy sokágú elágazásnak. Gyakran
az ilyen többágú elágazásnak van „egyébként” része, mely akkor hajtódik végre, ha
egyik feltétel sem igaz. Megállapodás kérdése, hogy a többágú elágazás végrehajtá-
sa során igaz feltételt találva tovább folytatjuk-e a feltételek kiértékelését, vagy
nem.
Ismétlés (iteráció)
Egy feltétel fennállásáig, vagy megadott számszor ismételjük a felsorolt utasításokat, ami-
ket ciklusmagnak nevezünk. A ciklusmag nem más, mint a többször végrehajtandó utasí-
tások sorozata.
Az ismétlésnek három típusát különböztetjük meg:
Elöltesztelő ciklus:
A feltétel vizsgálata a ciklusmag előtt található, a ciklusmag csak akkor hajtódik végre, ha
a feltétel igaz. Például: Amíg van pénzed, vásárolj! Ha nincs pénzed, akkor egyszer sem
vásárolsz (praktikus megoldás).
Algoritmizálás (tervezés)
Algoritmusok leírása
Hátultesztelő ciklus:
A feltétel vizsgálata a ciklusmag után található, ezért a ciklusmag egyszer biztosan végre-
hajtódik. Például: Ismételd a tapsolást, amíg nem fáj a kezed! Pontosabban: Tapsolj, és
ismételd amíg nem fáj a kezed! (Egyszer mindenképpen tapsolsz.)
Számláló ciklus:
A ciklusmag végrehajtása előre ismert mennyiségben.
Például: Ismételd 5-ször: Vágj egy szelet kenyeret!
Másik példa: Ismételd 1-től 5 „darab”-ig: Süss ki egy palacsintát! (Először a darab=1, ki-
sütsz 1 palacsintát, a darabszám 2 lesz, kisütsz még 1 palacsintát…). Az ismétlésszám
megadásánál olyan mennyiséget használhatsz, amelyiknél a „következő” fogalma értelme-
zett. Lehet tehát egész szám például, de nem lehet valós szám.
Láthattuk, hogy a mondatokkal történő leírás kellemesen használható, de hátránya, hogy
hosszadalmas, erősen nyelvfüggő és nem mindig egyértelmű.
Algoritmusok leírása mondatszerű elemekkel
A módszer lényege, hogy az algoritmusokban használatos alapelemekre szabványos szö-
vegelemeket vezetünk be. A mondatszerű leírás alapszerkezetei megegyeznek a strukturált
programok alapszerkezeteivel, kiegészítve néhány „kényelmi” elemmel.
Már itt érdemes megemlíteni két fogalmat, melyek elsősorban a programozási nyelvekhez
kötődnek, de már az algoritmus leírásnál is értelmezhetők:
A szintaxis a formai szabályok gyűjteménye (hogyan kell leírni).
A szemantika a tartalmi helyességet leíró szabályok összessége (mi a jelentése, mit kell
értenünk alatta).
Folyamatábra építőelemei
Nézzünk konkrét példát rá: Két szám szorzata!
Következő példa: Készítsük el a pozitív egész számok szorzásának algoritmusát (a szorzást ismételt össze-
adásra visszavezetve)!
Eddig az algoritmusokat természetes emberi nyelven megfogalmazott, számozott mondatokkal írtuk le. A mondatok egyértelmű és egyszerű tevékenységeket írtak le. Alap esetben a számozás határozta meg végrehajtás sorrendjét. Ebben a fejezetben egy új, széles körben ismert megjelenítési technikával, az úgynevezett folyamatábrával fogunk megismerkedni.
Alapelemek
A folyamatábra nem más, mint algoritmusok grafikus megjelenítése. Az egyes elemi lépéseket alakzatok segítségével jelenítjük meg, majd ezeket nyilakkal kötjük össze, amelyek meghatározzák az egyes tevékenységek végrehatásának sorrendjét. A különböző jellegű tevékenységekhez különböző alakzatok tartoznak.
Start- és Vége szimbólum: Ezek az ellipszis alakzatok határozzák meg azt, hogy hol kell elkezdenünk az algoritmus végrehajtását, illetve azt, hogy mikor értük el a lépéssorozat végét. A Start szimbólumból maximum egy lehet egy folyamatábrában. Csak egyetlen kifelé irányuló nyíl indulhat ki belőle és befelé irányuló nyíl nem kapcsolódhat hozzá. A Vége szimbólumból több is szerepelhet egy folyamatábrában, mindig elegendő pontosan egy végjel. Egy vagy több nyíl is mutathat irányába, viszont nem indulhat ki belőle egy sem.
Start- és Vége szimbólum
Elemi tevékenység: Egy téglalap alakzatban szereplő egyszerű és egyértelmű lépés, amely nem igényel további magyarázatot. Az alábbi ábrán szereplő tevékenység például egy értékadás, ami azt jelenti, hogy az X nevű mennyiség (más néven változó) értéke legyen innentől kezdve 1. Egy vagy több bemenő nyíl és pontosan egy kimenő nyíl tartozhat hozzá.
Elemi lépés
Input- és Output szimbólum: A legtöbb algoritmusnak szüksége van valamiféle bemeneti adatra. Ezt általában a felhasználó a végrehajtás során fogja csak megadni és ezt az értéket fogja az algoritmus felhasználni (hasonlóképpen, mint az általánosítást bemutató példában). A kapott érték mindig eltárolásra kerül az alakzatban megadott nevű mennyiségben. Máskor az algoritmus egy eredményt szolgáltat, közölni szeretne valamit a felhasználóval. A kimenet lehet például egy mennyiség értéke (mint a lenti példában), másrészt lehet egy egyszerű szöveg, mint például a „Szia!” üzenet. A szövegkonstansok mindig macskakörömben szerepelnek, így tudjuk őket megkülönböztetni a mennyiségnevektől. Ezekből a szimbólumokból csak egy nyíl mutathat kifelé.
Input- és Output szimbólum
Feltétel szimbólum: A folyamatábrák legösszetettebb szerkezetű és működésű eleme. Egy csúcsára állított rombuszban egy állítás szerepelhet. Az állítás egy logikai kifejezés, amely vagy igaz, vagy hamis kell kegyen. Miután kiértékeltük ezt a feltételt, azaz meghatároztuk az igazságtartalmát két lehetőség közül választhatunk. Ha a feltétel igaz, akkor amentén a nyíl mentén kell folytatnunk a végrehajtást, amely felé az igaz (esetleg az igen) szó van írva. Ha az állításról kiderül, hogy hamis, akkor a hamis (esetleg a nem) címkével ellátott nyíl mentén kell tovább haladnunk. Tehát a rombuszból mindig két felcímkézett nyíl mutat kifelé az oldalán.
Feltétel szimbólum
Beágyazás szimbólum: Előfordul, hogy egy folyamatábrában alkalmaznunk kell egy alapvetően több lépésből álló utasítássorozatot. Ha azt már korábban definiáltuk, leírtuk, de most nem szeretnénk ezt újra megtenni, akkor használhatjuk a dupla oldalú téglalap alakzatot a beágyazás szimbólumaként. Ezzel valósíthatjuk meg a korábban tárgyalt egyik algoritmus módosítási módszert. Az alábbi ábrán azt láthatjuk, hogy ki szeretnénk számolni az x mennyiség N. hatványát, ami alapvetően egy számos lépést tartalmazó tevékenység, de itt most csak hivatkozunk erre a korábban valószínűleg már leírt algoritmusra, mint egyfajta új elemi lépésre. A beágyazás szimbólumhoz kapcsolódó nyilakról ugyanazt mondhatjuk el, mint az elemi tevékenység esetén.
Beágyazás szimbólum
Bizonyos elemek esetén tehát előfordulhat, hogy több mint egy befelé mutató nyíl kapcsolódik hozzájuk. Ilyen esetben használhatjuk azt a jelölést, amikor az alakzat felé tartó nyilak egy pontban találkoznak és innen már csak egyetlen nyíl halad tovább az adott alakzat felé. (Később számos példát látunk majd rá.)
Az algoritmus alapszerkezetei folyamatábra esetén
Természetesen az algoritmusok három alapszerkezete folyamatábra segítségével is leírható. A szekvencia itt nyilakkal összefűzött tevékenységeket jelent. A nyilak egyértelműen meghatározzák a végrehajtás sorrendjét, mert összefűzésükkel csak egyetlen útvonal jön létre. Egy alakzatból csak akkor mehetünk tovább a nyíl mentén, ha az adott tevékenységet maradéktalanul végrehajtottuk. A tevékenységeket nem szükségszerű fentről lefelé vagy balról jobbra elhelyezni, mivel úgyis a nyilak határozzák meg az egymáshoz való viszonyukat.
Az elágazás egy feltétel segítségével valósítható meg. A rombuszt elhagyó nyilak egy-egy tevékenységre vagy tevékenységcsoportra mutatnak. Viszont ezek felírása után a két ágnak egyesülnie kell, azaz két nyíl egy pontban találkozik és egybeolvadva halad tovább. Az értelmezés a következő. Amikor elérkezel egy feltételhez, ki kell értékelni a rombuszban lévő logikai kifejezést. Ha ez a feltétel teljesül, haladj tovább az igaz ágon és hajtsd végre az ott található utasításokat és miután elérted a nyilak találkozási pontját, folytasd az elágazás utáni következő tevékenységgel! Ellenben ha a feltétel nem teljesül folytasd a hamis ág mentén a végrehajtást, majd végül ebben az esetben is az elágazás utáni utasításra kerül a sor. Tehát a két ág közül pontosan az egyik hajtódik végre (a feltételtől függően). Bármelyik ágról is legyen szó, minden esetben a végrehajtás ugyanúgy folytatódik. Néha a kétirányú elágazás egy speciális esete válik szükségessé, amikor az egyik ág egyetlen tevékenységet sem tartalmaz. Ez tehát azt jelenti, hogy vagy végrehajtunk egy lépést vagy kihagyjuk azt. A későbbiekre való tekintettel célszerű, ha a kihagyható tevékenység az igaz ágban helyezkedik el és így a hamis ág üres lesz (egyetlen nyíl a találkozási ponthoz).
Az ismétlések is feltétel segítségével írhatóak le. A feltételt tartalmazó rombuszból kiinduló egyik tevékenységsorozat ebben az esetben olyan, hogy előbb-utóbb a sorrendet jelentő nyilak mentén visszajutunk a már korábban is érintett feltételhez. Tehát egy hurok alakul ki. A feltétel másik oldalán ilyet nem találunk. A végrehajtás szempontjából tehát először kiértékelődik a feltétel. Ettől függően vagy belépünk a ciklusba, végrehajtjuk az ott található utasításokat, majd újra kiértékeljük a feltételt vagy egyszerűen a másik irányban haladunk tovább. Egyelőre magyarázat nélkül fogadjuk el, hogy a ciklusmag, vagyis az ismétlendő utasítások mindig a feltétel igaz oldalán helyezkednek el. Röviden tehát azt mondhatjuk, hogy az ismétlés addig történik, amíg a feltétel igaz és amint hamisnak bizonyul tovább lépünk. Fontos megjegyezni, hogy az ismétlendő utasítások hatással kell, legyenek a feltételre, ha ugyanis ez nem teljesül, akkor a feltétel mindig igaz marad, azaz sohasem lépünk ki a ciklusból. Egy algoritmusnak azonban végesnek kell lennie.
Alapszerkezetek folyamatábrával
Mit ábrázol ez a folyamatábra?
.
Az elágazás esetén a Tevékenység B azért van szürke színnel feltüntetve, mert a megbeszéltek szerint ez az ág lehet üres, azaz a tevékenység kihagyható. Mint látható az elágazás és az ismétlés is tartalmaz feltételt. Azonban könnyű őket elkülöníteni, ha figyelembe vesszük, hogy elágazás esetén a végrehajtás két ága később mindig összetalálkozik, míg ismétlés esetén ez nem történik meg, de az egyik ágon mindig visszajutunk az feltétel elé.
Nincsenek megjegyzések:
Megjegyzés küldése