Az algoritmusok elemei

A feladattól a kész programig

1. Specifikáció: a feladat megfogalmazása
2. Algoritmizálás: a megoldás módszerének kitalálása
3. Kódolás: a megoldás leírása egy programozási nyelven
4. Tesztelés: a program kipróbálása

Részfeladatok

• Az algoritmizálás a bonyolultabb, ötletelést igénylő
• A kódolás többé-kevésbé szisztematikus, magától értetődő. A meglévő megoldást kell megfogalmazni az adott programnyelven.

Elemi lépések, műveletek a számítógépen

• Kiírunk valamit a képernyőre
• Adatot kérünk a felhasználótól
• Kiszámolunk valamit
• Értéket adunk egy változónak
• …

Egyszerű program

PROGRAM
  KIÍR: "Helló, világ!" egyetlen elemi lépés
PROGRAM VÉGE

A gyakorlaton szerepeltek algoritmusok: prímtényezős felbontás, rendezés, számlálás…

• A pszeudokódot szabadosan adtuk meg:
  • Beszámoztuk a sorokat
  • „Ugorj az 5. sorra”
  • „Ha x<7, folytasd a 14. sornál”…
• Az ilyet úgy hívják, spagetti kód
• Az ugrásoktól áttekinthetetlen lesz a program

Strukturált programok (structured programs)

• Amelyek szekvenciából, elágazásból és ciklusból épülnek fel
• Matematikailag bizonyított: minden megoldható így
• Tapasztalat: sokkal jobban, mint spagetti kóddal!

• Alapvetően egymás után, de ez megváltoztatható vezérlési szerkezetekkel (control structure)
• Speciális programbeli utasítások tartoznak hozzájuk: ezek a vezérlésátadó utasítások (control flow statement)

A vezérlési szerkezetek lényege az, hogy valamilyen döntés (egy feltétel teljesülése) alapján máshol folyatódik általuk a program végrehajtása – nem a pszeudokódban következő utasításnál.

Program

léptetPROGRAM
    KIÍR: "Kérem a számot!"    
    BEOLVAS: a    
    a=a·a    
    KIÍR: a    
PROGRAM VÉGE

Működés

a: 

Mire használjuk itt a változót? Arra, hogy megjegyezzük a felhasználótól származó értéket – és később a négyzetét.

Feladat: Írjunk programot, amely kér egy számot a felhasználótól.
Mondja meg, hogy páros vagy nem.

A programsorok végrehajtása feltételhez köthető.

Fogalmak: elágazás (conditional), feltétel (condition, predicate), igaz ág (consequent), hamis ág (alternative).

• Elágazás: az egész vezérlési szerkezet
• Feltétel: logikai kifejezés, amelynek igaz/hamis voltától függ, hogy végrehajtódik-e az adott programrészlet
• Igaz ág, következmény: az a programrészlet, amely akkor hajtódik végre, ha a feltétel igaz volt
• Hamis ág, „else” ág: akkor hajtódik végre, ha a feltétel hamis volt

Program

léptetPROGRAM
    BEOLVAS: szam    
    HA szam/2 maradéka 0, AKKOR    
        KIÍR: "páros"             ha teljesül
    EGYÉBKÉNT
        KIÍR: "páratlan"         ha nem teljesül
    FELTÉTEL VÉGE
PROGRAM VÉGE

Működés

szam: 

Ez a programrész megnézi, hogy egy szám pozitív, nulla vagy negatív. Mire jó ez? Pl. egy másodfokú egyenlet diszkussziójához használható. Ha a diszkrimináns pozitív, két valós megoldás van. Ha nulla, akkor csak egy. Ha negatív, egy sem.

léptetPROGRAM
    BEOLVAS: szam    

    HA szam>0, AKKOR    
        KIÍR: "pozitív"    
    FELTÉTEL VÉGE

    HA szam=0, AKKOR    
        KIÍR: "nulla"    
    FELTÉTEL VÉGE

    HA szam<0, AKKOR    
        KIÍR: "negatív"    
    FELTÉTEL VÉGE
PROGRAM VÉGE

Az elágazásoknál fontos látni azt, hogy akár teljesül a feltétel, akár nem, a program folytatása mindenképp az elágazás utáni műveletnél lesz.

Feladat: írjunk programot, amelyik növekvő sorrendben kiírja a számokat.

KIÍR: 1
KIÍR: 2
KIÍR: 3
…
KIÍR: 8
KIÍR: 9
KIÍR: 10

Probléma

