Oszd meg!

Add a Twitter-hez Add a Facebook-hoz Add a Startlaphoz Add az iWiW-hez Add a Google Reader-hez

Közösség

Belépés

E-mail cím:
Jelszó:

Programozási tételek

Programozási tételek

 

Idővel, ha egyre több algoritmust készítenénk, tapasztalnánk azt, hogy bizonyos részfeladatok tipizálhatók, lényegében ugyanazon algoritmusok szükségesek a megoldásukhoz. Ezután néhány ún. típusalgoritmussal fogunk megismerkedni, melyeket "programozási tételeknek" is nevezhetünk. (akár a matematikában)

 

Ezen tételek ismeretében már a legtöbb feladat megoldása során nincs más dolgunk mint meghatározni, hogy milyen típusú feladatról van szó és alkalmazni a megfelelő algoritmust, a megfelelő programozási tételt. Persze el kell végezni a megfeleltetéseket. Ha nem használnánk programozási tételeket programjaink áttekinthetetlenekké válnának, oly módon oldanánk meg feladatot, mintha mindig fel kellene fedeznünk a megoldóképetet.

 

Az alábbiak során az egyes tételeknél mindig megnézünk egy általános feladatot, annak megoldását, majd egy a tételhez kapcsolódó egy konkrét feladatot és annak megoldását.

 

Sorozathoz egy érték hozzárendelése

 

1.     Az összegzés és átlagszámítás tétele

 

Feladat: Adott egy A nevű N elemű sorozat, amely numerikus elemeket tartalmaz. Készítsünk olyan programot, amely megadja a sorozat elemeinek összegét.

 

Gondolatmenet: Vegyük a sorozat elemeit rendre egyesével és adjuk hozzá az előzőek összegéhez. Az összegzés elvégzéséhez egy SUM nevű változót használjunk.  Az elemek feldolgozásához előírt lépésszámú növekményes ciklust szervezünk.

 

Algoritmus Összegez

                          Sum:=0

                          Ciklus I:= 1 -Től N -Ig

                             Sum:= Sum + A(I)

                          Ciklus Vége

                          Ki(Sum)

                        Algoritmus Vége.

 

Fontos lépés a Sum változó értékének nullázása, Sum:= 0 utasítás elvégzése. A Sum ugynevezett gyűjtő változó, értékét nullázni kell. A gyűjtés lépése Sum:=Sum+ A(i), olyan mint amikos egy kosárba mindig ujabb dolgokat teszünk.

 

Módosítsuk a feladatot, hogy az A(N) tömb elemeinek átlagát számoljuk ki.

 

Megfeleltetés:

A(N): sorozat;  Sum: összeg Átl: átlag

Algoritmus: ÁtlagSzámítás

                          Sum:=0

                          Ciklus I:= 1 -Től N -Ig

                                   Sum:= Sum + A(I)

                           Ciklus Vége

                          Átl:= Sum / N

                          Ki(Átl)

                        Algoritmus Vége.

 

Vegyük észre, hogy az átlag kiszámítása a teljes összegzés elvégzése után történt, tehát a cikluson kívül.

Konkrét feladat: N napon keresztül naponta egyszer megmértük a hőmérsékletet. Adjuk meg az N napos időszak átlaghőmérsékletet!

 

Megfeleltetés:

Sorozat: HŐ(N), megfelel A(N) -nek

N napi átlaghőmérséklet: ÁtlHő, megfelel Átl-nak

N nap hőmérsékletének összege: Összhő, megfelel Sum-nak.

(Ezután a feladat egyszerűen a szereplő azonosítók cseréjére vezethető vissza, vagyis egy szövegszerkesztői feladatot kaptunk. Persze nem árt érteni, mit csinálunk.)

 

Algoritmus: Átlagszámítás

                          Összhő:= 0;

                          Ciklus I:= 1 -Től N -Ig

                               Összhő:= Összhő + A(I)

                           Ciklus Vége

                          ÁtlHő:= Összhő / N

                          Ki(ÁtlHő)

                        Algoritmus Vége.

 

 

2.     Megszámlálás tétele:

 

Feladat: Ismert egy N elemű sorozat és a sorozat elemein értelmezett T tulajdonság. A T tulajdonsággal rendelkező elemek számára vagyok kíváncsi.

Gondolatmenet:

Vizsgáljuk meg a szorzat minden elemét! ( Ciklus szervezés 1-től N-ig.)  Ha  a sorozat valamely eleme rendelkezik T tulajdonsággal, akkor eggyel több ilyen elemünk van, vagyis megnöveljük a Db változó értékét eggyel: Db:=Db+1.

 

Algoritmus: Megszámlál

                          Db:=0

                          Ciklus I:= 1-Től N-Ig

                             Ha A(I) = T Tulajdonságú Akkor

Db:= Db+1

                              Elág vége

                          Ciklus Vége

                        Ki: Db

                        Algoritmus Vége.

 

Konkrét feladatok:

Számoljuk meg egy Számok(N) tömbnek hány pozitív eleme van!

Adjuk meg az osztály névsorából a "Kovács" vezetéknevű emberkék számát. (Írják fel a megfeleltetést, gondolatmenetet, algoritmust.)

 

 

3.     A maximum, (minimum) kiválasztás tétele

 

