7 10:23 page 1 #1 2.1 változat

“programozas” — 2005/11/7 — 10:23 — page 1 — #1

Pere László Programozás példatár 2.1 változat

P ÉCS , 2005


c 2005 Pere László Programozás példatár c 2005 by László Pere Programming examples Engedélyezett e dokumentum másolása, terjesztése és/vagy módosítása a GNU Szabad Dokumentáció Engedélyének 1.1, vagy a Szabad Szoftver Alapítvány által kiadott újabb változata alapján; feltéve, hogy a meglévo˝ részek, a címlap és a belso˝ borító változatlan marad. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, with the Front-Cover text and the the Back-Cover Text unchanged.

Szerz˝ o: P ERE L ÁSZLÓ

Ez a tananyag a P ÉCSI T UDOMÁNYEGYETEM T ERMÉSZETTUDOMÁNYI K AR Informatikus-fizikus, Programozó Matematikus és Programozó informatikus képzésének részeként a középiskolában oktatott programozási ismeretek ismétlésére szolgál. A tananyag, valamint a hozzá tartozó programok letölthet o˝ k a ftp://linux.pte.hu/pub/Pere címro˝ l. A tananyag elkészítését a HEFOP-3.3.1-P-2004-06-0016/1.0 pályázat támogatta.


Tartalomjegyzék 1. Bevezetés 1.1. A munkamenet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 6 7

2. A While nyelv kifejez˝ oereje 2.1. Állandó töltése változóba . . . . . . . . . . 2.2. Változó áttöltése . . . . . . . . . . . . . . . 2.3. Változó növelése változóval . . . . . . . . . 2.4. Az összeadás . . . . . . . . . . . . . . . . . 2.5. A szorzás . . . . . . . . . . . . . . . . . . . 2.6. A hatványozás . . . . . . . . . . . . . . . . 2.7. A feltételes utasításvégrehajtás . . . . . . 2.8. Összehasonlítás állandóval . . . . . . . . . 2.9. Az egyenl˝oség reláció . . . . . . . . . . . . 2.10.A logikai értékek kódolása . . . . . . . . . 2.11.A logikai tagadás . . . . . . . . . . . . . . . 2.12.A feltételes utasításvégrehajtás hamis ága 2.13.A logikai vagy muvelet ˝ . . . . . . . . . . . . 2.14.A logikai és muvelet ˝ . . . . . . . . . . . . . 2.15.A kisebb reláció . . . . . . . . . . . . . . . 2.16.Egyéb relációk . . . . . . . . . . . . . . . . 2.17.Feladatok . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

9 12 13 14 15 16 16 16 17 18 19 21 22 23 25 25 26 26

3. Tömbök a While nyelvben 3.1. A legnagyobb elem kiválasztása . 3.2. A tartomány kiszámítása . . . . . 3.3. A matematikai átlag kiszámítása 3.4. Elem beszúrása és eltávolítása . . 3.5. A matematikai sorozat . . . . . . 3.6. Az elemek transzponálása . . . . 3.7. Rendezés . . . . . . . . . . . . . . 3.8. Keresés . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

29 30 31 31 32 35 36 37 39

3

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .


4 3.9. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Törtek kezelése a While nyelvben 4.1. Osztás . . . . . . . . . . . . . . . 4.2. Legnagyobb közös osztó . . . . . 4.3. Gyökvonás . . . . . . . . . . . . 4.4. Állandó közelítése . . . . . . . . 4.5. Függvény közelítése . . . . . . . 4.5.1. Függvények ábrázolása . 4.6. Függvénysorok . . . . . . . . . . 4.7. Kétváltozós függvények . . . . . 4.8. Fraktálok . . . . . . . . . . . . . 4.9. Integrálás . . . . . . . . . . . . . 4.10.Deriválás . . . . . . . . . . . . . 4.11.Véletlenszámok el˝oállítása . . . 4.12.Feladatok . . . . . . . . . . . . .

41

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

45 45 46 48 48 49 49 51 53 56 57 59 61 63

5. A Grammar 5.1. A Grammar nyelvének alapszerkezete 5.2. Egyszeru ˝ faszerkezet . . . . . . . . . 5.3. Rekurzív szerkezetek . . . . . . . . . 5.4. A balrekurzió . . . . . . . . . . . . . . 5.5. Határolójelek . . . . . . . . . . . . . . 5.6. Muveleti ˝ jelek . . . . . . . . . . . . . . 5.7. Programok létrehozása . . . . . . . . 5.8. Feladatok . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

69 70 72 74 75 76 77 77 79

. . . . . . . . . . . . .

. . . . . . . . . . . . .


1. fejezet

Bevezetés E könyv a számítógépek programozásának alapjait igyekszik bemutatni. A könyv els˝osorban olyan olvasók, olyan egyetemi és f˝oiskolai hallgatók számára készült, akik semmilyen ismerettel nem rendelkeznek a témában, akik életük során egyáltalán nem tanultak számítógépprogramozást, nem írtak számítógépprogramot egyetlen programozási nyelven sem. Célunknak megfelel˝oen a könyv nem feltételez el˝oismeretet a témában. Az olvasónak tehát nem kell tudnia semmit a számítógépek programozásáról – legalábbis a könyvvel való ismerkedés kezdetén. Feltételezünk viszont néhány egyszeru ˝ el˝oismeretet a számítógéphasználattal témakörében. Ezeket az el˝oismereteket a következ˝o pontokban foglalhatjuk össze: • Szövegszerkesztési ismeretek, a billentyuzet ˝ használata. Az olvasónak képesnek kell lennie szöveges (ASCII) állományok kezelésére valamely szövegszerkeszt˝o programmal. (A középiskolákban oly népszeru ˝ Microsoft Word, amely a Microsoft Office része, nem szövegszerkeszt o˝ program.) • Állománykezelés, programok futtatása. Ez a témakör magába foglalja a könyvtárak és állományok létrehozását, a hozzájuk tartozó jogosultságok megváltoztatását, a szabványos be- és kimeneti csatornák átirányítását. • Alapvet˝o matematikai ismeretek, az egész és valós számok halmazán végzett elemi muveletek, ˝ egyszeru ˝ matematikai jelölésrendszer. Ezeket az alapismereteket az olvasónak más szakkönyveket használva kell megismernie. Javasoljuk a GNU/Linux vagy más UNIX felhasználói ismereteket bemutató könyvek használatát.[1, 3].

5


6

1.1. A munkamenet A könyvben egy igen egyszeru, ˝ mondhatni primitív programozási nyelvek segítségével mutatjuk a számítógépprogramozás alapjait. A primitív nyelv használatának a célja az, hogy a nyelv barokkos felépítményei, cizellált és burjánzó eszköztára ne vonja el a hallgatók figyelmét azoktól az ismeretekr˝ol, amelyek képesség szinten való elsajátítása a célunk. A használt nyelveket igen egyszeru ˝ értelmezo˝ programok1 segítségével kezeljük. Az általunk használt értelmez˝oprogramok az általunk megírt programot beolvassák a szabványos bemenetükro˝ l, majd sorról sorra végrehajtják a programban található utasításokat. Mivel a legtöbb esetben nem csak végrehajtani szeretnénk a programot, hanem meg is szeretnénk o˝ rizni a benne található utasítsokat, ezért a programot általában állományba készítjük el egy szövegszerkeszto˝ program segítségével, majd ezt az állományt irányítjuk az értelmezo˝ program szabványos bemenetére. 1. példa. E példa bemutatja hogyan készíthetünk While programot, hogyan futtathatjuk a benne található utasításokat. Készítsük el a következo˝ tartalmú állományt a szövegszerkeszto˝ program segítségével: 1 2 3 4 5

a := 10 while a<>12 do print a a := a + 1 wend

While/01-pelda.bas

Futtassuk most a programot a While értelmezo˝ program segítségével, annak szabványos bemenetére irányítva a programsorokat. # While <While/01-pelda.bas 10 11 Normális befejezés. #

Amint látjuk a program futtatása két szám kiírását eredményezte a szabványos kimeneten, majd leállt a program, amit a „normális befejezés” üzenet jelzett. Figyeljük meg, hogy a While program indításához a While parancsot használtuk, amely nagy betuvel ˝ kezdo˝ dik. Ha a programot kis kezdo˝ betuvel ˝ 1 Azokat a programokat nevezzük értelmezo ˝ programnak, amelyek egy adott nyelven megírt programot értelmeznek és utasításról utasításra végrehajtanak.


7

1.1. ábra. A While kézikönyve

próbáljuk indítani más program indul (a while a BASH parancsértelmezo˝ beépített parancsa), amely nem felel meg a céljainknak. A While program használatáról magyar nyelvu ˝ leírást olvashatunk a man While parancs begépelésével. A While kézikönyvoldalának elejét mutatja be az 1.1. ábra. A könyvben található While értelmez˝oprogram letölthet˝o az ftp://linux.pte.hu/pub/Pere/While-1.2.tar.gz címr˝ol. Ebben a könyvtárban megtalálhatjuk a program esetleges késo˝ bbi változatait is. A While értelmez˝o a GNU programcsomagok esetében megszokott módon fordítható le és telepíthet˝o a számítógépre[2]. A könyvben szintén használjuk a Grammar nevu ˝ programot, amely egy més programozási nyelvet értelmez és hajt végre. A Grammar ugyanúgy telepíthet˝o és ugynúgy használható, mint a While, de más feladatok elvégzésére használható, teljesen, illetve más nyelvet használ.

1.2. Feladatok 1. Módosítsuk a 1. példa programját oly módon, hogy a 2. sorban található számot átírjuk 100-ra, majd futtassuk a programot! 2. Módosítsuk a 1. példa programját, írjuk át a 4. sorban található 1-es értéket 2-re, majd futtassuk a programot! 3. Futtassuk a program kézikönyvoldalában található valamelyik példaprogramot, vizsgáljuk meg muködik-e! ˝


8 4. Vizsgáljuk meg a számítógépre telepített While változatszámát! Melyik kapcsoló szolgál erre a célra? 5. Töltsük le a könyvhöz tartozó példaprogramokat és csomagoljuk ki o˝ ket a tar program segítségével! Futtassuk valamelyik példaprogramot!


2. fejezet

˝ ereje A While nyelv kifejezo A programozási nyelvek sok szempont szerint csoportosíthatók, de a legnépesebb csoport mindenképpen az impertív nyelvek családja. Az imperatív nyelvek nevüket a latin imperare (parancsolni) szóról kapták. A nyelvek, amelyek ehhez a csoporthoz tartoznak olyan parancsokat tartalmaznak, amelyek a számítógép operatív memóriájában található memóriarekeszek manipulálására vonatkoznak. A memóriarekeszek ezen programozási nyelvek esetében általában névvel vannak ellátva és a legtöbb esetben változónak nevezzük o˝ ket. Az egyik legegyszerubb, ˝ mondhatni elméleti jelento˝ ségu ˝ imperatív nyelv a While nyelv, amelyet a számítógépprogramozással elméleti nézo˝ pontból foglalkozó szakemberek használnak matematikai vizsgálatok tárgyaként. Valójában a While nyelv sok, egymással egyenrangú változata is készítheto˝ , sok olyan While nyelvjárás készíthet˝o, amely megfelel a céljainknak. E könyvben a magyar szakirodalomban már bemutatott[4] egyszeru ˝ változatot használjuk. A While nyelvu ˝ programok a következ˝o kifejezésekb˝ol állnak: • Memóriarekesz törlése: x := 0 A kifejezésben az x helyén egy vagy több betub ˝ o˝ l álló tetsz˝oleges változónév szerepelhet. A kifejezés az adott változó törlésére ad utasítást, hatására a változó értéke 0-val válik egyenlo˝ vé. Vegyük észre, hogy ez a kifejezés nem teszi leheto˝ vé tetsz˝oleges érték elhelyezését a változóban, azaz a kifejezésben szereplo˝ 0 helyén nem állhat más érték. • Inkrementálás: x := x + 1 9


10 A kifejezésben az x helyén egy vagy több betub ˝ o˝ l álló tetsz˝oleges változónév szerepelhet. A kifejezés hatására az adott változó értéke 1-el növekszik, azaz értéke inkrementálódik. Vegyük észre, hogy a kifejezés segítségével a változó értéke nem növelhet˝o tetsz˝oleges értékkel, a kifejezésben szereplo˝ 1 helyén nem állhat más érték. • Dekrementálás: x := x − 1

A kifejezés a változó 1-el való csökkentésére (inkrementálás) ad utasítást. Ez a kifejezés muködésében ˝ és használatában egyébként megegyezik az inkrementáló kifejezés muködésével ˝ és használatával.

• While utasítás: while x 6= y do ... wend A legösszetettebb utasítás, amelyr˝ol a While nyelv a nevét kapta. Az utasításban az x és az y változó helyén tetszo˝ leges, egy vagy több betub˝ ˝ ol álló változónév szerepelhet, nem szerepelhet azonban szám vagy összetett kifejezés. Ez az összetett kifejezés a „. . . ” helyén szereplo˝ kifejezés vagy kifejezések ismétlését írja el˝o. A kifejezés végrehajtásakor el˝oször meg kell vizsgálni az x 6= y feltételt és a „. . . ” helyén szereplo˝ kifejezéseket csak akkor kell végrehajtani, ha a feltétel igaz értéket képviselt, azaz ha az x és az y változó értéke nem egyenl˝o. Ha viszont a feltétel igaz értéke miatt végre kell hajtani a „. . . ” helyén álló kifejezéseket, azok végrehajtása után meg kell ismételni a While kifejezés végrehajtását, azaz ismét meg kell vizsgálni az x 6= y egyenlo˝ tlenséget és ha az igaz, újra végre kell hajtani a „. . . ” kifejezéseket. E kifejezés jelentését jól jelzi a while szó, amely egyik jelentése „míg”, „amíg”. A bemutatott írásmód matematikai, annak nem minden jelét támogatják az egyszerubb ˝ szövegszerkeszto˝ k, ezért a While programozási nyelv a következ˝o írásmódot részesíti el˝onyben: • Memóriarekesz törlése: x := 0 • Inkrementálás:


11 x := x + 1 • Dekrementálás: x := x - 1 • While utasítás: while x <> y do ... wend A bemutatott kifejezéseken kívül két újabb kifejezést vezetünk be. Ezekre a kiegészít˝o kifejezésekre azért van szükségünk, hogy a gyakorlatban is használható programokat készíthessünk a While nyelv felhasználásával. A kiegészít˝o kifejezések lehet˝ové teszik, hogy a kiszámolt értékeket kiírassuk a szabványos kimenetre és azt, hogy megjegyzésekkel könnyítsük a program megértését: • Memóriarekesz kiíratása: print x A kifejezésben az x helyén tetsz˝oleges – egy vagy több betub˝ ˝ ol álló – változónév szerepelhet. A kifejezés hatására a változó értéke kiíródik a szabványos kimenetre, a változó értéke megjelenik a képerny˝on. Vegyük észre, hogy ez a kifejezés kizárólag egyetlen változó értékének kiírására alkalmas, több változót vagy szöveges értéket nem írhatunk a kifejezésbe. • Megjegyzés: rem szöveg A kifejezésben a szöveg helyén tetszo˝ leges karaktersorozat szerepelhet. A rem kulcsszó után, a sor végéig található karaktereket a program nem veszi figyelembe. Ennek az eszköznek a segítségével magyarázó szövegeket helyezhetünk el a programban, amelyek megkönnyítik a program elolvasását, megértését.