• Egyrészt: kipontozás? Ez nem szép megoldás. Sorminta!
• Másrészt: mi van akkor, ha a felhasználó kellene megmondja, meddig kellenek a számok? A program kódja nem függhet a bemenetétől!

A programozásban inkább ne!

Ciklus (loop): programrész ismétlése, amíg egy feltétel fennáll

Fogalmak: ciklusmag (loop body), ciklusfeltétel (loop condition), iteráció (iteration), ciklusváltozó (iterator).

• Ciklusmag, ciklustörzs: az ismételt utasítás(ok)
• Ciklusfeltétel: amely kifejezés igaz/hamis értéke alapján eldől, hogy végrehajtódik-e a ciklus törzse
• Iteráció: a ciklustörzs egy végrehajtása
• Ciklusváltozó, iterátor: a ciklust vezérlő változó, itt az i
• Elöltesztelő ciklus (pre-test loop): a feltételt a ciklustörzsbe lépés előtt ellenőrizzük

léptetPROGRAM
    KIÍR: "Meddig írjam ki?"    
    BEOLVAS: n    

    i=1    
    CIKLUS AMÍG i≤n    
        KIÍR: i    
        i=i+1    
    CIKLUS VÉGE

    KIÍR: "."    
PROGRAM VÉGE

i: 
n: 

Itt mire jó a változó? Azzal tudjuk elérni azt, hogy a ciklus törzsében lévő kiírás utasítás mindig más számot írjon a képernyőre! Azzal számoljuk, hogy éppen hol tartunk.

Feladat: számoljuk ki a felhasználó által megadott szám négyzetgyökét Hérón módszerével (babilóniai módszer).

A módszer

• Adott: szám; keressük: gyök²=szám
• Tippelünk egy gyököt
• A megoldás valahol tipp és szám/tipp között van
• Ezért az új tipp legyen (tipp + szam/tipp)/2
• Ezt ismételgessük, amíg a különbség kellően kicsi nem lesz

Ezt a módszert alexandriai Hérón találta ki – ugyanaz a Hérón, aki a háromszög területének kiszámítására használható képletet is. Ugyanazt elmondhatjuk a programozásról, mint amit sok más tudományról is el lehet mondani: „már a régi görögök is”.

léptetPROGRAM
    szam=2    
    tipp=1    
    CIKLUS AMÍG |tipp-szam/tipp|>0.001    
        tipp=(tipp + szam/tipp)/2    
    CIKLUS VÉGE
    KIÍR: "A keresett gyök: ", tipp    
PROGRAM VÉGE

szam:      
tipp:      

szam/tipp: 
különbség: 
átlag:     

Számok kiírása 1-től 10-ig:

i=0

CIKLUS AMÍG i≤9

    i=i+1

    KIÍR: i

CIKLUS VÉGE

i=1 első

CIKLUS AMÍG i≤10  utolsó

    KIÍR: i               teendők

    i=i+1     következő

CIKLUS VÉGE

i=1

CIKLUS AMÍG i≤10

    KIÍR: i

    i=i+1

CIKLUS VÉGE

CIKLUS i=1-től, i≤10-ig, +1-esével

    KIÍR: i



CIKLUS VÉGE

• Ez nagyon gyakori fordulat
• Az áttekinthetőség, olvashatóság miatt alkalmazzuk
• Rávezet, hogy átgondoljuk: honnan, hova, hogyan
• „i minden értékére… 1-től 10-ig 1-esével… csináljuk ezt…”

Ciklusfeltételek

• A ciklus bennmaradási feltétele logikai kifejezés
• Újra és újra kiértékelődik minden iterációban
• Ha teljesül, végrehajtódik a törzs
• Ha nem, a ciklus után folytatódik a program

Ciklusok

• Hányszor? Ahányszor a feltétel teljesül
• Ez lehet 0 is: a törzs egyszer sem hajtódik végre
• A feltétel előbb-utóbb hamissá kell váljon, különben végtelen ciklus (infinite loop) keletkezik
• A ciklusváltozónak változnia kell!

A feltétel hamissá kell váljon előbb-utóbb: praktikusan ez azt is jelenti, hogy a ciklusváltozónak, ha van, az egyes iterációk között változnia kell. Különben ugyanaz marad az értéke, és a ciklus feltételének igazságértéke sem fog változni! Ha nincs olyan utasítás a ciklusban, amely a ciklusváltozó értékét változtatja, az gyanús.

Feladat: írjunk programot, amelyik kér egy valós számot a felhasználótól, és Hérón módszerével kiszámolja a gyökét.