Feladat: Ebben a feladatban egy sorozat legnagyobb, (legkisebb) elemét kell megtalálni, pontosabban annak sorszámát meghatározni. A sorozat lehet szám vagy szöveges elemű.

 

Gondolatmenet a maximum kiválasztására:

A legelső elemet válasszuk maximumnak és annak sorszámát, vagyis 1-et a maximum elem sorszámának. Az elemek feldolgozását a 2. elemtől végezzük, ettől kezdve minden elemet hasonlítsunk össze a maximummal. Ha a maximumtól  a most vizsgált elem nagyobb akkor új maximumot és sorszámot választunk: a maximum értéke az éppen vizsgált elem, sorszáma a vizsgált elem sorszáma lesz.

A feladat megoldását úgy kapjuk, hogy visszavezetjük elemenkénti feldolgozásra. Ha ismerjük K elem közül a legnagyobbat és veszünk ezekhez egy új elemet, akkor a maximum, vagy az eddigi, vagy az új elem lesz.

 

Megfeleltetés:

A(N) - sorozat

MAXINDEX - a sorozat aktuálisan (az eddig vizsgáltak közüli) legnagyobb elemének sorszáma, végén a maximum sorszáma

MAXÉRTÉK – a sorozat aktuálisan legnagyobb értékű elemének értéke, végén a maximális érték

 

Algoritmus: MaxÉrték

                          MaxIndex:= 1

  MaxÉrték:= A(MaxIndex)

                          Ciklus I:= 2-Től N-Ig

                             Ha  MaxÉrték < A(I) akkor

MaxIndex:= I

MaxÉrték:=A(MaxIndex)

                              Elág vége

                          Ciklus Vége

                          Ki: MaxIndex

                          Ki: MaxÉrték

                        Allgoritmus Vége.

 

Egy Másik gondolatmenet:

Most egyszerre nem elég a sorozat egyetlen elemét vizsgálni, hiszen a legnagyobb az, amelyik mindegyiknél nagyobb, azaz mindegyikkel össze kell hasonlítani. A feladat megoldását úgy kapjuk, hogy visszavezetjük elemenkénti feldolgozásra. Ha ismerjük K elem közül a legnagyobbat és veszünk ezekhez egy új elemet, akkor a maximum, vagy az eddigi, vagy az új elem lesz.

 

Megfeleltetés:

A(N) - sorozat

INDEX - segédváltozó, mely az eddig megvizsgáltak közül mutatja a legnagyobb sorszámát

MAXINDEX - a sorozat legnagyobb elemének sorszáma

 

Algoritmus:

                        Program

                          Index:= 1

                          Ciklus I:= 2-Től N-Ig

                             Ha A(Index) < A(I) Akkor Index:= I

                          Ciklus Vége

                          Maxindex:= Index

                        Program Vége.

 

Az index, illetve a Maxindex egyértelműen meghatározza a maximum keresett értékét!

 

Gondolom a legkisebb elem kiválasztása már csak kézügyesség kérdése, ekkor a reláció jelet kell csak megfordítani, de emellett célszerű a változókat is átnevezni a minimum nevekre.

 

Más jelölésekkel és segédváltozókkal egy újabb megoldást kapunk.

                        Program

                          Érték:= A(1),

                          Index:=1       

                          Ciklus  I:= 2-Től  N-Ig

                              Ha Érték < A(I) Akkor

            Érték:= A(I) ; Index:= I

      Elágazás vége

                          Ciklus Vége

                          Maxindex:= Index

                          Maxérték:= Érték

                        Program Vége.

 

 

4.     A kiválogatás tétele:

 

Feladat: Egy N elemű sorozat összes T tulajdonsággal rendelkező elemét kell meghatározni, sorszámukat összegyűjteni egy másik sorozatban.

Gondolatmenet:

Összehasonlítom a sorozat összes elemét a T tulajdonsággal és közben számolom, sorszámozom a T tulajdonságúakat, melyek sorszámait egy B(K) vektorban fogom gyűjteni.

 

Algoritmus: kiválogat

                          J:= 0

                          Ciklus I:= 1-Től N-Ig

                             Ha A(I) T Tulajdonságú Akkor

J:= J+1; B(J):= I

                             Elág vége   

                          Ciklus Vége

                        Algoritmus Vége.

 

 

 

Feladat: Készítsen algoritmust, amely N ember magasságának ismeretében megadja az X magasságtól alacsonyabbakat! (Itt csak a magasságok értékét  tároltuk eddig is és csak ezt érjük el most is, de bármely más tulajdonság párhuzamosan kezelhető.)

 

Megfeleltetés:

sorozat - A(N)

tulajdonság - A(I) < X

A B tömb elemeinek számát a B_Esz változóban tároljuk.

Algoritmus: Alacsonyak

                        J:= 0

                        Ciklus  I:= 1-Től N-Ig

                                   Ha A(I) < X Akkor

J:= J+1; B(J):= I

                                   Elág vége

                        Ciklus Vége

                        B_Esz:=J;

Alg. Vége.

 

A tárolt értékek kiírása:

Ciklus  j:=1 –től B_Esz –ig

            Ki: A(B(j))

Ciklus vége

A ciklus belsejében az A tömb B(j) által mutatott elemét íratjuk ki.