12 Igen érdekes, hogy bármennyire is egyszeru ˝ és primitív a bemutatott programozási nyelv, mégis teljesértéku. ˝ Minden számítógéppel elvégezhet o˝ komputáció (számítás) elvégezhet˝o While nyelven megírt programmal. Igaz ugyan, hogy a bemutatott nyelv csak a pozitív egész számok kezelésére alkalmas (beleértve a 0-t is), de ez a probléma is megkerülheto˝ , hiszen minden adat kódolható egész számként, így a nyelv valójában bármilyen információ kezelésére és feldolgozására használható. A következ˝o oldalakon bemutatjuk hogyan végezhet˝ok el összetett muve˝ letek a While nyelv segítségével, újabb és újabb nyelvi eszközöket vezetünk, közben pedig megvizsgáljuk az imperatív programozási nyelvek legfontosabb eszközeit.

2.1. Állandó töltése változóba A While nyelv segítségével tetszo˝ leges egész szám elhelyezhet˝o a változókban. Ennek a muveletnek ˝ a lehetséges legegyszerubb ˝ módja a következ o˝ : 1 2 3 4 5 6 7 8

While/alap/01allando.bas rem A program a 3 értéket helyezi rem az x változóba. x := 0 x := x + 1 x := x + 1 x := x + 1 print x

A program a 3 értéket helyezi el az x változóban úgy, hogy a változót elo˝ bb törli, majd egymás után háromszor inkrementálja. Az általunk használt értelmez˝oprogram számára az állandó változóba való töltését egyszerubben ˝ is jelezhetjük. A program elfogadja a következo˝ formájú kifejezéseket: • Állandó töltése változóba: x := 23 A kifejezésben szerepl˝o 23 helyén tetsz˝oleges egész szám elhelyezhet˝o, az x helyén pedig tetsz˝oleges változónév állhat. A kifejezés hatására a változó értékként felveszi az adott egész értéket. • Állandó töltése változóba (programban): x := 23


13

2.2. Változó áttöltése A While nyelv segítségével tetszo˝ leges változó értéke áttölthet˝o bármely más változóba úgy, hogy az eredeti változó meg˝orzi az értékét. Ezt mutatja be a következ˝o példaprogram: 1 2 3 4 5 6 7 8

While/alap/02load.bas rem A programaz x értékét helyezi az y változóba. x := 7 y := 0 while x <> y do y := y + 1 wend print y

A program muködésének ˝ megértéséhez figyelembe kell vennünk, hogy csak a pozitív egész számokat támogatja a nyelv, hiszen így bármely változó értéke el˝oállítható, a 0-tól indulva tetsz˝oleges számú inkrementálás segítségével. A program a 4. sorban 0-ra állítja y értékét, majd addig inkrementálja, amíg az értéke el nem éri x értékét, azaz amíg az x 6= y feltétel igaz. A példaprogram kapcsán néhány egyszeru ˝ tényre érdemes felhívni a figyelmet: • Ha az x változóban elhelyezett, áttöltendo˝ érték a 0 volna, a programunk akkor is a helyes eredményt adná – azaz a program véghajtása után y értéke 0 lenne – mert a 6. sorban található inkrementálás egyszer sem hajtódna végre. • Az 5. sorban található feltétel szerint a program végrehajtása mindaddig az 5–7. sorokban történik, amíg x 6= y, azaz, ha a program végrehajtása közben eljutunk a 8. sorba, akkor x = y. Ez természetesen nem bizonyítja azt, hogy a program végrehajtása során valaha is eljutunk a 8. sorig, csak azt, hogy a program 8. sorának végrehajtásakor x = y. • A programban szerepel az x := 7 kifejezés, ami az eredeti While nyelvnek nem része, de mint láttuk az eredeti nyelven is elvégezheto˝ , az értelmez˝oprogram által elfogadott kifejezésr˝ol van szó. Az általunk használt értelmez˝oprogram a változó áttöltésére a következo˝ egyszerusített ˝ kifejezést is értelmezi: • Változó értékének töltése változóba:


14 x := y A kifejezésben az x és y helyén tetszo˝ leges változónevek állhatnak. A kifejezés hatására az értelmez˝oprogram az y helyén álló változó értékét áttölti az x helyén álló változóba úgy, hogy közben egyetlen más változó értéke sem változik. • Változó értékének töltése változóba (programban): x := y

2.3. Változó növelése változóval A While nyelv segítségével egy adott változó értékét csökkenthetjük egy másik változóban tárolt értékkel. Ezt mutatja be a következo˝ példaprogram: 1 2 3 4 5 6 7 8 9 10

While/alap/03noveles.bas rem A program x értékét növeli y értékével. x := 7 y := 10 s := 0 while s <> y do x := x + 1 s := s + 1 wend print x

A példaprogram muködése ˝ könnyen megértheto˝ , ha ismét figyelembe vesszük, hogy az értelmez˝oprogram által elfogadott értékek mindegyike el˝oállítható a 0 értéku ˝ változó tetsz˝oleges számú inkrementálásával. A program az s segédváltozó értékét addig növeli, amíg az egyenlo˝ nem lesz az y változó értékével. Mivel az s értéke kezdetben 0 (5. sor) a while kifejezésen belül található sorok (7–8. sorok) annyiszor hajtódnak végre, amennyi az y értéke, így a 7. sorban ennyiszer inkrementáljuk x értékét. Az x értékét y-szor inkrementálva értéke éppen y-al no˝ . A bemutatott példaprogrammal kapcsolatban a következo˝ egyszeru ˝ tényeket érdemes megjegyeznünk: • A példát receptként felhasználhatjuk, de arra mindenképpen ügyelnünk kell, hogy az s változót helyesen válasszuk meg. A program ugyanis az x változó névelése mellett, mellékhatásként megváltoztatja az s segédváltozó értékét is. Nyilvánvaló, hogy az s helyén olyan változónévnek kell szerepelnie, amelyet más célokra nem használunk.


15 • A while kifejezést a példaprogramban úgy használtuk, hogy benne található utasítások kiértékelésének számát tartottuk szem elo˝ tt (egyszer fut le, kétszer fut le stb.). Soha nem szabad azonban elfelejtenünk, hogy a bels˝o kifejezések kiértékelésének száma 0 is lehet, elo˝ fordulhat tehát, hogy a bels˝o utasításokat egyáltalán nem hajtja végre az értelmez˝oprogram, mert a feltétel már az els˝o lefutás el˝ott hamis értéket képviselt. A While értelmez˝oprogram a bemutatott muvelet ˝ elvégzésére a következo˝ egyszeru ˝ kifejezést is elfogadja: • Változó növelése változóban tárolt értékkel: x := x + y A kifejezésben az x és y helyén tetszo˝ leges változónevek állhatnak. A kifejezés hatására az értelmez˝oprogram az y helyén álló változó értékével növeli az x helyén álló változó értékét úgy, hogy közben egyetlen más változó értékét sem változtatja meg. • Változó növelése változóban tárolt értékkel (programban): x := x + y

2.4. Az összeadás Az el˝oz˝o szakaszban adott változó értékét növeltük meg egy más változóban tárolt értékkel. A következ˝o példa bemutatja, hogyan helyezhetjük el az összeadás értékét egy harmadik, az eredmény számára fenntartott változóben és hogyan adhatunk állandót a változó értékéhez: While/alap/04osszeadas.bas 1 rem Legyen z = x + y és v = x + 99! 2 3 x := 10 4 y := 8 5 z := x 6 z := z + y 7 print z 8 9 v := 99 10 v := v + x 11 print v A példaprogram az eddig bemutatott ismeretek alapján könnyen értelmezhet˝o. A While értelmez˝oprogram elfogadja és elvégzi az összedást egyszeru˝ sített formában (például x := 5 + y) is.


16

2.5. A szorzás A szorzás visszavezethet˝o az összeadásra, mint ahogyan az összeadás visszavezethet˝o volt az inkrementálásra. A While értelmez˝o a szorzás jelzésére elfogadja és végrehajtja a * muveleti ˝ jelet. A program a szorzás, összeadás és kivonás perecedenciáját, valamint a ( ) jeleket a matematikában megszokott módon kezeli, így a következo˝ példaprogram kifejezései a matematikai értelemben helyes eredményt adják: 1 2 3

math/01kifejezesek.bas a := 5 b := 8 * a + 14 c := (a + b) * (a - b)

2.6. A hatványozás A hatványozás visszavezethet˝o a szorzásra, ahogyan a szorzás visszavezethet˝o volt az összeadásra. A While értelmez˝o a hatványozás jelzésére elfogadja és végrehajtja a ^ muveleti ˝ jelet a matematikában megszokott precedenciával.

2.7. A feltételes utasításvégrehajtás A While nyelv segítségével az egyes kifejezések kiértékelését, azaz az utasítások elvégzését feltételhez köthetjük, azaz megadhatjuk, hogy a változók mely értéke esetén végezze el a program az adott utasítást és mely értékeinél hagyja figyelmen kívül. A következ˝o példaprogram kiírja x értékét, ha x 6= y, egyébként (ha x = y) pedig nem. 1 2 3 4 5 6 7 8 9

While/alap/05if.bas rem A program kiírja x értékét, ha x <> y. x := 10 y := 9 s := y while x <> s do print x s := x wend


17 A program a feltételes utasításvégrehajtást a while ciklusszervez o˝ kifejezés segítségével valósítja meg. Az 5. sorban egy segédváltozót vezetünk be, amelybe tároljuk y értékét. Ha a while kifejezés feltétele igaz (azaz x 6= y), a program végrehajtja az x változó kiíratását végzo˝ utasítást a 7. sorban és a 8. sorban elhelyezi x értékét a segédváltozóban. A 8. sornak öszönheto˝ en a while ciklusos jellege megszunik, ˝ hiszen ha végrehajtjuk a 8. sor utasítását az x 6= s nem teljesül, azaz a 7–8. sorok többször már nem hajtódnak végre. A while értelmez˝o a feltételes utasításvégrehajtás jelzésére elfogadja a következ˝o egyszeru ˝ kifejezést: • Feltételes utasításvégrehajtás if x 6= y then ... end A kifejezésben az x és y helyén tetszo˝ leges változónevek állhatnak. A program a kifejezés hatására végrehajtja a „. . . ” helyén álló kifejezéseket, ha az x 6= y egyenl˝otlenség igaz.

• Feltétetles utasításvégrehajtás (programban): if x <> y then ... end

Az egyszerusített ˝ írásmóddal az el˝oz˝o program a következ˝o formában valósítható meg: 1 2 3 4 5 6 7 8

While/alap/06if.bas rem A program kiírja x értékét, ha rem x <> y. x := 10 y := 9 if x <> y then print x end

2.8. Összehasonlítás állandóval Nagyon egyszeruen ˝ belátható, hogy a while és if szerkezetek feltételeként szerepl˝o összehasonlítás segítségével nem csak két változó hasonlítható össze, hanem egy változó és egy állandó is. Ezt mutatja be a következo˝ példa:


18

1 2 3 4 5 6 7 8

While/alap/07nemegyenlo.bas rem A program kiírja x értékét, ha y <> 0. x := 99 y := 10 s := 0 if y <> s then print x end

A program a már ismert egyszeru ˝ módszert használja, a feladatot egy s segédváltozó bevezetésével oldja meg. A While értelmez˝o által kezelt nyelvben a <> muveleti ˝ jel állandóval is képes összehasonlítani a változókat.

2.9. Az egyenl˝ oség reláció Talán nem a legegyszerubb ˝ módon, de belátható, hogy az eddigi eszközök használatával is képesek vagyunk elvégezni az egyenlo˝ ségvizsgálatot, azaz tudunk olyan programot készíteni, amely az if vagy while szerkezet feltételeként két változó egyenl˝oségét és nem egyenl˝otlenségét írja el˝o. A következ˝o példaprogram az egyenl˝oségvizsgálatot mutatja be: 1 2 3 4 5 6 7 8 9 10 11

While/alap/08egyenlo.bas rem A program kiírja x értékét, ha x = y. x := 10 y := 10 s := 1 if x <> y then s := 0 end if s <> 0 then print x end

A program elhelyezi s segédváltozóban a 0 értéket, ha x 6= y és kiírja x értékét, ha s 6= 0. A kett˝os tagadásnak köszönhet˝oen a program kiírja x értékét, ha az x 6= y nem igaz, azaz, ha x = y. A While értelmez˝o elfogadja az egyenl˝oségvizsgálat jelzésére az == kett˝os jelet, így használhatjuk a következ˝o kifejezéseket. • Egyenl˝oségvizsgálat (if):


19 if x = y then ... end • Programban: if x == y then ... end • Egyenl˝oségvizsgálat (while): while x = y do ... wend • Programban: while x == y do ... wend

2.10. A logikai értékek kódolása Az el˝oz˝okben már utaltunk rá, hogy minden adat kódolható egész számok formájában. Különösen igaz ez a logikai értékekre, hiszen a két logikai érték (hamis és igaz) kódolására két szám is elegendo˝ . Tulajdonképpen bármely két szám alkalmas volna arra, hogy a logikai értékek kódolására használjuk, a legegyszerubb ˝ azonban, ha a 0 és 1 számokat választjuk. Ezzel természetesen nem állítjuk azt, hogy e két számnak bármilyen köze van a logikai értékekhez, egyszeruen ˝ választunk két számot a kódolásra. Használjuk az 1 értéket a logikai igaz érték kódolására és használjuk a 0 értéket a logikai hamis érték kódolására. Állítsuk elo˝ a logikai értéket reláció eredményeként! A következo˝ program megvalósítja a a ⇔ x 6= y kifejezést1 , az x 6= y kifejezés értékét elhelyezve az a változóban. 1 2

x := 1 y := 8

While/alap/09logikaiertek.bas

1 A ⇔ muveleti ˝ jel logikai értékek egyenlo˝ ségét jelzi, a kifejezés azt jelzi, hogy a logikai változó értéke akkor, és csak akkor igaz, ha x 6= y.


20 3 4 5 6 7

a := 0 if x <> y then a := 1 end print a

