Az informatikában alapvető az algoritmus fogalma.
Az algoritmus több azonos jellegű, egymástól csak a kiinduló adatokban különböző feladat megoldására szolgáló eljárás, amelynek során előre meghatározott, véges számú lépést adott sorrendben végrehajtva jutunk el a feladat megoldásához.
A számunkra fontos algoritmusok azok, amelyek egy számítógépes program segítségével leírhatók ("kódolhatók"). Ekkor az algoritmus egyes lépéseinek meghatározott műveleteket végrehajtó utasításokat feleltetünk meg.
A programok segítségével leírható algoritmusok a főbb jellemzői a következők:
- végesség: a program egy idő után befejeződik
- egyértelműség: minden utasítás végrehajtása után egyértelműen meg tudjuk mondani, mi lesz a következő utasítás
- teljesség: a program a bemeneti (input) adatok minden lehetséges értéke mellett előállítja a megfelelő kimenetet (output)
Egy algoritmus rendszerint nem egy egyedi probléma megoldására szolgál, hanem több, egymáshoz valamilyen szempontból hasonló probléma megoldására (amelyek csak a bemeneti adatokban különböznek egymástól).
Az algoritmusok létrehozásakor mindig törekedjünk arra, hogy az algoritmus minél általánosabb legyen, azaz a megoldandó probléma által megengedett bemeneti (input) adatok minél szélesebb körére szolgáltasson megoldást.
Az ebben a fejezetben ismertetett algoritmusok formális leírására számos programot is meg fogunk adni. Az alábbiakban ezeknek a legfontosabb összetevőit tekintjük át. A példákat JavaScript programozási nyelven adjuk meg.
Kiinduló példa: egy bináris szám átalakítása decimális számmá.⇒
A legegyszerűbb programok a következő utasításokból épülnek fel:
-
változókat létrehozó ún. deklarációs utasítások; a változók a programok legfontosabb összetevői, amelyek egyedi névvel rendelkeznek és különböző típusú értékeket tárolhatnak; például
- var n; // az 'n' nevű változó deklarálása
- var i=1; // az 'i' nevű változó deklarálása, és 1 kezdőérték beállítása
- a változók értékét megváltoztató ún. értékadó utasítások; ezek rendszerint egy vagy több művelet eredményét tárolják el egy változóban; például
- i=i+1; /* az 'i' nevű változó aktuális értékéhez 1 hozzáadása, és a művelet eredményének eltárolása ugyanabban az 'i' változóban (amelynek az értéke innentől kezdve az eggyel megnövelt érték lesz, a korábbi érték törlődik) */
- kerulet=2*r*3.14; /* az 'r' nevű változó megszorzása először 2-vel, majd 3.14-gyel (π), és a szorzat eltárolása a 'kerulet' nevű változóban */
- a változók értékét beolvasó vagy kiíró i/o (input-output) utasítások; például
- writeln("a kerület értéke: "+kerulet); /* a 'kerulet' nevű változó kiírása a képernyőre a "a kerület értéke: " szöveg után */
- writeln("____________"); /* a "____________" szöveg kiírása a képernyőre (a megadott példaprogramokban így jelöljük majd a program végét) */
- az utasítások végrehajtásának sorrendjét meghatározó vezérlési szerkezetek (szekvencia, szelekció és iteráció); például
-
a=2; b=3; c=a+b; writeln(c); /* legyen az 'a' nevű változó értéke 2, majd a 'b' nevű változó értéke 3, ezután az 'a' és 'b' összegét (a+b) számítsuk ki és tároljuk a 'c' nevű változóban, majd a 'c' értékét írassuk ki */ → szekvencia
-
if(i==1) { writeln("igaz"); } else { writeln("hamis"); } /* az 'i' nevű változó aktuális értékétől függően "igaz" (ha 'i' értéke 1) vagy "hamis" (ha 'i' értéke nem 1) kiírása */ → (kétirányú) szelekció vagy elágazás
-
i=3; if(i<10) { write("0"); } writeln(i); /* ha az 'i' nevű változó aktuális értéke 10-nél kisebb (ha 'i' egy számjegyű természetes szám), akkor egy "vezető" nulla (0) kiírása */
→ (egyirányú) szelekció
- var j="5";
switch(j) {
case "1": writeln("elégtelen"); break;
case "2": writeln("elégséges"); break;
default: writeln("rendben");
}
/* ha a 'j' változó értéke '1', akkor "elégtelen", ha '2', akkor "elégséges", egyébként pedig "rendben" kiírása */
→ (többirányú) szelekció
-
var i=1; while(i<=n) { writeln(i); i=i+1; } /* az 'i' (ciklus)változó értékének a kiírása addig, amíg az 'i' értéke az 'n' változó aktuális értékénél kisebb vagy egyenlő */ → iteráció vagy (elöltesztelő) ciklus
!! a ciklusblokk utolsó utasítása (i=i+1;) nélkül végtelen ciklust kapunk !!
-
for(var i=1;i<=n;i=i+1) { writeln(i); } /* az 'i' nevű ciklusváltozó értékének a kiírása addig, amíg az 'i' értéke az 'n' változó aktuális értékénél kisebb vagy egyenlő; ebben a példában a 'for' ciklus egyenértékű a fenti 'while' ciklussal */ → iteráció vagy (rögzített lépésszámú) ciklus
Az utasítások sorrendjét meghatározó három legfontosabb strukturált programszerkezet vagy vezérlési szerkezet a következő:
- szekvencia
- elágazás vagy szelekció
- ciklus vagy iteráció
Az algoritmusok szemléltetésére folyamatábrákat használhatunk.
A fenti strukturált programszerkezetek folyamatábrák segítségével a következőképpen szemléltethetők (vö. Vég József: Folyamatábra, 2022-09-24):
A szekvencia egymás utáni utasítások sorozata (amelyeket például pontosvesszővel választhatunk el egymástól).
Az ábrán szereplő kétirányú elágazást (vagy elágaztatást) például JavaScript nyelven a következő utasítással tudjuk kódolni:
if(feltétel) {
utasítás(ok)
}
else {
utasítás(ok)
}
Ez a következőképpen fordítható le:
"Ha a feltétel teljesül (vagyis igaz), akkor hajtsd végre az 'if' után kapcsos zárójelben megadott utasítás(oka)t; egyébként pedig (vagyis ha a feltétel nem teljesül) hajtsd végre az 'else' után kapcsos zárójelben megadott utasítás(oka)t."
Az ábrán szemléltetett előltesztelő ciklust pedig JavaScript nyelven a következő utasítással tudjuk kódolni:
while(feltétel) {
utasítás(ok)
}
Ez a következőképpen fordítható le:
"Mindaddig, amíg a feltétel teljesül (vagyis igaz), (újra és újra) hajtsd végre a 'while' után kapcsos zárójelben megadott utasítás(oka)t."
Például az első 'n' szám kiíratását a következő algoritmussal tudjuk megvalósítani:
Az algoritmust JavaScript nyelven például a következőképpen kódolhatjuk:
// az első 'n' szám kiíratása
var n=10;
var i=1;
while(i<=n) {
writeln(i);
i=i+1;
}
writeln("_____________");
Vegyük észre, hogy az 'n' változó és az 'i' változó aktuális értéke határozza meg a 'while' ciklus ismétlődéseinek számát. Az 'n' változó kezdeti értéke 10, és az 'i' kezdeti értéke 1. Mivel a ciklus minden végrehajtásakor 'i' értéke eggyel nő, a tizedik végrehajtás után a ciklus befejeződik (ugyanis ekkor az 'i' értéke 11 lesz, ami már nagyobb 'n' értékénél).
Mivel a kódban szereplő ciklusszerkezet a gyakorlatban sokszor előfordul, a JavaScript nyelvben rendelkezésre áll ennek egy tömörebb formája, az ún. rögzített lépésszámú ciklus. Ezzel az algoritmus a következőképpen írható le:
// az első 'n' szám kiíratása (második változat)
var n=10;
for(var i=1;i<=n;i=i+1) {
writeln(i);
}
writeln("_____________");
A 'for' ciklus fejrésze "magába olvasztotta" az előző program
var i=1;
és
i=i+1;
utasításait, amelyeket a ciklusfeltétel előtt és után adunk meg. Bár két sor megtakarítása nem tűnik soknak, "sok kicsi sokra megy", és a tömörebb írásmód összetettebb programok esetén áttekinthetőbb programkódot eredményezhet. (Az i=i+1; utasítást rövidíthetjük i++; módon.)
A számítógép univerzális, automatikus működésű, kívülről vezérelhető, műszakilag megvalósított rendszer.⇒