Tudjuk, hogy negatív számnak nincsen gyöke a valós számok körében. Ez nem csak definíciós kérdés, hanem a programunkat is érinti. Ugyanis ha Hérón algoritmusa negatív számot kap, akkor ide-oda ugrál pozitív és negatív tippek között. Így végtelen ciklus keletkezik: a program soha nem áll le. Ezért a felhasználótól kapott számot az algoritmus futtatása előtt ellenőrizni kell. Ha negatív, akkor nincs gyök, és ezt jelenzni kell. Ha nem, akkor indulhat a számítás.

A bemeneti adatok érvényességi köre része kell legyen a specifikációnak! Jelen esetben például meg kell mondani azt, hogy a program egy valós számot kell kérjen (ez a bemenet), amelynek a gyökét fogja meghatározni (ez a kimenet), de a beolvasott szám nem lehet negatív.

PROGRAM
      KIÍR: "Melyik szám gyöke?"
      BE: szam
      HA szam≤0, AKKOR
            KIÍR: "A szám pozitív kell legyen!"
      EGYÉBKÉNT
            tipp=1
            CIKLUS AMÍG |tipp-szam/tipp|>0.001
                  tipp=(tipp + szam/tipp)/2
            CIKLUS VÉGE
            KIÍR: "A keresett gyök: ", tipp
      FELTÉTEL VÉGE
PROGRAM VÉGE

A vezérlési szerkezetek tetszőleges mélységben egymásba ágyazhatóak. A lenti program egy szekvenciát tartalmaz, amelynek része a szám beolvasása és egy feltétel. A feltétel hamis ágában egy újabb szekvencia van, amely egy ciklust is tartalmaz.

C forráskódok

Nyelvtani szabályok

• Összefoglaló nevük: szintaxis
• Minden nyelvben van, pl. magyarban is:
  • Én alszom, ő alszik ← helyes
  • Mi alszanak ← hibás
• A forráskód meg kell feleljen az összes szabálynak

Szintaktikai hibák

int x, a, b, c;

printf("Az eredmény:")  // lemaradt pontosvessző

printf("%d\n", y);      // y: ismeretlen változó