A program könnyen érhet˝o. A 3. sorban elhelyezzük a 0 (hamis) értéket az a változóban. Ha x 6= y, elhelyezzük az 1 (igaz) értéket a-ban, ha nem, akkor a változó értéke marad 0. A program kapcsán a következ˝o egyszeru ˝ gondolatokat érdemes megjegyeznünk: • A program csak egyszer vizsgálta meg a két változó egyenlo˝ ségét, holott a feladat szöveges megfogalmazása két feltételvizsgálatot sugallt (ha egyenl˝o, ha pedig nem egyenl˝o). Nyilvánvaló, hogy az egy feltételvizsgálattal a program hatékonyabb, mint két feltételvizsgálattal. • A 3. sorban tulajdonképpen feltételeztük, hogy a x = y azzal, hogy elhelyeztük a 0 értéket az a változóban. A programozás során sokszor élünk ilyen „feltételezésekkel”, sokszor helyezünk el alapértelmezés szerinti értéket a változókban, amelyeket aztán késo˝ bb szükség esetén módosítunk. Az el˝oz˝o programot a While értelmez˝oprogram számára egyszerusített ˝ formában is írhatjuk. Ezt mutatja be a következo˝ példaprogram: 1 2 3 4 5 6

While/alap/10logikaiertek.bas rem Logikai érték kifejezésben. x := 1 y := 8 a := x <> y print a

A While az relációjelek használatát mindenütt leheto˝ vé teszi, ahol a muve˝ leti jelek megengedettek így a relációjelek segítségével összetett kifejezések is készíthet˝ok. A következ˝o program bemutatja, hogyan használhatjuk fel a logikai értéket hordozó változót az if és a while feltételeként. 1 2 3 4 5

While/alap/11logikaivaltozo.bas rem Logikai értéket hordozó változó felhasználása. x := 18 a := x <> 18 if a <> 0 then


21 6 7

print x end

A példában megfigyelhetjük, hogy az a logikai változó értékét az if szerkezetben összehasonlítjuk 0-val. Ha az a értéke 0 (hamis), akkor az a 6= 0 értéke is hamis, ha az a értéke 1 (igaz), akkor az a 6= 0 értéke is igaz. Nyilvánvaló, hogy a ⇔ a 6= 0

azaz a akkor és csakis akkor igaz, ha a 6= 0. Ennek megfelel˝oen a While értelmez˝oprogram megengedi, hogy a logikai változót egymagában is használjuk az if és a while szerkezetek feltételeként. Így az el˝oz˝o program egyszerusített ˝ formában is írható: 1 2 3 4 5 6 7

While/alap/12logikaivaltozo.bas rem Logikai értéket hordozó változó felhasználása. x := 18 a := x <> 18 if a then print x end

Felmerül természetesen a kérdés, hogy mi történik, ha valamelyik programban logikai változóként használunk egy változót, amelynek értéke nem helyesen kódolt logikai érték, azaz aktuális értéke sem 0, sem pedig 1. A While értelmez˝o a programozási nyelvek esetében megszokott módon viselkedik. A változó értékét hamis értékunek ˝ tekinti ha 0, minden más esetben pedig igaz értékunek. ˝ (Valójában az a ⇔ a 6= 0 pontosan ezt jelenti!)

2.11. A logikai tagadás Készítsük el a logikai tagadást muveletét, ˝ ahol b=a azaz b az a negáltja a következ˝o igazságtáblázat alapján: a I H

a H I

A logikai tagadás ügyesen megszerkesztett if kifejezés segítségével elvégezhet˝o, a legegyszerubb ˝ megoldás azonban a következo˝ :


22

1 2 3 4 5 6

While/alap/13not.bas rem Logikai tagadás kivonással. a := 1 b := 1 - a print a print b

A program muködésének ˝ helyessége akár próbálgatással is könnyen belátható, hiszen az a változó csak kétféle értéket vehet fel. A While értelmez˝o a logikai tagadás elvégzésére elfogadja a not kulcsszót, így az el˝oz˝o példaprogram a következ˝o formában is írható: 1 2 3 4 5 6

While/alap/14not.bas rem Logikai tagadás egyszer˝ usített írásmódja. a := 1 b := not a print a print b

2.12. A feltételes utasításvégrehajtás hamis ága Egészítsük ki a feltételes utasításvégrehajtás szerkezetét olyan résszel, amely a feltétel hamis értéke mellett hajtódik végre! A következ˝o példaprogram növeli vagy csökkenti y értékét attól függo˝ en, hogy annak jelenlegi értéke egy állandóval egyenlo˝ -e (vagy nem). 1 2 3 4 5 6 7 8 9

y := 9 x := y == 8 if x then y := y + 10 end if not x then y := y - 10 end print y

While/alap/15else.bas

A példaprogram túl sok gyakorlati haszonnal nem kecsegtet, megfigyelheto˝ azonban benne egy jellemz˝o szerkezet. A programban található két egymás utáni feltételes utasításvégrehajtás feltétele nem független egymástól, az egyik feltétel éppen az ellentéte a másiknak. Az ilyen szerkezetek egyszerubb ˝ írásmódja a következ˝o:


23 • Feltételes utasításvégrehajtás hamis ággal: if x = y then ... else ... end A kifejezés hatására a then és else közti utasítások hajtódnak végre, ha a feltételes utasításvégrehajtás feltétele igaz értéket képvisel, az else és az end közti utasítások hajtódnak végre, ha a feltétel hamis értéket képvisel. A kifejezésben feltételként az eddig bemutatott bármely kifejezés használható. • Feltételes utasításvégrehajtás hamis ággal (programban): if x == y then ... else ... end Az el˝oz˝o program az egyszerusített ˝ írásmóddal a követetkezo˝ képpen alakul: 1 2 3 4 5 6 7

y := 8 if y == 8 then y := y + 10 else y := y - 10 end print y

While/alap/16else.bas

2.13. A logikai vagy muvelet ˝ Az eddig bemutatott eszközökkel könnyedén megvalósítható a logikai vagy muvelet. ˝ Készítsük el a q := a ∨ b

logikai vagy muveletet ˝ megvalósító programot a következo˝ igazságtábla alapján!


24 a H H I I

b H I H I

a∨b H I I I

A vagy muvelet ˝ elvégzésére többféle megoldási mód is kézenfekvo˝ nek látszik. Használhatunk ügyesen megszerkesztett if szerkezeteket és magától értet˝od˝o módon adódik az összeadás muvelete ˝ is2 . Egy hatékony (és nem túl kézenfekv˝o) megoldás a következ˝o: 1 2 3 4 5 6 7 8 9

While/alap/17or.bas rem Logikai vagy m˝ uvelet. a := 0 b := 0 q := 1 if not a then q := b end print q

A program az 5. sorban elhelyezi a logikai igaz értéket kódoló 1-et a q változóban, feltételezve ezzel, hogy az eredmény értéke igaz lesz. A program a 6. sorban megvizsgálja az a értékét és ha az nem igaz, az eredmény tárolására szolgáló változóban elhelyezzük a b változó értékét. Ha figyelmesen megfigyeljük az igazságtábla minden sorát és végigkövetjük mind a négy lehetséges a, b értékkombinációt könnyen beláthatjuk, hogy a program mindig a helyes eredményt adja. A program muködési ˝ kissé kifordultnak tunik, ˝ az olvasó számára úgy tun˝ het, hogy az emberi gondolkodással nincs összhangban. Valójában azonban a következ˝o két megfogalmazás egyenértéku: ˝ 1. Az a ∨ b logikai vagy muvelet ˝ eredménye igaz, ha az a vagy a b, esetleg mindkett˝o igaz. 2. Az a ∨ b logikai vagy muvelet ˝ eredménye b, ha a hamis, különben igaz.

A fenti két megfogalmazással egyenértéku ˝ további definíciókat adhatunk a logikai vagy muveletre, ˝ az pedig, hogy melyiket tekintjük az emberi gondolkodáshoz közelebbinek csak attól függ, hogy hány évet töltöttünk el számítógépprogramok készítésével vagy logikai áramkörök tervezésével. A While értelmez˝oprogram a logikai vagy muveletének ˝ elvégzésére elfogadja az or kulcsszót. 2 Az

egyszeru ˝ összeadás azonban nem felel meg céljainknak, hiszen 1 + 1 6= 1.


25

2.14. A logikai és muvelet ˝ A logikai vagy muvelet ˝ mintájára elkészítheto˝ a logikai és muvelet ˝ is3 .

2.15. A kisebb reláció Készítsük el a kisebb relációt kiszámító programot, valósítsuk meg a a⇔x
összefüggést! Az érdekesség kedvéért készítsük el úgy a programot, hogy az adjon helyes eredményt a negatív egész számokra számokra is (a While értelmez o˝ ezeket is kezeli)! Ha a problémát végiggondoljuk láthatjuk, hogy nem is olyan egyszeru ˝ megoldást találni: 1. Ha pozitív egész számot elegend˝oen sokszor dekrementálunk, egyenl˝o lesz 0-val. Két szám közül ilyenkor az lesz a kisebb, amelyik elo˝ bb érte el a 0-t. 2. Negatív számokat inkrementálnunk kell, hogy elérjük a 0-t. 3. Azt, hogy egy szám negatív-e, az eddigi eszközeinkkel nem tudjuk eldönteni (x < 0). A következ˝o program megoldja a feladatot az egész számok halmazán: While/alap/19kisebb.bas 1 rem Legyen a <=> x < y 2 x := -1 3 y := 2 4 i := x 5 j := y 6 while i <> y and j <> x do 7 i := i - 1 8 j := j - 1 9 wend 10 a := i <> y 11 print a A program azon az egyszeru ˝ elgondoláson alapul, hogy ha két egész szám nem egyenl˝o és elegend˝oen sokszor dekrementáljuk mindkett˝o, akkor vagy az egyik, vagy a másik fog olyan kis értékre csökkenni, mint amekkora a másik volt. A program ezen elgondolás alapján néhányszor végigkövetve megérthet˝o. 3 A program elkészítése a klasszikus fordulattal „az olvasótól balra található” (left to the reader).


26

2.16. Egyéb relációk Az általánosan használt további relációk hasonló programmal megvalósíthatók vagy az alábbi kifejezések alapján kifejezheto˝ k: • Nagyobb:

x > y ⇔ x < y ∧ x 6= y

• Nagyobb vagy egyenl˝o: x≥y ⇔x>y∨x=y • Kisebb vagy egyenl˝o:

x≤y ⇔x
A While értelmez˝o a relációjeleket (>, <, >= és <=) a programozási nyelvek esetében és a matematikában megszokott módon kezeli.

2.17. Feladatok 1. Készítsünk programot, amely elvégzi a z = xy szorzást az összeadás ciklikus végrehajtásának segítségével! 2. Készítsünk programot, amely elvégzi a z := xy hatványozást a szorzás muveletének ˝ ciklikus végrehajtásával! 3. Készítsen programot és állapítsa meg vele, hogy a b := 1 - a és b := not a kifejezések viselkedése különbözik-e egymástól, ha az a változó értéke nem 0 és nem 1! Írja le a különbséget szavakkal! 4. Mutasson be legalább három különféle programot a logikai tagadás elvégzésére! A programokban ne használja a not kulcsszót! 5. Mutasson be legalább három különféle programot a logikai és muvelet ˝ elvégzésére! A programokban ne használja az and kulcsszót! 6. Mutasson be legalább három különféle programot a logikai vagy mu˝ velet elvégzésére! A programokban ne használja az or kulcsszót! 7. Készítsen programot, amely megvalósítja az a ⇔ x < y relációt a pozitív számok (beleértve a 0-t is) halmazán!


27 8. Legyen x = 1, 27 és legyen y = 0, 28! Kódolja e számokat egész számmá és végezze el az xy szorzást! Mennyi az eredmény? 9. Legyenek x = m1 × 10k1 és y = m2 × 10k2 számok, ahol m1 , m2 , k1 , k2 legyenek egészek! Mutasson be programot, amely elvégzi az xy szorzást! 10. Készítsünk programot, amely bizonyítja a A∨B =A∧B összefüggést! A program A és B minden lehetséges értékkombinációjára számítsa ki az egyenl˝oség jobb- és bal oldalát, majd hasonlítsa össze o˝ ket. 11. Készítsünk programot, amely adott matematikai sorozat elemeit írja a képerny˝ore! A program a matematikai sorozat meghatározása használjon két változót! 12. Készítsünk programot, amely mértani sorozat elemeit írja a képerny˝ore! A program a mértani sorozat meghatározására használjon két változót! 13. Írja le szavakkal, hogy milyen problémát old meg a következo˝ program! 1 2 3 4 5 6 7 8 9 10

While/peldak/01.bas i := 10; j := 12; k := -1 m := i; if j>m then m := j end if k>m then m := k end print m

14. Írja le szavakkal, hogy milyen problémát old meg a következo˝ program! 1 2 3 4 5 6 7 8

While/peldak/02.bas i := 10; j := 12; k:= 14 if j-i == k-j then n := 1 elem := k while n <= 5 do elem := elem + k - j print elem n := n + 1


28 9 10

wend end


3. fejezet

Tömbök a While nyelvben Az eddigi programokban minden változót, a memóriának minden névvel ellátott területét saját névvel láttuk el. Sokszor azonban nem akarunk nevet adni minden változónak, hanem azonos névvel szeretnénk elérni több változót is. A metamatikában a változók azonos névvel való jelölésére általában az indexelt jelölést használjuk, ahogyan azt a következo˝ példa is bemutatja: x=

PN

i=0 xi N +1

A példa a matematikai átlag kiszámításának módját írja le. A képlet alapján N +1 darab változó matematika átlagát úgy számíthatjuk ki, hogy összeadjuk a változók értékét és elosztjuk az elemek számával1 . Figyeljük meg, hogy a képletben a változók jelölésére az x betut ˝ használtuk, azt pedig, hogy az adott változónéven belül melyik melyik konkrét értékr˝ol beszélünk, az index segítségével határoztuk meg. Az x változó tehát N + 1 érték tárolására alkalmas, az értékekre az xi jelöléssel hivatkozunk, ahol i adott tartományon belüli egész számot jelöl. Az ilyen eszközt általában egy dimenziós tömbnek vagy vektornak nevezzük. A While értelmez˝oprogram képes vektorokat kezelni a következo˝ jelölés alapján: • Vektor elemére való hivatkozás: xi 1 A képlet kissé eltér a szokásos formulától. Ennek az az oka, hogy a legtöbb matematikus szerint az elemeket 1-to˝ l számozzuk, a programozók szerint pedig 0-tól.

29


30 • Vektor elemére való hivatkozás (programban): ... x[i] ... A kifejezés az x vektor i-edik elemére hivatkozik. Az x helyén tetszo˝ leges változónév, az i helyén pedig tetszo˝ leges, numerikus értéket adó kifejezés állhat, amelyet az értelmezo˝ program egész értékre alakít. A vektorok elemeinek számozása 0-tól indul, a lehetséges indexértékek i = 0, 1, 2, . . . számára fels˝o korlátot csak a rendelkezésre álló operatí memória és virtuális memória szab határt. A következ˝o oldalakon vektorok kezelését végz˝o példaprogramokat találunk. A példaprogramok segítségével összetettebb vezérlo˝ szerkezetekkel, nyelvi kifejezésekkel, illetve bonyolultabb eljárásokkal ismerkedünk meg.

