2016. augusztus 25., csütörtök

Algoritmizálás a gyakorlatban

Algoritmuson vagy inkább eljáráson olyan megengedett lépésekből álló módszert, utasítást, részletes útmutatást, receptet értünk, amely valamely felmerült probléma megoldására alkalmas. Például eljárást, algoritmust, receptet lehet adni egy „kombo” asztal (vagy egyéb bútor) összeszerelésére, valamilyen élelmiszer, mondjuk sajt (vagy bármilyen tejipari termék) elkészítésének módjára, a Deák térről a Lánchídhoz vezető út megtalálására, vagy éppen két egész szám legnagyobb közös osztójának kiszámolására. A számítógépes programok általában tartalmaznak algoritmusokat, ezekkel utasítják a gépet az adott feladat végrehajtására.

A konkrét algoritmus megadásához tudni kell, hogy mik a megengedett lépések. Enélkül az az egy lépés is algoritmus lehetne, hogy süssük meg a kenyeret, hogyan készítsünk teát. Csak a megengedett lépésekkel lehet az algoritmuson bonyolultsági elemzést végezni.

Algoritmus fogalma

    Az életben meg kell oldani bizonyos feladatokat lehetőség szerint gyorsan és jól. A legnehezebb dolog nem a számítógépes nyelv használata, a megoldás lekódolása, hanem a megoldási módszer kitalálása. Ez viszont nyelv független!

Javaslat: Írjuk le azokat az instrukciókat (mintha értelmes emberi lénnyel próbálnánk végrehajtatni), amelyek elvezetnek a probléma megoldásához.
Az instrukciók tartalmazhatnak utasításokat, feltételeket, ismétléseket.

Algoritmusnak nevezzük azon instrukciók halmazát, mely egy feladat megoldásához vezetnek. Az algoritmus egy út a felvetődött probléma megoldásához.
Kidolgozhatunk több különböző módszert is !

Típusok


Algoritmus elemei:

    Szekvencia (tevékenység): Egymás után végrehajtandó tevékenységek sorozata
    Szelekció (elágazás): Választás megadott tevékenységek közül
    Iteráció (ciklus): Megadott tevékenységek ismételt végrehajtása. A ciklusmagot nullaszor, egyszer vagy sokszor hajtjuk végre a ciklus feltételétől függően.
    Feltétel nélküli ugrás: Vezérlés átadása a program egy megadott pontjára.

Példa algoritmusra:

Nézzük meg például annak az algoritmusát, hogyan juthatunk el metróval a Déli pályaudvartól a Városligetbe!


 START
   Metrójegy vétele
   Beszállás a "kék metróba"
   Utazás a következő megállóig
   Deák tér a megálló?
   Ha igen, akkor kiszállás
   Beszállás a "sárga metróba"
   Utazás a következő megállóig
   Városliget a megálló?
   Ha igen, akkor kiszállás
STOP

Készítsd el az algoritmus folyamatábráját!

További feladatok:
1. Feladat:

Az a és b oldal ismeretében a téglalap kerületének kiszámítása. Bontsuk elemi lépésekre a feladatot!

Az algoritmus mondatszerű leírása:
         START
                   a  oldal beolvasása
                   b  oldal beolvasása
                   a és b pozitív ?
                            ha nem, az oldalak ismételt beolvasása
                   téglalap kerületének kiszámítása
                   az eredmény kiíratása
         STOP

2. Feladat:

Készítsd el az ébredés folyamatának algoritmusát!
Feladatvizsgálat:
A feladatot nagyvonalúan ábrázoljuk. Alapvetően kétféle viselkedésünk lehet reggel, és ez attól függ, hogy jókor ébredtünk-e fel.

3. Feladat:

Készítsd el a teafőzés algoritmusát!
Feladatvizsgálat:
A teafőzés folyamatábrája tartalmaz elágazást is, hátul tesztelő ciklust is, emellett egyszerű műveletekből áll.

4. Feladat:

Számítsuk ki és írassuk ki 5 előre megadott szám átlagát!
Feladatvizsgálat:
1. Bemenő adatok:
    a, b, c, d, e: kis, egész számok, byte típusúak.
2. Kimenő adat:
    f: először a számok összegét tároljuk ebben a változóban, majd az átlagot. Ez utóbbi tört értékű is lehet, ezért ez a változó real típusú kell, hogy legyen.

5. Feladat:
Határozd meg két pozitív egész szám legnagyobb közös osztóját! (Euklideszi algoritmus)


6. Feladat:

Készítsd el a paprikáskrumpli főzésének algoritmusát!
Feladatvizsgálat:
A feladatot ügyesen kell egyszerű, mégis nem teljesen elemi lépésekre bontani. Egyértelmű bontása nincsen, csak annyi a lényeg, hogy a folyamatábrában használatos jeleket a funkciójuknak megfelelően gyakoroljuk.

7. Feladat:

Elemezed Petőfi Sándor Arany Lacinak című versét!

8. Feladat:

Folyamatábrával tervezd meg, hogy hogyan fogsz fölkészülni a következő osztálykirándulásra!

forrás: Burján Károly

      Betyár-teendők algoritmusa (Sobri Jóska és betyárjai)
         Állj ki az útra !
         Ciklus
            Figyelj !
         Ciklus, míg Jön kereskedő
         Rabold ki !
      Algoritmus vége

      Teafőzés algoritmusa (filteres teából)
         Tedd fel a vizet forrni !
         Ciklus

         Ciklus, míg Forr a teavíz
         Ízesítsd !
      Algoritmus vége

      Bevásárlás I. algoritmusa (önkiszolgáló boltban)
         Végy egy kosarat/kocsit !
         Ciklus
            Keresd meg a "következő" árut !
            Ha Van ilyen, akkor Tedd a kosárba/kocsiba !
         Ciklus, míg Nincs "következő" áru, amit vásárolni akartál
         Fizesd ki a választott termékeket !
      Algoritmus vége

      Bevásárlás II. algoritmusa (Peny Market)
         Ha van 10 vagy 20 Ft-os érméd, akkor
            Végy egy kocsit !
            Ciklus
               Keresd meg a "következő" árut !
               Ha Van ilyen, akkor Tedd a kocsiba !
            Ciklus, míg Nincs "következő" áru, amit vásárolni akartál
            Fizesd ki a választott termékeket !
         egyébként
            Menj haza !
         Ha vége
      Algoritmus vége

Szakirodalom:

https://infopy.eet.bme.hu/ea02/#1
http://programarcadegames.com/index.php?lang=hu
http://mek.oszk.hu/08400/08435/08435.pdf




Nincsenek megjegyzések:

Megjegyzés küldése