x=2*(a+b+c;             // lemaradt bezáró zárójel

EBNF: formalizmus a szintaxis leírására.

szám = nemnulla, { számjegy };
nemnulla = '1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9';
számjegy = '0' | nemnulla;

• Akárhány számjegyből állhat, nem kezdődhet nullával.
• Helyes: 98, 54079, 43, 1, 112.
• Helytelen: 1ax, abcd, s98, 012.

A C nyelv összes nyelvtani szabálya kb. 5 oldalnyi EBNF-fel leírható. De ezt most nem fogjuk megtenni.

EBNF leírást használnak a programozók is, akik egy nyelvet használnak, és szintaxisát szeretnék megérteni. De ebből dolgoznak azok is, akik a fordítóprogramot írják: ha matematikai precizitással adottak a nyelvtani szabályok, akkor a nyelv minden mondatát könnyű értelmezni. Ezzel még fogunk foglalkozni.

printf("Helló, világ!\n");

x=3;
printf("x+1=%d\n",              // több sorba is írható
       x+1);

printf("A négyzet oldalhossza?\n");
scanf("%lf", &a);
printf("Átló=%f\n", a*sqrt(2)); // négyzetgyök (square root)

• A kifejezések konstansokból, változókból és operátorokból állnak.
• A kifejezés utasításokat pontosvessző zárja.

Egy vagy több változó definíciója „kvázi EBNF”-ben:

típus név [=kezdeti érték] {, név [=kezdeti érték]};

Példák C-ben:

int x=3;              // x nevű egész, kezdeti értéke 3

double f_1=0, f_2=0;  // két valós, f_1 és f_2

int szam, SZAM;       // inicializálatlanok. ez két különböző!

• A változó neve tartalmazhat betűket, számokat és _ (alulvonás) karaktert.
• Számmal nem kezdődhet, ékezetes betű sem lehet benne.

Egy változónak adhatunk kezdeti értéket (rögtön a definíciójakor). Ezt inicializálásnak is hívjuk, és pontosan ugyanaz, mint az értékadás. (Értéket többször is kaphat.) A változókat nem kötelező inicializálni, azonban figyelni kell arra, hogy ne használjuk az értéküket addig, amíg nem adtunk nekik.

#include <stdio.h>
                        // bemenet/kimenet utasításokhoz
int main()
{
    int x;              // változó definíciók

    x=2*3;
    printf("%d\n", x);  // utasítások


    return 0;           // program vége
}

A programunk maga is egy utasításblokk.

• A blokk elején lehetnek a változódefiníciók. (Csak ott!)
• Után pedig utasítások.

A blokkoknak csak az elején lehetnek változódefiníciók. Ez azt jelenti, hogy az összes szükséges változót az elején meg kell adnunk, neveikkel és típusaikkal együtt. Az nem baj, ha csak később kapnak értéket.

if (feltétel)
    utasítás;
[ else utasítás; ]

if (x>0)                       // a feltétel zárójelben
   printf("pozitív!\n");
else
   printf("nem pozitív.\n");   // hamis ág (elmaradhat)

if (x<0) {                   // több utasítás: { } között
   x=-x;
   printf("x negatív volt.\n");
}                            // itt nem kell pontosvessző

Ha a feltétel következményében vagy hamis ágában több utasítás is van, az egy szekvencia, ami C-ben utasításblokként jelenik meg. Ezért kellenek a kapcsos zárójelek. Ha csak egyetlen utasítás van, akkor nincsen rájuk szükség, de nem is hiba kiírni őket.

while (feltétel)
    utasítás;

while (x>0)              // a feltétel zárójelben
    x=x-1;

while (x>0) {            // több utasítás: { } között
    printf("x=%d\n", x);
    x=x-1;
}

#include <stdio.h>
#include <math.h>

int main()
{
    double szam, tipp;

    printf("Szám: ");
    scanf("%lf", &szam);

    tipp=1;
    while (fabs(tipp-szam/tipp) > 0.001) // |tipp-szam/tipp|
        tipp=(tipp + szam/tipp)/2;

    printf("%f gyöke %f.\n", szam, tipp);

    return 0;
}

for (innentől; idáig; így)
    utasítás;

1 2 3 4 5

for (x=1; x<=5; x=x+1) // pontosvesszők!
    printf("%d ", x);

„for every value of x from (x=1; to x<=5; step by x=x+1)”

/* számok egytől tízig */

for (x=1; x<=10; x=x+1)
    printf("%d ", x);

x=1;
while (x<=10) {
    printf("%d ", x);
    x=x+1;
}

A két kódrészlet pontosan ugyanazt csinálja.

• Mindig azt érdemes írni, amelyik áttekinthetőbb
• A gépnek mindegy, nekünk számít!

Érdekesség: Harold Abelson az MIT egyetem professzora, a Creative Commons és a Free Software Foundation alapítványok egyik alapító tagja. (Az utóbbi alapítványhoz tartozik a GNU projekt, amely keretében a Linux rendszert is fejlesztik. Ez az androidos okostelefonok alapja.) Társszerzője a Structure and Interpretation of Computer Programs könyvnek, amelyből a fenti gondolat is származik.

#include <stdio.h>

int main()
{
   int y;

   for (y=1; y<=5; y=y+1) {
      int x;

      for (x=1; x<=5; x=x+1)
         printf("%2d ", x*y);
      printf("\n");
   }

   return 0;
}

A szorzótábla kirajzolása két ciklussal. Kívül a sorok ciklusa (y, öt iteráció), és azon belül soronként öt szám (x, öt iteráció soronként) és egy újsor karakter. Az x változó csak a belső ciklushoz van, így azt érdemes belül definiálni, mert csak ott használjuk. A változódefiníció szabályait viszont ott is betartjuk: a blokkok elejére kerül a definíció, és utána az utasítások.

#include <stdio.h>
#include <math.h>

int main()
{
│   double szam;
│
│   printf("Szám: ");
│   scanf("%lf", &szam);
│   if (szam<=0) {
│   └─  printf("Pozitív kell legyen!\n");
│   } else {
│   │   double tipp=1;
│   │   while (fabs(tipp-szam/tipp) > 0.001) {
│   │   └─  tipp=(tipp + szam/tipp)/2;
│   │   }
│   └─  printf("%f gyöke %f.\n", szam, tipp);
│   }
│
└─  return 0;
}

Hogy ki pontosan hova helyezi el a nyitó és záró kapcsos zárójeleket, hova tesz szóközöket a műveleti jelek köré stb. – ez ízlés kérdése. Rengeteg stílus alakult ki, amelyek közül a tananyagban az ún. K&R stílust fogjuk használni. (Persze itt-ott ettől eltérünk, főleg ha ezt az előadásban a dia szűkös mérete kényszeríti.) Ezt a stílust tréfásan egyiptomi zárójelezésnek is szokták nevezni, a kapcsos zárójelek elhelyezése miatt.