3.1. A legnagyobb elem kiválasztása Talán a legegyszerubb ˝ feladat, amelyet a vektorokkal kapcsolatban el lehet képzelni a legnagyobb vagy legkisebb elem kiválasztása. Ezt a feladatot végzi el a következ˝o program (a program elején található értékadásokat helytakarékosság céljából nem újsorkarakterekkel, hanem ; karakterekkel választottuk el): 1 2 3 4 5 6 7 8 9 10 11 12 13 14

arrays/max.bas rem Tömb legnagyobb elemének kikeresése. a[0] := -10; a[1] := -18; a[2] := -8; a[3] := -77; max := a[0] n := 1 while n <= 3 do if max < a[n] then max := a[n] end n := n + 1 wend print max

A program az 5. sorban „feltételezi”, hogy a legelso˝ elem a legnagyobb, majd az összes elemet végigjárva újra- és újra összehasonlítja az elemeket a feltételezett legnagyobb elemmel. A 8–10. sorokban a program a vektor


31 adott elemét legnagyobbként választja ki, ha az az addig talált legnagyobb elemnél nagyobb. Figyeljük meg, hogy a max változó mindeig az adott elemig talált legnagyobb elemet tartalmazza! A program kapcsán a következ˝o tényre érdemes felfigyelnünk: • A while kifejezésen beül bármilyen kifejezések szerepelhetnek, így az if kifejezés ciklikus végrehajtására is módunk van.

3.2. A tartomány kiszámítása A következ˝o példaprogram szintén nagyon egyszeru ˝ feladatot lát el, kiszámatja, hogy a vektor mekkora tartományt foglal el. A tartomány a legnagyobb elem és a legkisebb elem különbsége. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

arrays/range.bas rem A tartomány kiszámítása. a[0] := -10; a[1] := -18; a[2] := -8; a[3] := -77; max := a[0] min := a[0] n := 1; while n <= 3 do if max < a[n] then max := a[n] end if min > a[n] then min := a[n] end n := n + 1 wend print max - min A program muködése ˝ az eddigi ismeretek alapján könnyen megértheto˝ .

3.3. A matematikai átlag kiszámítása A matematikai átlag – ahogyan azt már bemutattuk – az elemek összegének és az elemek számának hányadosa. A matematikai átlag kiszámítását végzi el a következ˝o példaprogram:


32

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

arrays/average.bas rem Matematikai átlag kiszámítása. a[0] := -10; a[1] := -18; a[2] := -8; a[3] := -77; n := 0 sum := 0 while n <= 3 do sum := sum + a[n] n := n + 1 wend if n > 0 then print sum / n else print 0 end

Figyeljük meg, hogy a program a 12. sorban megvizsgálja, hogy az elemek száma egyenl˝o-e 0-val, pedig a 7. sorban kezd˝od˝o while kifejezésb˝ol egyértelmuen ˝ kiderül, hogy a 12. sorban n = 3. Ez a feleslegesnek tun ˝ o˝ ellen˝orzés azonban lehet˝ové teszi, hogy a program elejét, az elemszámot tetsz˝olegesen megváltoztassuk anélkül, hogy a 13. sorban a 0-val való osztás veszélye felmerülne. A program szerint a 0 darab elemet tartalmazó számhalmaz matematikai átlaga 0. A konkrét feladat megoldását végz˝o programok esetében nyilván másképpen is dönthetünk.

3.4. Elem beszúrása és eltávolítása Igen gyakran van szükségünk arra, hogy vektorokba elemeket szúrjunk be vagy onnan elemeket távolítsunk el. Az elem beszúrása és törlése nem túl bonyolult feladat, de kezd˝o programozók sokszor vétenek hibát az ilyen jellegu ˝ programokban. A legtöbb problémát az okozza, hogy a beszúrás és eltávolítás során a vektor adott területén található elemeket át kell helyeznünk a vektor más területeire. A mozgatás tehát a vektoron belül történik, így fennáll az elemek véletlen felülírásának veszélye. Tegyük fel, hogy a 2 elemu ˝ vektor 0 helyére szeretnénk beszúrni a 13 érté-


33 ket. Azt gondolnánk, hogy a következ˝o módszer megoldást ad: x0 = 13 x1 = x 0 x2 = x 1 Ha figyelmesen végigkövetjük az értékadásokat, azonnal láthatjuk, hogy az elvégzésük után mindhárom elem értéke 13 lesz, ami nem szerencsés 2 . A következ˝o megoldás helyes eredményt ad: x2 = x 1 x1 = x 0 x0 = 13 A következ˝o program egy 4 elemu ˝ vektor legels˝o helyére szúr be egy új értéket az eredeti elemek értékét mozgatással mego˝ rizve: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

rem Elem beszúrása.

arrays/insert.bas

a[0] := -10; a[1] := -18; a[2] := -8; a[3] := -77; rem Kiírjuk az elemeket a képerny˝ ore. n := 0 while n <= 3 do print a[n] n := n + 1 wend rem Beszúrjuk az új elemet a tömb elejére. n := 4 while n >= 1 do a[n] := a[n-1] n := n - 1 wend a[0] := 13

2 Könnyu ˝ belátni, hogy a megoldás rossz, az elemeket az értékadások megváltoztatják, miel˝ott felhasználták volna az értéküket. Bármilyen furcsa azonban, igen sokan követnek el ilyen jellegu ˝ hibát, nyilvánm azért, mert a programban található ciklikus végrehajtást még nem szokták meg, nem látják át azonnal.


34 21 22 23 24 25 26

rem Újra kiírjuk az elemeket. n := 0 while n <= 4 do print a[n] n := n + 1 wend

A programot az eddigi ismeretek segítségével könnyen megérthetjük, de néhány dologra érdemes felhívni a figyelmet: • Vektor elemeinek mozgatása közben fennáll a felülírás veszélye, ha a forrás és célterület átlapolódik (közös elemük van). Ilyen esetben érdemes egy rajzon végigkövetve ellen˝orizni a program muködését. ˝ • Ha a célterület a forrásterület felett található, és a két terület átlapolódik, a másolást végz˝o ciklusnak csökken˝o indexérték szerint kell haladnia. • Ha a vektorban újabb elemet szúrunk be, annak mérete növekszik. Mivel a vektor méretét külön tartjuk nyilván, gondoskodnunk kell a program a megváltozott méretet vegye figyelembe. A következ˝o példaprogram egy elemet – az 1 indexu ˝ elemet – eltávolít a vektorból. Mivel nem az utolsó elemet távolítjuk el a vektorból, ismét szükség van az elemek áthelyezésére. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

arrays/remove.bas rem Elem eltávolítása. a[0] := -10; a[1] := -18; a[2] := -8; a[3] := -77; rem Kiírjuk az elemeket a képerny˝ ore. n := 0 while n <= 3 do print a[n] n := n + 1 wend rem Eltávolítjuk az 1-es index˝ u elemet. n := 2 while n <= 3 do a[n - 1] := a[n] n := n + 1 wend rem Újra kiírjuk az elemeket a képerny˝ ore.


35 20 21 22 23 24

n := 0 while n <= 2 do print a[n] n := n + 1 wend

A feladat megoldásakor az el˝oz˝o feladathoz hasonlóan most is az elemek áthelyezésére van szükség, most azonban a célterület a forrásterület alatt található. A program muködése ˝ könnyen megértheto˝ , ha egy rajzon végigkövetjük az egyes lépéseket. A program muködése ˝ kapcsán a következo˝ tényekre érdemes felhívni a figyelmet: • Ha a vektorból elemeket távolítunk el, a vektor mérete csökken.

• Ha az elemek áthelyezése során a célterület a forrásterület alatt található és a két terület átlapolódik, az áthelyezést végzo˝ ciklikus kifejezésnek növekv˝o indexérték szerint kell haladnia. Az elemek eltávolítása és az elemek beszúrása kapcsán meg kell említenünk, hogy mindkét példaprogram olyan ciklikus szerkezetet használt, amelyben két indexérték is szerepelt (n és n − 1). Az ilyen ciklusok határait (kezd˝o és végértékét) különös gondossággal kell kezelnünk!

3.5. A matematikai sorozat A matematikai sorozat szomszédos elemeinek különbsége állandó: xi − xi−1 = d

(3.1)

mégpedig ∀i = 1, 2, . . . , N értékekre3 . Ebb˝ol következik, hogy xi = xi−1 + d

(3.2)

formula alapján az adott elemb˝ol kiszámítható a rákövetkez˝o elem értéke. A következ˝o példaprogram megvizsgálja, hogy egy vektor elemei matematikai sorozatot alkotnak-e és ha igen, akkor kiszámítja a sorozat néhány következ˝o elemét és elhelyezi a vektorban. 1 2 3 4

arrays/series.bas rem Matematikai sorozat folytatása. a[0] := -10; a[1] := 0; a[2] := 10; a[3] := 20; a[4] := 30; a[5] := 40; a[6] := 50; a[7] := 60; 3 Az

elemeket ismét 0-tól számozzuk, azaz a megengedett legkisebb indexérték a 0.


36 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

rem Ellen˝ orzés. sorozat := 1 diff := a[1] - a[0] n := 2 while n <= 7 do if diff <> a[n] - a[n - 1] then sorozat := 0 end n := n + 1 wend rem Folytatás. if sorozat then rem Folytatás n := 8 while n <= 20 do a[n] := a[n - 1] + diff n := n + 1 wend rem Kiírás. i := 0 while i <= 20 do print a[i] i := i + 1 wend end

A program a 10–15. sorokban megvizsgálja, hogy a vektor elemeire igaz-e a 3.1. egyenl˝oség. Ha csak egyetlen elemre is hamisnak bizonyul az egyenl˝oség, a program a 11–13. sorok feltételes utasításvégrehajtása értelmében logikai hamis értéket helyez el a sorozat nevu ˝ változóban. A program a 18–32. sorokban található feltételes utasításvégrehajtás alapján folytatja a sorozatot, ha az az el˝oz˝oekben matematikai sorozatnak bizonyult. Az egyes elemek kiszámítása a 3.2. formula alapján történik 21–24. sorok ciklikus végrehajtásával a 22. sorban.

3.6. Az elemek transzponálása Sokszor van szükségünk arra, hogy a tömb elemeit adott tartományba képezzük le. Az ilyen transzponálási feladatokra az összeadás (kivonás), illetve


37 a szorzás (osztás) muveletét ˝ használhatjuk ahogyan azt a középiskolában a függvények és a koordinátageometria témakörében megismertük. Ha például adott egy ai vektor és szeretnénk elérni, hogy a tömb legkisebb eleme m értéket vegyen fel, akkor használhatjuk a következo˝ összefüggést: ai = ai + m − min(a)

(3.3)

ahol min(a) a vektor legkisebb eleme. Ez a formula a tömb minden elemének értéket megnöveli (vagy csökkenti) annyival, hogy a legkisebb elem értéke éppen m legyen. Mivel a formula minden egyes elemet azonos értékkel növel – illetve csökkent –, az elemek közti különbség nem változik. Ha például m = 8 és a tömb legkisebb értéke min(a) = 10, akkor a formula m − min(a) = −2, azaz minden elemet ketto˝ vel csökkentünk. A tömb legkisebb eleme tehát 10 + m − min(a) alapján 8 lesz. Sok esetben úgy akarjuk átalakítani a vektor elemeinek értékét, hogy azok egy adott tartományba essenek. Ilyenkor a vektor legnagyobb és legkisebb értéke is az el˝ore meghatározott értéket veszi fel a transzponálás után. Nyilvánvalóan úgy végezzük el az átalakítást, hogy az elemek közti különbségek arányait megtartjuk. Az ilyen átalakításokat egyszeruen ˝ elvégezhetjük, ha elso˝ lépésben a tömb minden eleméhez annyit adunk hozzá, hogy a legkisebb elem az elo˝ re meghatározott értéket vegye fel (3.3. formula), majd minden elemet akkora értékkel szorzunk, hogy a legnagyobb elem az el˝ore meghatározott értéket vegye fel. A transzponálást elvégz˝o formula és program elkészítését gyakorlásképpen az olvasóra bízzuk.

3.7. Rendezés A számítástechnikában a rendezésen (sort) az elemek nagyság szerinti sorrendbe való átrendezését értjük. A számok kapcsán a rendezés mindig egyértelmu, ˝ hiszen egyértelmu, ˝ hogy a számok esetében a ≤, illetve ≥ muveletet ˝ hogyan értelmezzük. Az a tömb elemeit rendezettnek tekintjük, ha az tömb minden elemére i > j ⇒ a i ≥ aj

(3.4)

i > j ⇒ a i ≤ aj

(3.5)

azaz, ha a nagyobb indexu ˝ helyen mindig legalább akkora érték található, mint a kisebb helyen. A tömb elemeit fordított sorrend szerint rendezettnek tekintjük, ha a tömb minden

azaz, ha a nagyobb indexu ˝ helyen mindig legfeljebb akkora érték található, mint a kisebb értéku ˝ helyen.


38 A rendezés elvégzésére több módszer is ismeretes, amelyek közül nem egy bonyolult, összetett, nem egynek komoly ero˝ feszítést igényel a megértése. A legegyszerubb ˝ – és ezért nem túl hatékony – rendezési módszer a buborékrendezés, amelyet szomszédcserés rendezésnek is szokás nevezni. A buborékrendezés lényege, hogy el˝obb a tömb végére mozgatjuk a legnagyobb elemet, majd a utolsó el˝otti helyre tesszük a maradék elemek között található legnagyobb elemet, majd a utolsó el˝otti el˝ott található helyre helyezzük a maradék elemek közt található legnagyobb elemet és így tovább. A buborékrendezés tehát visszavezetheto˝ a legnagyobb elem kiválasztására, ami nyilvánvalóan nagymértékben megkönnyíti a program elkészítését. A következ˝o program a buborékrendezés módszerének felhasználásával rendezi növekv˝o sorrendbe adott tömb elemeit. A program a szakmában bevett módszer alapján nem különíti el a legnagyobb elemet, egyszeruen ˝ csak feljebb mozgatja az adott elemet, ha azt az o˝ t megel˝oz˝o elemnél nagyobbnak találja. A program muködésének ˝ megértésé feladatul az olvasóra bízzuk. arrays/sort.bas 1 rem Rendezés (buborékrendezés) 2 3 a[0] := -10; a[1] := -18; a[2] := -8; a[3] := -77; 4 a[4] := 21; a[5] := -9; a[6] := -110; a[7] := -200; 5 elemek := 8 6 7 k := 0 8 while k < elemek - 1 do 9 m := 0 10 while m < elemek - k - 1 do 11 if a[m] > a[m + 1] then 12 tmp := a[m] 13 a[m] := a[m + 1] 14 a[m + 1] := tmp 15 end 16 m := m + 1 17 wend 18 k := k + 1 19 wend 20 21 rem Rendezett vektor elemeinek kiírása. 22 n := 0 23 while n < elemek do 24 print a[n] 25 n := n + 1 26 wend A rendezésre vonatkozó apró szakasz végén meg kell említenünk, hogy


