1. Algoritmusok
A mindennapi életben gyakran kerülünk olyan helyzetbe,
amikor meglévő ismereteink alapján nem tudjuk azonnal megmon-
dani, hogy elérhető-e kitűzött célunk, illetve, ha igen, ho-
gyan: problémahelyzetbe kerültünk. A megoldás két dolgot je-
lent: az eredmény (azaz elvárásaink) pontos ismeretét és an-
nak a folyamatnak tervét, amely az eredmény létrehozásáig el-
vezet. A cél elérésének érdekében megtervezzük az elvégzendő
cselekvéseink sorozatát, ügyelve arra, hogy bármilyen közbül-
ső 'állapotba' jutva a cél elérhető legyen ('célirányban' ma-
radjunk). E tevékenységünket hívják algoritmuskészítésnek.
Olyan problémamegoldó eljárást (algoritmust) kell konstruál-
nunk, amely véges számú lépésben befejeződik, a bemenő ada-
tokból előállítja a kimenő adato(ka)t, azaz megoldja a fela-
datot.
Amikor a számítógépnek kell megmondanunk, hogy mit csinál-
jon, akkor nem elégedhetünk meg a hétköznapi élet megkívánta
algoritmusok precizitásával: pontosabb, egyértelműbb leírást
kell adnunk úgy, hogy gépünk számára is követhető legyen el-
képzelésünk (neki nincsenek beleérzései, intuiciói, csak a
leírtakra támaszkodhat)!
Az első fejezetben megpróbálunk mintát adni arra, hogy
hétköznapi tevékenységeink algoritmizálásától hogyan lehet
fokozatosan eljutnunk olyan algoritmusokhoz, amelyek -szinte
minden kódolás nélkül- lefuttathatók az ELAN programozási
nyelven.
Természetesen csak ötletek adására vállalkozhatunk; java-
soljuk, mindenki saját életéből keressen további 'testre sza-
bott' feladatot.
Ajánlott irodalom:
1. J. Hvorecky - J. Kelemen: Ötlettől az algoritmusig.
Tankönyvkiadó, 1987.
2. C.H.A. Koster: Programozás felülnézetben.
Műszaki Könyvkiadó, 1988.
3. Lovász L. - Gács P.: Algoritmusok.
Műszaki Könyvkiadó, 1987.
1.1 Hétköznapi algoritmusok
Ebben a részben nyugodtan engedjük szabadon fantáziánkat.
Csak arra kell törekednünk, hogy a feladat leírása áttekint-
hető, világos legyen! Próbáljunk meg minden tevékenységet
(utasítást) külön-külön sorba írni! A megoldó algoritmusok
csupán nagy vonalakban hasonlítsanak arra, amit később algo-
ritmusnak (programnak) nevezünk!
1.2 Általános robotmodell
A számítógép szerepébe egy XXI. századi szerkezetet kép-
zelünk, amely roppant intelligens, így kevés utasítással
is könnyen irányítható. Utasításkészlete a feladathoz rugal-
masan alakítható. Előnye, hogy 'eljátszható', vagyis ha va-
lakit kinevezünk robotnak, akkor kipróbálhatjuk algoritmusa-
ink helyességét (esetleg még hatékonyságát is).
A robotot egyszerű -magyar nyelvű- utasításokkal vezérel-
hetjük. Ilyenek a LÉPJ, a FORDULJ, a MONDD, a KÉRDEZD, TEDD.
Lehetőség van összetett utasítások definiálására: ISMÉTELD
n-SZER; ISMÉTELD AMÍG; ISMÉTLÉS VÉGE; HA feltétel AKKOR te-
vékenység1 KÜLÖNBEN tevékenység2. Jól látható, hogy a robot
utasításai megfelelnek az algoritmusleíró nyelvben használt
utasításoknak.
A robot ismer néhány speciális változót, ilyen például a
VÁLASZ. Ebben mindig a legutolsó kérdésre adott válasz talál-
ható. A robot ugyanúgy használhat változókat, mint ahogyan az
algoritmusleíró nyelvben használunk.
A robot egy lehetséges kezdő-utasításkészlete, amely tet-
szés szerint bővíthető!
LÉPJ Egy lépés előre.
FORDULJ ...-RA ... FOKOT Jobbra- vagy balrafordulás.
NÉZZ A LTVNY nevű változó értékadó
utasítása (a robot pillanatfel-
vételt készít a szemként működő
kamera segítségével, s a képet
tárolja).
MONDD(...) A zárójelben lévő szöveget vagy
számot kimondja
KÉRDEZD (...) A VLASZ nevű változó értékadó
utasítása (fülként működő mikro-
fon segitségével az érzékelt
hangokat tárolja).
TEDD ...-BA ...-OT Értékadó utasítás.
ISMÉTELD ...-SZOR Ciklusszervező utasítás.
...
ISMÉTLÉS VÉGE
ISMÉTELD AMG ... Ciklusszervező utasítás.
...
ISMÉTLÉS VÉGE
ISMÉTELD Ciklusszervező utasítás.
...
AMG ...
ISMÉTLÉS VÉGE
HA ... Elágazás.
AKKOR ...
KÜLÖNBEN ...
stb.
Kezdetben csak néhány egyszerű utasítást használjunk és az
újabbakat csak fokozatosan, egy-egy feladaton keresztül ve-
zessük be.
1.3 Karesz: a robot
Karesz, a robot egy egyszerű, algoritmikus világban él,
sík vidéken. Idejét az utcán tölti.
Karesz C.H.A. Koster 'Programozás felülnézetben' című
könyvében szerepel, tulajdonságainak leírását onnan vesszük
át.
A következő ábra a 12. út és a 9. utca sarkán mutatja őt,
orral kelet felé.
17 . . . . . . . . . . . . . . . .
16 . . . . . . . . . . . . . . . .
15 . . . . . . . . X X X X X X X .
14 . . . . . . . . X . . . . . X .
13 . . . . . . . . X . o . . . X .
12 . . . . . . . . X . . . . . X .
11 . . . . . . . . X . . X X X X .
10 . . . . . . . . . . . . . . . .
9 . . . . . . . . . . . > . . . .
8 . . . . . . . . . . . . . . . .
7 . . X X X . . . . . . . . . . .
6 . . . . X . . . . . . . . . . .
5 . . . . X . . . . . . . . . . .
4 . . . . X . . . . . . . . . . .
3 . . . . X X X X . . . . . . . .
2 . . . . . . . .X. . . . . . . .
1 . . . . . . . . X . . . . . . .
1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
Eleinte Karesz a kezdőpontban álldogál (első út, első ut-
ca) a képernyő bal alsó sarkában, orral észak felé. Kareszen
kívül ebben a világban még kavicsok és falak vannak. A kavi-
csok az utcasarkon heverhetnek. Karesz felvehet egy-egy kavi-
csot és a zsebébe rakhatja; vagy kivehet egy-egy kavicsot a
zsebéből és ledobhatja azon a sarkon, ahol éppen áll. A zseb
akkora, hogy korlátlan mennyiségű kavics fér bele.
A képernyőn a falakat X fogja jelölni, a kavicsokat pedig
o. Hogy Karesz világának a képernyőn látható részében marad-
jon, a képernyőt képzeletbeli fal veszi körül (ami a képen
már nem látható).
A falak elzárják az utcák és az utak kereszteződését úgy,
hogy Karesz nem tud átmenni rajtuk. Ezért aztán gyakran kerü-
lőt kell tennie, hogy kitűzött célját elérje.
Karesz a következő utasításokat ismeri:
Indulj Karesz Karesz világát a képernyőre rajzolja,
Karesz maga a kezdőpontban áll, orral
észak felé.
Fordulj jobbra Kareszt 90 fokkal jobbra fordítja a
síkban.
Fordulj balra Kareszt 90 fokkal balra fordítja a
síkban.
Lépj Kareszt a következő utcasarokra viszi
arra, amerre az orra mutat. Ügyelnünk
kell arra, hogy Karesz a falon ne
akarjon átmenni.
Vedd fel a kavicsot Karesz felveszi a lába előtt, a sar-
kon heverő kavicsot, s a zsebébe te-
szi.
Dobj el egy kavicsot Karesz kivesz egy kavicsot a zsebéből
és eldobja az utcasarkon, ahol áll.
llj Eltünteti Karesz világát a képernyő-
ről.
északra néz Csak akkor igaz, ha Karesz orra észak
felé áll (egyébként hamis).
keletre néz Csak akkor igaz, ha Karesz orra kelet
felé áll.
délre néz sak akkor igaz, ha Karesz orra dél
felé áll.
nyugatra néz
Csak akkor igaz, ha Karesz orra nyugat
felé áll.
fal előtt áll Csak akkor igaz, ha a következő sarkon
fal található és ezért Karesz nem me-
het oda.
jobbra fal van Csak akkor igaz, ha Karesztől jobbra a
sarkon fal található.
van itt kavics Csak akkor igaz, ha a sarkon, Karesz
lába alatt egy kavics hever.
Az algoritmusokat a finomítás eszközével hozzuk létre.
név :
szakasz.
A név kisbetűvel kezdődik, és kisbetűkből, számjegyekből és
(esetleg) szóközökből áll. A szakasz egy vagy több, egymástól
pontosvesszővel elválasztott programegységből épül fel.
proramegység ; programegység ; ... ; programegység
A programegység lehet elemi (pl. egy algoritmus meghívása),
vagy lehet más programegységekből összerakva vezérlési, vá-
lasztási és ismétlő szerkezetek felhasználásával. (Jól látha-
tó, hogy itt az ELAN programozási nyelv lehetőségeit használ-
juk.