39 habár a rendezés témaköre meglep˝oen bonyolult, a rendez˝oprogramok mu˝ ködésének megértése sokszor nehezen értheto˝ , a gakorlatban ritkán van rendez˝oprogram készítésére szükség. Ennek egyszeruen ˝ az az oka, hogy a legtöbb fejleszt˝okörnyezet könyvtári eszközként biztosítja a rendezéshez szükséges eszközöket, ezért ezeket az alkalmazásprogramozónak nem kell elkészítenie.

3.8. Keresés A tömb elemeinek keresése igen könnyen elvégezheto˝ . Ha meg akarjuk keresni az adott értékkel rendelkez˝o tömbelemet, egyszeruen ˝ végig kell nézni az elemeket és értéküket össze kell hasonlítani a keresett értékkel. A keresést befejezhetjük, ha az adott értéket megtaláltuk a tömbben, ha viszont az utolsó tömbelem értéke sem egyezik meg a keresett értékkel, akkor az adott érték nem található meg a tömb értékei közt. A legtöbb gyakorlati feladat megoldása közben kínosan kell ügyelnünk erre a második esetre, azaz a keresés befejezése után mindig meg kell vizsgálnunk, hogy a keresés sikeres volt-e. A következ˝o program az ilyen egyszeru, ˝ lineáris keresést mutatja be. A program muködése ˝ magától értet˝od˝o. arrays/search01.bas 1 rem Keresés rendezetlen vektorban. 2 3 a[0] := -10; a[1] := -18; a[2] := -8; a[3] := -77; 4 a[4] := 21; a[5] := -9; a[6] := -110; a[7] := -200; 5 elemek := 8 6 7 keresett := -110 8 k := 0 9 while k < elemek do 10 if a[k] == keresett then 11 print k 12 end 13 k := k + 1 14 wend A lineáris keresés hatásfoka igen gyenge, ezért csak a legrittkább esetben használjuk. Nyilvánvaló, hogy egy N elemu ˝ tömb elemének kikereséséhez legjobb esetben 1 lépésre (ha az elso˝ elem a keresett elem), legrosszabb esetben viszont N (ha a keresett elem az utolsó elem) lépésre van szükség. A valószínuségszámítás ˝ segítségével könnyen belátható, hogy véletlenszeru ˝ helyzetu ˝ elem esetében átlagosan N2 lépésre van szükség, ami nagyméretu ˝ elemszám esetén iszonyatosan lelassíthatja a program muködését. ˝


40 Rendezett tömbökben nagymértékben felgyorsíthatjuk a keresést, ha az úgynevezett bináris kere˝oalgoritmust használjuk. A bináris keresés módszere könnyen megérthet˝o, hiszen sokszor magunk is használjuk, ha keresést végzünk rendezett elemek között. Ha például egy adott oldalszámot keresünk egy könyvben, akkor el˝oször középen nyitjuk ki, megnézzük, hogy a keresett oldalszám nagyobb-e mint az a pont, ahol a könyvet felütöttük. Ha a keresett oldalszám nagyobb mint a megtalált oldalszám, a jobb kéz fel˝oli lapok közepét, illetve ha kisebb, bal kéz felo˝ li lapok közepét választjuk újabb keresési pontként. A könyvlapok felezésével elérjük, hogy ne kelljen egyenként végignézni a köny lapjait. Hasonló módszert az mindennapjainkban sokszor végzünk, néha tudatosan, néha pedig annyira magától érteto˝ d˝o módon, hogy fel sem tunik. ˝ A következ˝o példaprogram bináris keresést végez rendezett vektorban. A program a minden keresési lépésben nyilvántartja a vizsgált tartomány alsó és fels˝o határát, a felez˝opontot és a fels˝o vagy az alsó tartományt jelöli ki célterületként. Ha a vizsgált tartomány elemszáma 0, a keresés eredménytelenül végz˝odött, biztos, hogy a keresett elem nem található meg az elemek halmazában. A módszer természetesen csak rendezett elemek esetén használható. arrays/search01.bas 1 rem Keresés rendezett vektorban. 2 3 a[0] := -10; a[1] := -9; a[2] := -8; a[3] := -7; 4 a[4] := -6; a[5] := -5; a[6] := -4; a[7] := -2; 5 6 keresett := -6 7 also := 0 8 felso := 7 9 kozepso := (felso - also) / 2 10 11 while 1 do 12 if keresett < a[kozepso] then 13 felso := kozepso 14 end 15 if keresett > a[kozepso] then 16 also := kozepso 17 end 18 if also == felso then 19 quit 20 end 21 if a[kozepso] == keresett then 22 print kozepso 23 quit 24 end


41 25 26

kozepso := also + (felso - also) / 2 wend

A példaprogram kapcsán meg kell jegyeznünk, hogy a While értelmezo˝ program nem csak egész számokat kezel, ezért a program néha váratlan módon viselkedik (1, 25-dik elem). A program muködik, ˝ minden elrendezés esetén helyes eredményt ad, de néha a szükségesnél több lépésben ad eredményt.

3.9. Feladatok 1. Készítsen programot, amely egy vektor legkisebb elemét keresi meg! A program csak a legkisebb elem értékét írja ki a szabványos kimenetre! 2. Készítsen programot, amely a legnagyobb elemet keresi meg, de úgy, hogy a tönbindexet csökkentve halad a tömbelemeken! 3. Készítsen programot, amely vektor legnagyobb elemét keresi meg, de a keresés során nem a vektor legnagyobb elemének értékét, hanem a vektor legnagyobb elemének indexét tartja nyilván! 4. Készítsen programot, amely egy vektor elemeinek matematikai átlagát számítja ki, de úgy, hogy a 100-nál nagyobb értékeket nem veszi figyelembe. 5. Készítsen programot, amely egy tömb elemeinek a matematikai átlaguktól számított legnagyobb eltérését számítja ki! Vegy figyelembe, hogy az elemek értéke kisebb és nagyobb is lehet a matematikai átlagnál! 6. Készítsen programot, amely három új elemet szúr be egy 10 elemu ˝ vektor els˝o három helyére! 7. Készítsen programot, amely egy új elemet szúr be a 10 elemu ˝ tömb 5 indexu ˝ elemének helyére! A program o˝ rizze meg a vektorban található elemeket és sorrendjüket! 8. Készítsen programot, amely egy vektor tetszo˝ leges területét tetsz˝oleges irányba és távolságra áthelyezi! A program vizsgálja meg, hogy a célterület a forrásterület alatt vagy felett helyezkedik el és a megfelel o˝ irányba haladva végezze el az elemek áthelyezését! 9. Készítsen programot, amely megállapítja egy vektorról, hogy az rendezett-e!


42 10. Készítsen programot, amely kikeresi egy tömb legnagyobb elemét és eltávolítja azt a tömbb˝ol! 11. Készítsen programot, amely a tömb három legnagyobb elemét távolítja el! A program el˝obb rendezze sorba az elemeket és aztán távolítsa el az els˝o (vagy utolsó) három elemet! 12. Készítsen programot, amely két rendezett vektort másol egy új vektorba úgy, hogy az eredményül kapott vektor szintén rendezett legyen! A program a másolás közben mindig abból a vektorból vegye a következ˝o elemet, amelynek els˝o eleme nagyobb! 13. Készítsen programot, amely egy vektor elemeinek sorrendjét ellentétesre változtatja, azaz megfordítja a vektort! 14. Készítsen programot, amely adott vektorelem minden eleméhez akkora – pozitív vagy negatív – értéket ad, hogy a legkisebb elem értéke 0 legyen! 15. Két tömb, A és B az egész számok egy-egy hamazát tartalmazza. Készítsen programot, amely a két halmaz únióját számítja ki! 16. Két tömb, A és B az egész számok egy-egy halmazát tartalmazza! Készítsen programot, amely a két halmaz metszetét számítja ki! 17. Készítsen programot, amely három – tömbben tárolt – halmaz únióját számítja ki! 18. Készítsen programot, amely adott vektorból létrehozza az átlagostól való eltéréseket tartalmazó vektort! Az eredeti vektor ai elemének helyén az új vektorban található bi elem értéke legyen |a − ai |, ahol a jelöli a matematikai átlagot, |x| pedig az abszolútérték jelölésére szolgál. 19. Készítsen programot, amely megkeresi egy vektor átlagához legközelebb álló elemét, azt az elemet, amelynek átlagtól való eltérése a legkisebb!

20. Készítsen programot, amely az adott vektor minden eleméhez akkora értéket ad, valamint a vektor minden elemét akkora értékkel szorozza, hogy a vektor legkisebb eleme 0, legnagyobb eleme pedig 1000 legyen! (Ne feledjük, hogy a While értelmez˝o kezeli a tizedes törteket is!) 21. Két tömb a sík pontjainak x, illetve y koordinátáit tartalmazza. Készítsen programot, amely kiválogatja azokat a pontokat, amelyek illeszkednek adott y = ax + b egyenesre!


43 22. Legyen

p(x) = a0 + a1 x + a2 x2 + · · · + an xn

n-ed fokú polinom, az a tömb pedig tartalmazza a polinom ai együtthatóit. Készítsen programot, amely kiszámítja a p(x) értékét adott x helyen! 23. Készítsen programot, amely tetsz˝oleges két polinomról eldönti, hogy melyik képvisel nagyobb értéket adott x helyen!


44


4. fejezet

Törtek kezelése a While nyelvben Nyilvánvaló, hogy minden adat kódolható egész számok formájában, de a legtöbb programozási nyelv képes törteket is kezelni. A valós számok halmazának elemein számításokat végz˝o programok a számokat általában tizedes törtként képesek megjeleníteni és a hasonló formában adott számokat képesek számként értelmezni. A következ˝o oldalakon olyan egyszeru ˝ programokat láthatunk, amelyek törtszámokon végeznek muveleteket. ˝ A While értelmezo˝ program a már bemutatott muveleteket ˝ bizonyos pontosságig törteken is elvégzi, de az eredményt csak akkor írja ki tizedes tört formájában, ha indításkor a -p kapcsolót kapja. A törtekkel végzett muveletek ˝ kapcsán meg kell jegyeznünk, hogy a számítógép a valós számokat csak véges pontossággal képes kezelni, ami oly összetett problémákat okoz, hogy a matematika külön ága foglalkozik a kérdéssel.

4.1. Osztás Az egész számokon végzett osztás nem feltétlenül ad egész értéket eredményül. A következ˝o példaprogram bemutatja hogyan végezhetjük el az osztást maradékos formában, úgy, hogy az eredmény mindig egész szám legyen. 1 2 3 4

While/alap/20osztas.bas rem Legyen n = x/y (egész)! x := 17 y := 4 45


46 5 6 7 8 9 10 11 12

s := x n := 0 while s >= y do s := s - y n := n + 1 wend print n print s

A While az osztás eredményének és a maradéknak a kiszámítására a következ˝o muveleti ˝ jeleket használja: • Hányados: x := a / b Meg kell azonban jegyeznünk, hogy a program lebeg˝opontos aritmetikát használ, azért ennek a muveletnek ˝ az eredménye tizedestört is lehet! • Maradék: x := a % b Ez az egész osztás maradéka, amelyre n = a%b esetében 0 ≥ n ≥ b − 1 egész szám.

4.2. Legnagyobb közös osztó Az osztás muvelete ˝ után logikusan következik a legnagyobb közös osztót kiszámító program bemutatása. A következo˝ módszer segítségével kiszámíthatjuk két egész szám legnagyobb közös osztóját – ami természetesen szintén egész szám: 1. Legyen r a p/q osztás maradéka! 2. Ha r = 0, akkor a legnagyobb közös osztó q. 3. Legyen p = q és q = r! 4. Ismételjük az eljárást az 1. ponttól! A bemutatott módszer alapján készült a következo˝ példaprogram, amely a módszer egy lehetséges megvalósítása:


47

1 2 3 4 5 6 7 8 9 10 11 12

While/math/02lnko.bas p := 876; q := 8687 r := p % q p := q q := r while q <> 0 do r := p % q p := q q := r wend print p

Figyeljük meg a példaprogramban, hogy a while kifejezésben ismételt utasítások a while kifejezés el˝ott is megtalálhatók. A program tehát a ciklikus végrehajtás el˝ott egyszer biztosan végrehajtja ezeket az utasításokat (a while kifejezésen belül található utasítások nem feltétlenül hajtódnak végre). Ha olyan ciklikus végrehajtásra van szükségünk, amelynek utasításai egyszer biztosan végrehajtódnak, akkor használhatjuk az úgynevezett hátultesztel˝o ciklikus kifejezéseket, amelyek a ciklikus végrehajtás feltételének a vizsgálatát a ciklikusan végrehajtott utasítások végrehajtása után végzik el. Az ilyen kifejezések egyszer biztosan végrehajtáják a belso˝ utasításokat. A While a hátultesztel˝o ciklikus kifejezésre a következ˝o formát használja: • Repeat utasítás: repeat ... until q = 0 • Programban: repeat ... until q = 0 Ügyeljünk arra, hogy a repeat ciklus feltételének értelmezése ellentétes a while ciklus feltételével összevetve. (Ebben a nyelvben!) A legnagyobb közös osztó kiszámítására készült programot a hátultesztelo˝ ciklikus kifejezésre átírva némiképpen egyszerubb ˝ programot kapunk: 1 2

While/alap/21repeat.bas p := 876; q := 8687


48 3 4 5 6 7 8 9

repeat r := p % q p := q q := r until q == 0 print p

4.3. Gyökvonás A gyökvonás elvégzésére a legegyszerubb ˝ módszer az úgynevezett Newton √ iteráció, amely n kiszámítására x0 = 1 és n 1 xk + (4.1) xk+1 = 2 xk Figyeljük meg, hogy a módszer egy adott xk+1 kiszámításához mindig fel√ használja az el˝oz˝oleg kiszámított xk értékét és így fokozatos közelíti n értékét. Nyilvánvaló, hogy minél többször végezzük el az iterációs lépést, annál pontosabb eredményt kapunk. A következ˝o példaprogram a bemutatott módszert használja adott szám négyzetgyökének kiszámítására: While/alap/21repeat.bas 1 rem Gyökvonást megvalósító program (Newton iteráció) 2 n := 2 3 k := 1 4 x := 1 5 while k < 100 do 6 x := (1/2) * (x + n / x) 7 k := k + 1 8 wend 9 10 print x

4.4. Állandó közelítése Számítsuk ki ln 2 állandó értékét az ln 2 = 1 −

1 1 1 1 + − + −··· 2 3 4 5

összefüggés alapján! A feladatot elvégzi a következo˝ program:


49

1 2 3 4 5 6 7 8 9 10 11

While/peldak/04-ln2.bas nevezo := 1 lnketto := 0 while nevezo<50000 do if nevezo%2 == 0 then lnketto := lnketto - 1/nevezo else lnketto := lnketto + 1/nevezo end nevezo := nevezo + 1 wend print lnketto

Figyeljük meg, hogy a formula ugyan most másképpen jelezte a muvele˝ tek ismétl˝od˝o jellegu ˝ végrehajtását, a programban azonban a megszokott módon, a while kifejezéssel írtuk el˝o az ismétlést!

4.5. Függvény közelítése Az el˝oz˝o példaprogram alapján könnyen készíthetünk programot sin x értékének kiszámítására ha felhasználjuk a sin x = x −

x5 x7 x9 x3 + − + −··· 3! 5! 7! 9!

(4.2)

összefüggést. A program muködését ˝ felgyorsíthatjuk, ha a többtagú összeg tagjait mindig az el˝oz˝o tagból számítjuk ki! A While értelmez˝o az egyszeruség ˝ érdekében elfogadja a 4.1. táblázatban felsorolt függvényeket.

4.5.1. Függvények ábrázolása A függvények ábárolását sokféleképpen, sokféle program segítségével ábrázolhatjuk. A legegyszerubb ˝ módszer az, ha a While által kiírt adatokat a szabványos bemenetr˝ol egy állományba irányítjuk, majd az így kapott szöveges állományt valamilyen segédprogrammal grafikusan ábrázoljuk. A While ezt a munkát a következ˝o kifejezésekkel támogatja: newline Az önmagában álló newline utasítás hatására a While egy üres sort ír a szabványos kimenetre. Az üres sor elhelyezésére a kétváltozós függvények három dimenziós ábrázolásához lehet szükségünk. printnl x A kifejezés a print utasítás esetében már bemutatott módon muködik, ˝ de a szám kiírása után a While nem helyez el újsor karaktert, így egy sorba több számot is írhatunk.


50 Jelölés acos(x) asin(x) atan(x) cbrt(x) cos(x) cosh(x) exp(x) log10(x) log() sinh(x) sin(x) sqrt(x) tanh(x) tan(x)

Jelentés arkusz koszinusz arkusz szinusz arkusz tangens √ köbgyök ( 3 x) koszinusz koszinusz hiperbolikusz exponenciális fgv. (ex ) 10-es alapú logaritmus természetes alapú logaritmus szinusz hiperbolikusz szinusz √ négyzetgyök ( x) tangens hiperbolikusz tangens

4.1. táblázat. A While beépített függvényei

A következ˝o példaprogram sin(x) és sin(5x) értékét számítja ki és írja ki a kimenetre. 1 2 3 4 5 6 7 8 9 10 11 12

While/math/03sin.bas rem A sin(x) és a sin(5x) függvények rem kirajzolására használt program. x := 0 while x < printnl printnl print

6.29 do x sin(x) sin(5*x)

x := x + 0.01 wend

A program a szabványos kimenetre írja a kiszámított értékeket, minden sorba három számot. Az els˝o szám x, a második sin(x), a harmadik pedig sin(5x) értékét tartalmazza. Figyeljük meg a print és printnl utasítások használatát! A programot futtatva annak szabványos kimenetét állományba irányíthatjuk a következ˝o módon: $ While -p <03sin.bas >sin.data $


51 A program által készített sorok szerkezetés mutatja be a következo˝ parancs. Figyeljük meg, hogy a While -p kapcsolója hatására az adatok tizedestört formában jelentek meg. $ head -n 5 sin.data 0.000000000000000000 0.010000000000000000 0.020000000000000000 0.029999999999999999 0.040000000000000001 $

0.000000000000000000 0.009999833334166664 0.019998666693333080 0.029995500202495660 0.039989334186634161

0.000000000000000000 0.049979169270678331 0.099833416646828155 0.149438132473599217 0.198669330795061216

Szöveges adatok ábrázolására többek közt a Gnuplot programot is használhatjuk. A Gnuplot számára egy szöveges állományban adhatjuk meg, hogy melyik állományban találhatók az ábrázolandó adatok, azokat milyen módon, milyen formában kívánjuk ábrázolni. A következo˝ példa bemutatja hogyan ábrázolhatunk két adatsort egyenes vonalakkal összekötött pontok segítségével: 1 2 3 4 5 6 7

While/math/sin.gnuplot set terminal postscript set output "sin.ps" set zeroaxis set nokey plot "sin.data" using 1:2 notitle with lines,\ "sin.data" using 1:3 notitle with lines

Az adatok ábrázolását végz˝o Gnuplot programot a következ˝o egyszeru ˝ formában futtathatjuk: $ gnuplot sin.gnuplot $

Figyeljük meg, hogy a program futtatásakor egyszeruen ˝ csak a Gnuplot leíróállomány nevét kell megadnunk, a program a többi információt a leíróállományból, illetve az adatállományból olvas. A Gnuplot által készített grafikont a 4.1. ábrán láthatjuk.

4.6. Függvénysorok Ábrázoljuk a következ˝o függvényt az els˝o néhány tagjának kiszámításával! f (x) =

sin(nx) n n=1,3,... X

A következ˝o program kiszámítja a függvényértékeket:

(4.3)


52 1 0.8 0.6 0.4 0.2 0 -0.2 -0.4 -0.6 -0.8 -1

0

1

2

3

4

5

6

7

4.1. ábra. A sin(x) és sin(5x) értékek ábrázolása

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

While/math/04negyzet.bas rem A sávkorlátozott négyszögjel. x := 0 while x < 6.29 do n := 1 fx := 0 while n < 15 do fx := fx + sin(n * x) / n n := n + 2 wend printnl x print fx x := x + 0.01 wend

A függvény ábrázolásához (4.2. ábra) használhatjuk a következo˝ Gnuplot programot, amely a kimeneti állományban LATEX formátumú képet helyez el: 1

While/math/negyzet.gnuplot set terminal latex


53 1 0.8 0.6 0.4 0.2 0 -0.2 -0.4 -0.6 -0.8 -1

0

1

2

3

4

5

6

7

4.2. ábra. A sávkorlátozott négyszögjel 2 3 4 5 6

set output "negyzet.tex" set zeroaxis set nokey plot "negyzet.data" using 1:2 notitle with lines

4.7. Kétváltozós függvények Kétváltozós függvények megjelenítésekor ügyelnünk kell arra, hogy az egyes x vagy y adatsorok közt egy üres sort helyezzünk el a szöveges állományban, ha az adatokat a Gnuplot programmal kívánjuk megjeleníteni. A következo˝ 2 program ilyen formában számolja ki az f (x, y) = x2 + y2 függvény értékeit. 1 2 3 4 5 6

While/math/negyz3d.bas rem Kétváltozós függvény ábrázolása. x := -2 while x <= 2 do y := -4 while y <= 4 do


54

12 10 8 6 4 2 0 -2 -1.5

-1 -0.5

0 0.5

1 1.5

2 -4

-3

-2

-1

0

1

2

3

4

4.3. ábra. Kétváltozós függvény ábrázolása a nem látható élek kitakarásával 7 8 9 10 11 12 13 14 15

fxy := x*x + y*y/2 printnl x printnl y print fxy y := y + 0.2 wend newline x := x + 0.2 wend

A függvény megjelenítésére használhatjuk a következo˝ Gnuplot programot, amelynek eredményét a 4.3. ábrán láthatjuk. 1 2 3 4 5 6 7

While/math/negyz3d.gnuplot set terminal latex set output "negyz3d.tex" set zeroaxis set nokey set hidden3d splot "negyz3d.data" with lines


55

4.4. ábra. Kétváltozós függvény interaktív megjelenítése Ha a Gnuplot programban nem adunk meg kimen˝o állománynevet, az ábra a képerny˝on jelenik meg (4.4. ábra). Ilyenkor az ábrán az egér segítségével beállíthatjuk a néz˝opontot, az ábrát „megforgathatjuk”. A képerny˝on használhatjuk a pm3d megjelenítési módot, amely „kitölti” a felületet, nem csak egyszeru ˝ drótvázként jeleníti meg (ez az üzemmód nem minden kimen˝oállomány-formátumnál muködik). ˝ Az interaktív megjelenítést végzo˝ Gnuplot program ak övetkez˝o: 1 2 3 4 5 6 7

While/math/negyz3dint.gnuplot set zeroaxis set nokey set hidden3d set pm3d set palette gray splot "negyz3d.data" with lines pause -1 "Hit return to continue"

A háromdimenziós megjelenítésr˝ol b˝ovebben olvashatunk a Gnuplot dokumentációjában (info gnuplot) és az Interneten található segédanyagokban.


56

4.8. Fraktálok A Mandelbrot halmaz a Z komplex sík azon C elemeit tartalmazza, amelyekre a zn+1 = zn2 + C

(4.4)

(z0 = C) komplex függvény zn elemeire zn 6= ∞. Ha programot akarunk készíteni, amely a Mandelbrot halmazt ábrázolja, azaz kirajzolja a Mandelbrot féle almaemberkét, akkor a sík adott részének minden x, y elemére valamely n-ig el kell végeznünk a 4.4. formulában látható iterációt és meg kell vizsgálnunk, hogy az x, y pont milyen távolságba „menekült el” a ∞ irányába. A következ˝o példaprogram a Mandelbrot halmazt mutatja be az értékek kiszámításával. Figyeljük meg, hogy a program mennyire különbözo˝ nek tunik ˝ az eredeti formulától! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

While/math/mandelbrot.bas x := -2 while x <= 1 do y := -1 while y <= 1 do rem Az iteracio itt kezdodik p := 0 q := 0 psq := 0 qsq := 0 iteration := 0 while iteration < 30 and psq + qsq < 4 do psq := p*p qsq := q*q pnew := psq - qsq + x qnew := 2 * p * q + y p := pnew q := qnew iteration := iteration + 1 wend printnl x printnl y print iteration y := y + 0.02 wend newline x := x + 0.02 wend


57 A program által kiszámított értékek ábrázolására használhatjuk a következ˝o Gnuplot programot, amely egymás után két formában is megmutatja az adatokat: While/math/mandelbrot.gnuplot 1 set xlabel "x" 2 set ylabel "y" 3 set hidden3d 4 5 set pm3d 6 set palette gray 7 show pm3d 8 show palette 9 10 set title "The Mandelbrot Set" 11 set pm3d 12 splot "mandelbrot.data" with lines 13 pause -1 "Hit return to continue" 14 15 set pm3d map 16 replot 17 pause -1 "Hit return to continue" A program el˝obb térbeli képet rajzol a halmazról (4.5. ábra), majd kétdimenzoós formában, szürkeárnyalatokkal ábrázolja ugyanazokat az adatokat (4.6. ábra). A Gnuplot programot receptként felhasználhatjuk más adatsorok ábrázolására is.

4.9. Integrálás Ha egy adott függvény adott határok közt vett integrálját szeretnénk kiszámítani, két megoldási módszer is adódik. Az els˝o módszer a formális eszközöket használja. Ha ezt választjuk az integrálandó függvényt formálisan, muveleti ˝ jelekkel leíró kifejezést különféle átírási szabályok segítségével átalakítjuk. A következo˝ formula ilyen átírási szabályt mutat be: Z Z −1 n−1 n n−1 sin x dx = sinn−2 x dx (sin x) cos x + n n A módszer el˝onye, hogy abszolút pontos eredményt ad (ha ad!), hátránya azonban, hogy igen nehezen automatizálható. A matematika átírási szabályainak alkalmazása az emberi elme egyik legösszetettebb képessége, amelyben megfigyelhet˝ok ugyan automatizmusok, de számítógéppel csak csekély mértékben utánozható.


58

4.5. ábra. A Mandelbrot halmaz háromdimenziós képe

4.6. ábra. A Mandelbrot halmaz szürkeárnyalatos képe


59 A másik módszer numerikus eszközöket használ. Ennek a módszernek a lényege, hogy az integrálást jól automatizálható, számítógéppel könnyen elvégezhet˝o lépésekre bontjuk és számítógépes program segítségével a számítógéppel végeztetjük el. A numerikus módszer el˝onye, hogy ha az adott függvény integrálható, akkor mindig használható, jól automatizálható, hátránya viszont, hogy szinte soha nem ad pontos eredményt, ráadásul a hiba nehezen becsülheto˝ meg. A numerikus integrálás különféle módszerei megleheto˝ sen összetettek, a numerikus integrálást végz˝o programok muködése ˝ sokszor nehezen értheto˝ , mi azonban egy igen egyszeru ˝ módszert használunk, amelyet a következo˝ formula ír le: Z xN N X f (x) dx = f (xi )(xi+1 − xi ) (4.5) x1

i=1

A módszer lényege, hogy az integrálás elvégzéséhez az adott értelmezési tartományt azonosan kis méretu ˝ szakaszokra bontjuk, a szakaszok szélességét megszorozva a szakaszok alsó határán vett függvényértékkel közelítjük a szakasz alatt található területet és a területek összeadásával közelítjük a függvény integrálját. A 4.5. formulával kapcsolatban meg kell jegyeznünk, hogy az egyenlo˝ ség nem igaz, továbbá senki sem használ ilyen primitív formulát a függvények numerikus integrálására. Igaz viszont, hogy a formula alapján igen könnyen készíthetünk programot, ami esetenként megfelelhet a céljainknak.

4.10. Deriválás A program segítségével könnyen elvégezheto˝ numerikus integráláshoz hasonlóan a deriválás is elvégezhet˝o numerikus formában. Egyszeruen ˝ ki kell számolnunk a függvény értékét két közeli helyen és ki kell számolnunk a két érték közt a függvény meredekségét. Ezt mutatja be a következo˝ program, amelyet az f (x) = x3 függvény és deriváltja ábrázolására használhatunk: 1 2 3 4 5 6 7 8 9 10

While/math/05derivalt.bas rem Függvény és deriváltja. x := -10 dx := 0.05 while x < 10 do fx := x*x*x dfx := (fx - fxold) / dx if x <> -10 then


60 1000

f (x) f 0 (x)

800 600 400 200 0 -200 -400 -600 -800 -1000 -10

-8

-6

-4

-2

0

2

4

6

8

10

4.7. ábra. Függvény és deriváltja 11 12 13 14 15 16 17 18

printnl x printnl fx print dfx end fxold := fx x := x + dx wend

A grafikus ábrázolást végz˝o Gnuplot programban most a jelmagyarázatot létrehozó utasításokat is elhelyeztük. Az eredményként kapott grafikont a 4.7. ábrán láthatjuk. 1 2 3 4 5 6

While/math/05derivalt.bas set terminal latex set output "derival.tex" set zeroaxis plot "derival.data" using 1:2 title "$f(x)$" with lines,\ "derival.data" using 1:3 title "$f’(x)$" with lines


61

˝ állítása 4.11. Véletlenszámok elo D. Lehmer módszere véletlenszámok elo˝ állítására (linear congruential method): a1 := k for i := 2 to N do ai := (bai−1 + 1) mod m end for A bemutatott elgoritmus egyes elemei a következo˝ k: • A k tetsz˝oleges egész.

• Az N tetsz˝oleges egész szám, az el˝oállítandó véletlenszámok számát határozza meg. • A b és az m (majdnem) tetsz˝oleges egészek, megválasztásuk nagymértékben befolyásolja az el˝oállított véletlenszámokat. • Az ai véletlenszámok triviálisan 0 és m − 1 közé eso˝ egész számok, amelyek véletlenszeruen ˝ (de nem véletlenül) helyezkednek el az adott tartományban. Figyeljük meg, hogy az elgoritmus megadásakor a for kulcsszóval jeleztük a ciklikus végrehajtást. A for kulcsszó után megadtuk annak a változónak a nevét (i), amelyet ciklikusan növelni kell, majd a bejárandó értékek határát (2, illetve N ). Az i változó a ciklikus végrehajtás minden lépésében 1-el növekszik. A While nyelvében nincsen a for szerkezet közvetlen leírására alkalmas nyelvi kifejezés, de ez a szerkezet leírható a while ciklikus kifejezés segítségével. Ez alapján programot, amely a véletlenszámokat elo˝ állítja, könnyen elkészíthetjük. Az m és b megválasztása nagymértékben meghatározza az elo˝ állított véletlenszámokat. A következ˝o szabályok betartásával „jó” véletlenszámokat kapunk (D. Knuth): • Legyen m elegend˝oen nagy szám és legyen b körülbelül egy helyiértékkel kisebb. • A b számjegyei csak a . . . x21 szabályszeruséget ˝ tartalmazzák, ahol x páros szám. Készítsünk While programot, amely véletlenszámokat hoz létre a bemutatott módszer segítségével! 1 2

r := 17 i := 1

While/peldak/03-random.bas


62 3 4 5 6 7

while i <= 200 do i := i + 1 r := (r*421+1)%1000 print r wend A program által el˝oállított számsorozat a következ˝o:

158 327 916 525 754 203 472 161 870 199 748 117 906 715

519 668 637 26 435 464 713 782 271 780 909 258 427 16

500 229 178 947 136 345 174 223 92 381 690 619 768 737

501 410 939 688 257 246 255 884 733 402 491 600 329 278

922 611 320 649 198 567 356 165 594 243 712 601 510 39

163 232 721 230 359 708 877 466 75 304 753 22 711 420

624 673 542 831 140 69 218 187 576 985 14 263 332 821

705 334 183 852 941 50 779 728 497 686 895 724 773 642

806 615 44 693 162 51 960 489 238 807 796 805 434 283

Figyeljük meg, hogy a számok véletlenszeruen ˝ követik ugyan egymást, de az utolsó helyiértékek összehasonlításával szabályszeruséget ˝ figyelhetünk meg. Ez a szabályszeruség ˝ csak akkor zavarja meg az egyébként véletlenszeru ˝ sorozat használatát, ha a fels˝o helyiértékeket elhagyjuk. A legtöbb véletlenszámgenerátor leírása felhívja a figyelmet arra, hogy ha csak az alsó helyiértékeket használjuk, a számsorozatban szabályszeruségek ˝ lesznek: „If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in j=1+(int)(10.0*rand()/ (RAND_MAX+1.0)); and never by anything resembling j=1+(rand() % 10); (which uses lower-order bits).” Az idézet a rand man lapjáról származik, ahol idézik a következo˝ muvet: ˝ Numerical Recipes in C: The Art of Scientific Computing (William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling; New York: Cambridge University Press, 1992 (2nd ed., p. 277)).


63

4.12. Feladatok 1. Készítsen programot, amely egy adott számról eldönti, hogy az prímszám-e. A program kísérelje meg elosztani az N számot minden 2 ≤ i ≤ N2 egész számmal, számolja ki az osztás maradékát és ga az 0 fejezze be a vizsgálatot, mert az N nem prím! 2. Készítsen programot, amely kiírja az összes prímszámot 1 . . . 1000 tartományban! 3. Készítsen programot, amely kiírja mindazokat a pi , pj prímszámokból álló párokat, amelyekre pi , pj ≤ 1000, valamint j − i = 2 (ikerprímek)! 4. Készítsen természetes törtek egyszerusítését ˝ végz o˝ programot!

5. Készítsen programot, amely a π2 1 1 1 = 1+ 2 + 2 + 2 +··· 6 2 3 4 összefüggés alapján kiszámítja π 2 értékét! 6. Készítsen programot, amely a π3 1 1 1 = 1− 3 + 3 − 3 +··· 32 3 5 7 összefüggés alapján kiszámítja π 3 értékét! 7. Készítsen programot, amely ex = 1 + x +

x2 x3 + +··· 2! 3!

összefüggés alapján kiszámítja ex értékét adott x-re! 8. Készítsen programot, amely x ≥ 12 -re az ln x =

x−1 x

+

1 2

x−1 x

2

+

1 3

x−1 x

3

+···

összefüggés alapján kiszámítja ln x értékét adott x helyen! 9. Készítsen programot, amely a sin x = x −

x5 x7 x3 + − +··· 3! 5! 7!

összefüggés alapján kiszámítja sin x értékét adott x helyen!


64 10. Készítsen programot, amely a cos x = 1 −

x3 x5 x7 + − +··· 3! 5! 7!

függvény segítségével kiszámítja sin x értékét adott x-re! 11. Készítsen hatékony programot, amely kiszámítja sin x és cos x értékét adott x helyen! 12. A következ˝o meglep˝o formula érdekes módon közelíti π értékét: π=

∞ X

n=0

4 2 1 1 − − − 8n + 1 8n + 4 8n + 5 8n + 6

1 16

n

Készítsen programot, amely a formula segítségével adott pontossággal kiszámítja π értékét! 13. Készítsen programot, amely kiszámítja a legkisebb Hardy-Ramanujan számot! Az ilyen számok kétféleképpen is felírhatók két egész szám köbeként. 14. Készítsen programot, amely a kör sugarából kiszámítja a kör területét! 15. Készítsen programot, amely kiszámítja az a, b, c együtthatókkal megadott ax2 + bx + c = 0 másodfokú egyenlet valós gyökeit! A program legyen felkészítve arra, hogy a valós gyökök száma lehet 2, 1 illetve 0 is! 16. Készítsen programot, amely (x1 , y1 ), illetve (x2 , y2 ) koordinátákkal megadott pontok távolságát számítja ki! 17. Készítsen programot, amely az f (x) = mx + b függvénnyel megadott egyenes alatti területet számítja ki x1 , x2 határok között! A feladat megoldásához ne használjon ciklikus utasításvégrehajtást! 18. Készítsen programot, amely adott sugarú körre kiszámítja, hogy mekkora a kör területével közelít˝oleg megegyez˝o területu ˝ négyszög oldalhosszúsága! Írja le részletesen, hogy milyen módszert használt! R2 19. Készítsen programot, amely kiszámítja 1 x2 dx közelít˝o értékét! R2√ 20. Készítsen programot, amely kiszámítja 1 x dx közelít˝o értékét!

21. Készítsen programot, amely maghatározza, hogy az x1 , y1 , r1 , illetve x2 , y2 , r2 értékekkel megadott körök érintik-e egymást, azaz igaz-e, hogy egyetlen közös pontjuk van!


65 22. Készítsen programot, amely igen nagy számú egész számot hoz létre véletlenszeruen ˝ az 1 . . . 100 tartományban és megszámolja, hogy az egyes értékek hányszor jelentkeztek! A program kimenetének tanulmányozásával döntse el, hogy valóban véletlenszeruen ˝ jelentkeznek-e a számok, vagy megfigyelhet˝o valamilyen szabályszeruség! ˝ 23. Készítsen programot, amely véletlenszámokat állít elo˝ az 0 ≤ x ≤ 1 tartományban! A program legalább négy tizedesig véletlen számjegyeket adjon! 24. Készítsen programot, amely véletlenszeru ˝ prímszámokat állít elo˝ , amelyek számjegyeinek száma legalább 8. 25. Készítsen programot, amely a 4.3. formulában meghatározott függvényt 3, 5 és 10 tag kiszámításával ábrázolja! 26. Készítsen programot, amely az el˝oz˝o példában említett három függvény deriváltját ábrázolja! 27. Készítsen programot, amely a f (x) = rázolja!

sin(x) x

függvényt és deriváltját áb-

28. Vizsgálja át a következ˝o példaprogramot! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

While/math/negyz3dint.gnuplot rem Hullámfelület ábrázolása. x := -15 xx := 1; yy := 1; while x <= 15 do y := -15 while y <= 15 do d := sqrt((x-xx)*(x-xx) + (y-yy)*(y-yy)) + 1 fxy := cos(d) / d printnl x printnl y print fxy y := y + 0.5 wend newline x := x + 0.5 wend

A program segítségével a 4.8. ábrán látható hullámfelületet rajzolhatjuk ki. Alakítsa át a programot úgy, hogy több hullám interferenciáját mutassa be!


66

4.8. ábra. Hullámfelület ábrázolása 29. Készítsen a 4.9. ábrán látható grafikonhoz hasonló ábrát! 30. Ábrázolja a következ˝o függvényt! f (x, y) =

x2

xy + y 2 + 0, 1

(4.6)

31. Ábrázolja a következ˝o függvényt! f (x, y) =

sin(x2 y 2 ) x2 + y 2

(4.7)

32. Ábrázolja a következ˝o függvényt! f (x, y) = sin(x) cos(y)

(4.8)

33. A Mandelbrot halmaz kicsiny része felnagyítva végtelen bonyolultságot mutatnak. Nagyítsa fel a Mandelbrot féle almaemberke határvonalát és ábrázolja a felnagyított területet szürkeárnyalatos képen.


67

4.9. ábra. Az ln(x2 y2 ) függvény


68


5. fejezet

A Grammar A Grammar program a While programmal ellentétben nem numerikus feladatok elvégzésére, hanem szöveges feladatok megoldására készült, saját, a While nyelvét˝ol alapjaiban különböz˝o nyelvvel rendelkezik. A legtöbb programozási nyelvben változók, a változók értékét megváltozó értékadások, az érétkadások elvégzését vezérlo˝ elágazásos és ciklikus szerkezetek vannak. Az ilyen nyelveket általában imperatív vagy algoritmikus nyelveknek nevezzük. A Grammar azonban nem ilyen! Nyelvében nincsenek változók, nincsen értékadás és nincsenek elágazást vagy ciklikusságot vezértlo˝ szerkezetek, legalábbis olyan értelemben nincsenek, mint ahogyan azokat az imperatív nyelvek esetében megfigyeltük. Habár az ilyen nyelvekbo˝ l kevesebbet találunk a programozás világában, azért ezek a nyelvek is léteznek és széles körben használtak. A Grammar megkísérli bemutatni ezeknek a leíró jellegu ˝ nyelveknek a használatát, ha csak nagyon vázlatosan is, de bemutatva, hogy nem csak imperatív nyelvek léteznek. A következ˝o egyszeru ˝ példaprogram bemutatja a Grammar kifejezéseinek használatát: 1 2 3 4 5 6

start: ’ab\n’ ; ab:

Grammar/01-pelda.gr

’ab’ | ’’ ;

Ha az értelmez˝oprogram szabványos bemenetére küldjük ezt a programot, akkor az egy véletlenszeruen ˝ el˝oállított szöveggel válaszol: $ Grammar
69


70 aabb $

Az értelmez˝oprogramnak a -s kapcsoló után megadhatjuk, hogy hány darab véletlenszeru ˝ kifejezést szeretnénk elo˝ állítani a segítségével: $ Grammar -s 5
Ha a programnak a -t kapcsolót adjuk, nem csak az eredményül elo˝ állított kifejezéseket írja ki, hanem azt is, hogy milyen lépések során jutott el az eredményig: $ Grammar -t ------------------------------------------------ab\n ------------------------------------------------aabb\n ------------------------------------------------aabb\n aabb $

5.1. A Grammar nyelvének alapszerkezete A Grammar program kifejezések sorozatából áll. A legeggyszerubb ˝ kifejezések alakja a következ˝o: nemterminális: ’mondat’ ; Ahol a nemterminális az angol nyelv betuib˝ ˝ ol képzett szó, a mondat pedig tetsz˝oleges karakterlánc, amely szóközöket és ékezetes betuket ˝ is tartalmazhat és ahol a < és > jeleknek különleges jelentésük van. Az ilyen jellegu ˝ kifejezések egy egyszeru ˝ nyelvtani szabályt írnak le, azt jelzik, hogy az adott nemterminálissal, mint rövidítéssel fogjuk jelezni a szövegben a mondatot, azaz a tulajdonképpeni szöveges értéket. A kifejezés b˝ovített alakja alternatív módon több mondatot is tartalmaz, ahogyan a következ˝o példa is bemutatja:


71 nemterminális: ’mondat1’ | ’mondat2’ | ’mondat3’ ; A kifejezés azt jelzi, hogy az adott nemterminálissal – mintegy gyujt ˝ o˝ fogalomként – több mondatot is jelölünk, címkézünk. A következo˝ programrészlet például a köznapi értelemben értelmesnek tunik: ˝ gyumolcs: ’szilva’ | ’körte’ ; Figyeljük meg, hogy a nemterminális nevét úgy kellett megválasztanunk, hogy az ne tartalmazzon ékezetes karaktert, hiszen amint említettük a nemterminális kizárólag az angol nyelv betuit ˝ tartalmazhatja. Ez a megkötés kissé nehezíti a program elolvasását, de nem okoz komoly problémát, hiszen a nemterminálisok nem jelennek meg a program kimenetén. A nemterminálisokat a bemutatott szabályok jobb oldalán úgy használhatjuk fel, hogy nevüket <> jelek közé írjuk, így a szabályok felsorolásával összetett szerkezeteket, nyelvtanokat írhatunk le. Ezt mutatja be a következ˝o példaprogram: Grammar/02-pelda.gr 1 start: ’Az asztalon van egy .\n’ 2 | ’A pálinka elfogyott.\n’ 3 ; 4 5 gyumolcs: ’szilva’ 6 | ’körte’ 7 ; A program futtatásának eredménye a következo˝ : $ Grammar/02-pelda.gr A szilvapálinka elfogyott. A körtepálinka elfogyott. A szilvapálinka elfogyott. Az asztalon van egy körte. $

Az, hogy az egyes nemterminálisokat, a rájuk vonatkozó szabályokat milyen sorrendben írjuk le, mindegy. Az értelmezo˝ program el˝oször beolvassa az összes szabályt és csak utána végez muveleteket ˝ a nyelvtanon. Egy nemterminális azonban kitüntetett fontosságú. Az egyik nemterminálisnak – amelyet a hagyomány szerint a program elején helyezünk el – a neve start. A program számára minden nyelvtani kifejezésnek megalkothatónak és visszavezethet˝onek kell lennie a start nemterminálisra.


72

5.2. Egyszeru ˝ faszerkezet Könnyen készíthetünk olyan Grammar programot, amely a mondatokban található nemterminálisok segítségével egyszeru ˝ faszerkezetet valósít meg és meglep˝oen változatos mondatszerkezeteket hozhatunk létre a program segítségével. A következ˝o program ilyen szerkezetet mutat be. Grammar/idojaras.gr 1 start: ’ <mijen> .\n’ 2 | ’A <szemely> szerint <mijen> .\n’ 3 ; 4 5 mijen: ’gyönyör˝ u’ 6 | ’szép’ 7 | ’igazán kellemes’ 8 ; 9 10 ido: ’id˝ onk van’ 11 | ’az id˝ ojárás ma’ 12 | ’napunk van ma’ 13 ; 14 15 kezdet: ’Azt hiszem nyugodtan mondhatjuk, hogy’ 16 | ’A <szemely> , hogy’ 17 | ’Igazán’ 18 ; 19 20 kijelent: ’mondta’ 21 | ’említette’ 22 | ’szerint’ 23 | ’azzal viccelt’ 24 | ’állítja’ 25 ; 26 27 szemely: ’’ 28 | ’ ’ 29 | ’rádió’ 30 ; 31 32 nev: ’Jóska’ 33 | ’Béla’ 34 | ’barátom’ 35 ; 36 37 kije: ’unokatestvére’


73 38 39 40 41

| ’ismer˝ ose’ | ’lánya’ | ’sógorának unokatestvére’ ; A program futtatása során a kvöetkez˝o mondatokat hozta létre:

A barátom sógorának unokatestvére szerint igazán kellemes ido˝ nk van. Igazán gyönyöru ˝ az id˝ojárás ma. A Béla sógorának unokatestvére állítja, hogy szép napunk van ma. A Jóska mondta, hogy igazán kellemes id˝onk van. Azt hiszem nyugodtan mondhatjuk, hogy gyönyöru ˝ napunk van ma. A rádió azzal viccelt, hogy gyönyöru ˝ az id˝ojárás ma. A barátom ismer˝ose szerint igazán kellemes az id˝ojárás ma. A barátom ismer˝ose szerint szép napunk van ma. A barátom szerint szép id˝onk van. A rádió említette, hogy gyönyöru ˝ id˝onk van. Azt hiszem nyugodtan mondhatjuk, hogy gyönyöru ˝ napunk van ma. A rádió szerint gyönyöru ˝ az id˝ojárás ma. Igazán szép napunk van ma. A Béla szerint igazán kellemes napunk van ma. A barátom szerint szép az id˝ojárás ma. A Béla szerint igazán kellemes napunk van ma. Azt hiszem nyugodtan mondhatjuk, hogy igazán kellemes az ido˝ járás ma. A rádió szerint szép az id˝ojárás ma. A barátom ismer˝ose szerint igazán kellemes napunk van ma. A Jóska sógorának unokatestvére szerint igazán kellemes ido˝ nk van. Azonnal láthatjuk, hogy milyen izgalmas világ tárul ki elo˝ ttünk, ha a magyar nyelv adott részhalmazának nyelvtanát leíró programot készítünk. Gondoljunk csak a horoszkópot, faviccet vagy éppen sértegetést készít o˝ programra, amely utóbbit például a megfelel˝o módon összekapcsolva az elektronikus levelést végz˝o programmal eszközt kaphatunk több millió ember névsorban történ˝o megsértésének automatizálására. Mellékesen felhasználhatjuk a Grammar értelmezo˝ programot arra is, hogy kissé mélyebben is megértsük a programozási nyelvek felépítését és használatát. A következ˝o program például értékadásokat hoz létre: 1 2 3 4 5

start:

Grammar/idojaras.gr ’ = <ertek> <muvelet> <ertek>\n’ | ’ = <ertek>\n’ ;

muvelet: ’+’


74 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

| ’-’ | ’ *’ | ’/’ ; ertek:

’’ | ’’ ;

valtozo: ’a’ | ’b’ ; konst:

’42’ | ’13’ ;

A program futtatásának eredménye: a a b b a a b b

= = = = = = = =

13 b b - 13 42 a a b / 42 b

A létrehozott kifejezések némelyikének ugyan nem sok haszna van, de matematikai értelemben mindegyik helyesnek, jól formáltnak tunik. ˝ Ez természetesen nem bizonyítja, de sugallja, hogy a program a matematika nyelvének egy részét leíró nyelvtant ad meg.

5.3. Rekurzív szerkezetek Rekurzióról általában akkor beszélünk, ha egy program önmagát indítja el vagy egy fogalmat önmagával definiálunk. A rekurzió egyrészt veszélyes, hiszen könnyen a végtelen körkörösség vagy a paradoxon hibájába eshetünk, másrészr˝ol viszont roppant nagy a kifejez˝oereje ezért nem mondhatunk le róla. A Grammar lehet˝ové teszi rekurzív szabályok létrehozását. Azokat a szabályokat nevezzük rekurzívnak, amelynek a bal oldalán található nemterminálisa a jobb oldalon is szerepel. A következo˝ szabály tisztán rekurzív, mert a szabály mindkét jobb oldalán szerepel a bal oldal nemterminálisa.


75

1 2 3

kif:

Grammar/03-pelda.gr ’ + ’ | ’ - ’ ;

Az ilyen szabályok gyakorlatilag használhatatlanok, hiszen nincs mód a körkörösségb˝ol való kiszabadulásra, a szabály feldolgozása mindenképpen végtelen programvégrehajtást eredményez. Lényeges, hogy a rekurzív szabályok legalább egy jobb oldala ne tartalmazza a bal oldali nemterminálist. A rekurzió egy használható formáját mutatja be a következo˝ példa: 1 2 3 4

kif:

Grammar/03-pelda.gr ’ + ’ | ’ - ’ | ’<szam>’ ;

Azzal, hogy a szabályt egy újabb jobb oldallal egészítettük ki, amelyben nem szerepel a bal oldali nemterminális, leheto˝ vé tettük, hogy a szabály feldolgozása befejez˝odjön. A rekurzív szabályok kapcsán meg kell jegyeznünk, hogy azért nagyon fontosak, mert lehet˝ové teszik hosszú és összetett nyelvi kifejezések kezelését, amelyek a beszélt nyelvben is elo˝ fordulnak, de a gépi nyelvekben és a matematikában elengedhetetlenül fontosak.

5.4. A balrekurzió A nyelvtanokat kezel˝o módszerek és a nyelvtanok alapján muköd˝ ˝ o programok általában arra bátorítanak, hogy használjunk úgynevezett balrekurzív szabályokat. A balrekurzív szabályok olyan szabályok, amelyekben a rekurzíiót el˝oidéz˝o, a szabály bal oldalán is található nemterminális a szabály jobb oldalán található mondat elején található meg. A következ˝o példa balrekurziót használ: 1 2 3 4 5 6 7 8 9

start: ;

Grammar/balrekurzio.gr ’PRINT <lista>\n’

lista: ’’ | ’<lista>, ’ ; tetel: ’alpha’ | ’beta’


76 10 11 12

| ’gamma’ | ’delta’ ;

A szabályok közül a második rekurzív, mert a második jobb oldalon megtalálható a bal oldalon is olvasható nemterminális. Ez a szabály balrekurzív is, mert a jobb oldal elején olvashatjuk a rekurziót okozó nemterminálist. A példaprogram listaszeru ˝ szerkezeteket hoz létre, ahogyan a következ o˝ futtatás bemutatja: $ Grammar -s 3
Amint látható az ilyen egyszeru ˝ balrekurzív szabályokat könnyen használhatjuk listaszeru ˝ szerkezetek kezelésére, amelyeket a legtöbb programozási nyelv használ. Listákat el˝oállító balrekurzív szabályok esetében elo˝ fordulhat, hogy az üres, elemet nem tartalmazó listát is kezelni szeretnénk a nyelvtannal. Ilyenkor a szabályban üres jobb oldalt is használnunk kell, ahogyan a következ˝o példa is bemutatja: 1 2 3 4 5 6

start: | ; szam: | ;

Grammar/ureslista.gr ’’ ’<start><szam>’ ’1’ ’0’

Az értelmez˝o és fordítóprogramok általában 0 vagy több utasításból álló programokat kezelnek, ezért a legtöbb nyelvtanban találunk ilyen szabályokat is.

5.5. Határolójelek A matematika és a programozási nyelvek leheto˝ vé teszik, hogy az egyes kifejezéseket határolójelek közt szarepeltessük. Ilyen esetekben érdemes ügyelnünk arra, hogy az együvé tartozó jeleket egyszerre, egy jobb oldalon vezessük be, hogy semmiképpen ne fordulhasson elo˝ olyan eset, amikor az egyik jel szerepel, a másik azonban nem. A következo˝ példa ezt módszert mutatja be:


77

1 2 3 4 5 6

start: | ; szam: | ;

Grammar/határolojelek.gr ’<szam>\n’ ’(<szam>)\n’ ’1’ ’0’

Általában elmondhatjuk, hogy az összefügg˝o nyelvi elemeket (például if, then, else vagy while, wend) egyazon jobb oldalon érdemes bevezetni, mert így könnyebb elkerülni a hibákat és a létrehozott nyelvtan természetesebb formában írja le a nyelvet.

5.6. Muveleti ˝ jelek A muveleti ˝ jelek kezelésekor arra kell ügyelnünk, hogy a legtöbb nyelvben a muveleti ˝ jelek nem csak egyszeru ˝ elemeket (állandók, változók) hanem összetett kifejezéseket is összekapcsolhatnak. A következo˝ programrészlet bemutatja a muveleti ˝ jelek kezelését: 1 2 3 4 5 6 7 8 9

numkif: | | | | | | | ;

Grammar/whilereszlet.gr ’<szam>’ ’’ ’ + ’ ’ - ’ ’ * ’ ’ / ’ ’ % ’ ’()’

5.7. Programok létrehozása Ha elegend˝oen bonyolult gépi nyelv mondatainak el˝oállítására készítünk nyelvtant, akkor valószínuleg ˝ nagyon sok rekurzív szabályt kell beépítenünk. Ennek az lesz az eredménye, hogy a véletlenszeruen ˝ elo˝ állított kifejezések nagyon bonyolultak lesznek. Ennek elkerülése érdekében a Grammar nyelve leheto˝ vé teszi, hogy a szabályok jobb oldala el˝ott egy számmal jelezzük milyen valószínuséggel ˝ szerepeljen az adott mondat a létrehozott kifejezésekben. A Grammar e jobb oldalak el˝ott álló számokkal súlyozzal a véletlenszeru ˝ választást, azaz a nagyobb számmal jelölt mondatot nagyobb valószínuséggel ˝ fogja választani.


78 Így elkerülhetjük, hogy a ritkán használt mondatok ugyanolyan mennyiségben szerepeljenek a létrehozott kifejezésekben, mint a sur ˝ un ˝ használtak. A következ˝o példaprogram ezt a lehet˝oséget használja While programok létrehozására. Grammar/while.gr 1 start: ’’ 2 | ’<start>’ 3 ; 4 5 ut: 5 ’ := \n’ 6 | 1 ’ := \n’ 7 | 1 ’print \n’ 8 | 1 ’while do\nwend\n’ 9 | 1 ’repeat\nuntil \n’ 10 | 1 ’if then\nend\n’ 11 | 1 ’if then\nelse\nend\n’ 12 ; 13 14 numkif: 10 ’<szam>’ 15 | 10 ’’ 16 | 1 ’ + ’ 17 | 1 ’ - ’ 18 | 1 ’ * ’ 19 | 1 ’ / ’ 20 | 1 ’ % ’ 21 | 1 ’()’ 22 ; 23 24 logkif: 10 ’==<szam>’ 25 | 1 ’ ’ 26 ; 27 28 logop: ’and’ 29 | ’or’ 30 ; 31 32 szam: ’1’ 33 | ’2’ 34 | ’3’ 35 | ’4’ 36 | ’5’ 37 | ’<szam><szam>’ 38 ; 39


79 40 41 42 43 44 45 46

valtozo: | | | | | ;

’a’ ’b’ ’c’ ’i’ ’j’ ’k’

A program futtatásának eredményét mutatja be a következo˝ néhány sor. $ Grammar
Amint láthatjuk az eredmény értelmetlen, de nyelvtani értelemben helyes program, amelyet a While képes futtatni.

5.8. Feladatok 1. Mutasson példákat olyan nyelvi szerkezetekre a magyar nyelvben, tetsz˝oleges programozási nyelvben és a matematikában, amelyeket legkönnyebben rekurzív szabályok segítségével kezelhetünk! 2. Készítsen magyar nyelvu ˝ programokat létrehozó mondatokat rekurzív szabályok felhasználásával! 3. Készítsen a balrekurzív szabályok mintájára jobbrekurzív szabályt, amely a rekurziót okozó nemterminálist a jobb oldal végén tartalmazza! 4. Készítsen nyelvtant, amely páros számokat hoz létre! 5. Készítsen nyelvtant, amely olyan While programokat hoz létre, amelyek páros számokat hoz létre!


80 6. Készítsen nyelvtant, amely olyan While programokat hoz létre, amelyek páros számokat írnak ki növekv˝o sorrendben! 7. Készítsen nyelvtant, amely olyan While programokat hoz létre, amelyek véletlenszámokat hoz létre! 8. Készítsen nyelvtant, amely olyan While programokat hoz létre, amelyek tartalmaznak while szerkezeteket, de soha nem futnak végtelen ideig. 9. Készítsen Grammar programot, amely olyan While programokat hoz létre, amelyek tömböket is tartalmaznak! 10. Készítsen Grammar nyelvtant, amely olyan while programokat hoz létre, amelyek tömböket töltenek fel véletlenszeru ˝ értékekkel! 11. Készítsen Grammar nyelvtant, amely olyan While programokat hoz létre, amelyekben nem triviális nyelvtani hibák vannak!


Irodalomjegyzék [1] Pere László. Linux: felhasználói ismeretek I. Kiskapu, Budapest, 2002. [2] Pere László. GNU/Linux rendszerek üzemeltetése I. Kiskapu, Budapest, 2005. [3] Jerry Peek, Mike Loukides, Tim O’Reilly, et al. UNIX Power Tools. O’Reilly & Associates, Inc., 103a Morris Street, Sebastopol, CA 95472, USA, Tel: +1 707 829 0515, and 90 Sherman Street, Cambridge, MA 02140, USA, Tel: +1 617 354 5800, March 1993. [4] Nyékyné Gaizler Judit (szerk.). Programozási nyelvek. Kiskapu, Budapest, 2003.

81

7 10:23 page 1 #1 2.1 változat

Recommend Documents