Tömbök algoritmusai. Rekurzió

A nagy ZH-n, vizsgákon halálfejes hibának nevezzük azokat a hibákat, amik leginkább arról tanúskodnak, hogy az elkövetőjük soha gépen C programot még nem írt. Eléggé meglehetős pontlevonások járnak értük.

include [stdio.h]

world main {
   var $szam, $szorzat;
   
   repeat {
      scanf $szam
      $szam=$szam · $szorzat
   } until (szam<>0)

   printf $szorzat;
}

/* fv-ben fv */
int hányprím(int meddig) {
   int prím(int szám) {
      …
   …

/* „amíg minden elem -1” */
while (for (i=0; i<10; ++i)
         tömb[i]==-1; ) {

/* beolvasás és összegzés */   
scanf("%d", &+sum);

/* tíz szám visszafelé */
int a, b, c, d, …;

scanf("%d", &a);
  –||– ("%d", &b);
         –||–    c);
…
printf("%d", c);
  –||–   ("%d", b);
  –||–   ("%d", a);

/* triviális túlindexelés */
int tomb[10];
for (i=1; i<=1000; ++i)
   tomb[i]=1;

/* indefinit méretű tömb */
char s1[];
gets(s1);
char *s2;
gets(s2);

Pl. „térjen vissza a függvény IGAZ-zal, ha páros, HAMIS-sal, ha páratlan a paraméterként kapott szám”

/* felesleges, nem kért input/output művelet */
void fv() {
   int szám;
   scanf("%d", &szám);
   if (szám%2==0) printf("páros");
   else printf("páratlan");
}

/* Harsányi János - 49 */
void j(char*s){char*p=s;while(*p=*s)p+=*s++!=32;}

/* Seres Márk Dániel - 46 */
m(char*c){for(int i=0;*c=c[i];*c-32?c++:i++);}

/* Szabó Antal - 46 */
a(char*s){for(char*t=s;*t;(*t=*s++)-32&&t++);}

/* Széll András - 45 */
a(char*s){for(char*k=s;*s=*k;*k++==32?:s++);} // !

/* Marussy Kristóf - 44 */
k(char*a){for(char*b=a;*b=*a++;)*b^32&&++b;}

/* Czirkos Zoltán - 43 */
r(char*s){for(char*p=s;*p=*s;p+=*s++!=32);}

/* Kővágó Zoltán - 42 */
x;z(char*b){for(x=0;b[x]=*b;x-=*b++==32);} // !

Tömbi algoritmusok: keresések

„Tapasztalt C programozó – nagyjából azt jelenti, hogy tömbkezelésből teljesen profi.” – Marshall Cline

Keresés táblázatban – kérdéseink

• Szerepel-e egy konkrét elem?
• Hol van az első ilyen elem?
• Egy bizonyos tulajdonságú elem
  • Ezt a keresés kulcsának nevezzük

Generikus algoritmusok

• A keresések ugyanúgy működnek:
  • Akármilyen típusú az adat (szám, sztring, ember, …)
  • Akármilyen tulajdonság (adott értékű elem, páros elem, „a” betűvel kezdődő, 170–180 centi magas)
• A következő példák double[]-ben keresnek adott elemet

int van_e(double *szamok, int meret, double keresett) {
   int i, van_talalat;
   
   van_talalat=0;
   i=0;
   while (i<meret && !van_talalat) {
      if (szamok[i]==keresett)
         van_talalat=1;
      ++i;
   }
   
   return van_talalat; // miért állt meg a ciklus?
}

• „Van-e?” – elég egy olyat találni, és megállhat a ciklus
• Ha egyet sem találtunk, akkor hamis érték marad a változóban

Egyéb megvalósítások

A van-e függvényt egyéb formákban is lekódolhatjuk. Ezek mind ugyanolyan jól működnek, mint a fenti változat.

van_talalat=0;
for (i=0; i<meret && !van_talalat; ++i)
   if (szamok[i]==keresett)
      van_talalat=1;

return van_talalat;

for (i=0; i<meret && szamok[i]!=keresett; ++i)
   ;

return i<meret;

for (i=0; i<meret; ++i)
   if (szamok[i]==keresett)
      return 1;

return 0;

for (i=0; i<meret; ++i)
   if (szamok[i]==keresett)
      break;

return i<meret;

int hol_van(double *szamok, int meret, double mit)
{
   int i;
   
   for (i=0; i<meret; ++i)
      if (szamok[i]==mit)
         return i;

   return -1;
}

• A függvény a megtalált elem indexével tér vissza
• Ha nincs meg, akkor -1-gyel vagy meret-tel
  • Egyik sem lehet index, így megkülönböztethető

A nincs találatra a -1-et és a tömb méretét is elterjedten használják. Mindkettő a tömb indexeinek tartományán kívül esik (mivel az 0…meret-1), ezért mindkettő egyformán jó lehet. A -1 előnye, hogy szembetűnőbb, a méret előnye, hogy nem negatív szám (mivel a tömb mérete amúgy sem lehet negatív, így elvileg a méreteket, indexeket tárolhatnánk előjel nélküli változókban is).

Pointer visszatérés Pointer aritmetika

double *keres(double *szamok, int meret, double mit)
{
   int i;
   
   for (i=0; i<meret; ++i)
      if (szamok[i]==mit)
         return szamok+i;  // &szamok[i]

   return NULL;
}

double *keres(double *szamok, int meret, double mit)
{
   double *iter;
   
   iter=szamok;
   while (iter!=szamok+meret) { // utolsó utáni
      if (*iter==mit)
         return iter;
      ++iter;                   // pointer lép a következőre
   }

   return NULL;
}

tomb[elemek]=keresett; // szándékos!
i=0;
while (tomb[i]!=keresett)
   ++i;
if (i!=elemek)
   return i;  // meglett!
else
   return -1; // a strázsát találtuk meg

Lényege: betesszük a tömb végére a keresett elemet.

int tomb[10+1]={2, 5, 7, 3, 8, 6, 9, 4, 8, 7}; // +1!
hely=strazsakeres(tomb, 10);

Ha rendezett a tömb…

• Nem csak == és != van, hanem a < és a > is hasznos információ!
• ==: Ezt keressük!
• <: Valahol előrébb kell legyen.
• >: Hátrébb kell legyen.

új következő C megvalósítás

int binkeres(double *t, int db, double mit) {
   int min=0, max=db-1, // határok
       kozep=(min+max)/2;

   /* amíg nincs meg és el nem fogy a vizsgálandó rész */
   while (t[kozep]!=mit && min<=max) {
      if (t[kozep]<mit)
         min=kozep+1;   // középtől jobbra
      else
         max=kozep-1;   // középtől balra
      kozep=(min+max)/2;
   }

   /* miért állt meg a ciklus? megtaláltuk vagy nem? */
   return t[kozep]==mit ? kozep : -1;
}

Lineáris keresés

• Lehet, hogy egyből megtaláljuk, lehet, hogy a végén lesz
• Átlagosan méret/2 lépés kell
• A keresési idő egyenesen arányos a tömb méretével
  • méret×2 → idő×2
  • méret×3 → idő×3
  • …

Bináris keresés

• Minden lépésben felezni tudjuk az intervallumot
• A keresési idő ~ log₂méret
• 1000 elem → 10 lépés
• 1 millió → 20 lépés
• 1 milliárd → 30 lépés! ☺

Algoritmusok hatékonysága

Rendezések

Rendezett tömb

• Növekvő sorrend: a szomszédos elemekre t[i]<=t[i+1]
• Tranzitív tulajdonság: ha A≤B és B≤C, akkor A≤C

A „helyben rendezés” fogalma

• Nincs segédtömb, a meglévő tömbben dolgozunk
• Megengedett lépések: két elem összehasonlítása és cseréje

A rendezések működése

• „Oszd meg és uralkodj” elv (divide and conquer)
• A rendezett részt növeljük, amíg el nem fogy
• Genericitás: az algoritmusok általánosak (sorrend, típus)

Lényege: egymás melletti elemek összehasonlítása és cseréje.

Egy sor csere által a legnagyobb elem a végére kerül.

void buborek(double t[], int db) {
   int i, j;

   /* egyre rövidebb tömbrészletek ciklusa */
   for (i=db-1; i>0; --i)
      /* egymás utáni párok ciklusa */
      for (j=0; j<i; ++j)
         if (t[j+1]<t[j]) {      // összehasonlítás
            double temp=t[j];    
            t[j]=t[j+1];         // csere
            t[j+1]=temp;
         }
}

Keverő rendezés (cocktail sort)

nyulak (rabbits)

nagy értékű elemek, amelyek a hamar a helyükre kerülnek

teknősök (turtles)

kicsi értékűek, amelyek lassan vándorolnak a tömb elejére

Ötlet: a rendezést felváltva egyik-másik irányba végezzük.

Javított buborékrendezés (improved bubble sort)

Figyeli, hogy egy fésülés során volt-e csere. Ha nem, leállítható a rendezés.

Lényege: megkeresi a rendezetlen tömbrészlet legkisebb elemét, és az elejére rakja.

void kozvetlen(double t[], int db) {
   int i, j, minindex;

   for (i=0; i<db-1; ++i) {
      minindex=i;                // minimum keresése
      for (j=i+1; j<db; ++j)
         if (t[j]<t[minindex])
            minindex=j;
      if (minindex!=i) {         // csere?
         double temp=t[minindex];
         t[minindex]=t[i];       // csere.
         t[i]=temp;
      }
   }
}

A fenti megvalósítás nem a legnagyobbat, hanem a legkisebb elemet keresi meg a tömbből, és azt rakja az elejére, ahogyan az előbbi dián látható animáció is. A kód szerkezete hasonló az előzőéhez, itt is ciklusban ciklus kell. A külső ciklus i változója éppen azt az indexet tárolja mindig, amelyik helyre az odavaló elemet keressük. Első futásnál ez 0, vagyis az egész tömb (t[0]…t[db-1]) legkisebb elemét keresi meg a j-s, belső ciklus. A keresés után a legkisebbnek talált elem ide kerül, és később már nem is mozdul el innen.

Buborék

Közvetlen kiválasztás

A fenti animáció kicsit csal, nem túl igazságos… Ugyanis az összehasonlítások idejére nem figyel, hanem csak a helycseréket animálja. Ugyanakkor a lényeg látszik: a buborékrendezés nagyon sok ideig bíbelődik a cserékkel, míg a közvetlen kiválasztásos módszer hamarabb végez a tömbbel.

Ötlet: egy indexelő tömböt rendezzünk, ne az eredetit!

 

Így bármilyen nagy a tömbelem, ugyanolyan gyorsak a cserék!

Ember nevsor[100];
int index[100];   // ugyanakkora

printf("%s", nevsor[index[5]].nev);
/* nevsor[nev_index[i]]             → név szerinti sorrend */
/* nevsor[szuletesi_datum_index[i]] → dátum szerinti sorrend */

Ha nem az eredeti tömböt rendezzük, hanem az indexelő tömböt, akkor sokkal gyorsabbak a rendezések, és ezáltal a csere is. További előny, hogy egyszerre akár többféle rendezettséget is fenntarthatunk, mert több indexelő tömbünk is lehet!

Lényege: ha az egymás mellettiek jó sorrendben vannak, léphetünk egyet előre. Ha rossz sorrendben, akkor csere.

Ha a csere által rossz sorrend keletkezik, az csak a csere előtt lehet, ezért visszafelé kell lépni egyet.

void torperendez(double t[], int db) {
    int i;
    
    i = 0;
    while (i < db) {
        if (i == 0 || t[i-1] <= t[i]) // jó sorrend?
            i++;                /* előre */
        else {
            double tmp = t[i];  /* csere */
            t[i] = t[i-1];
            t[i-1] = tmp;
            i--;                /* vissza */
        }
    }
}

Rekurzió

Pl. mi lenne, ha egy faktoriálist számító masina így nézne ki belülről:

     ┌
     │ 1,        ha n=0
n! = ┤
     │ n·(n-1)!, ha n>0
     └

Ez helyes, hiszen ha N=0, a faktoriálisa 1, ha nem 0, akkor pedig N faktoriálisa N szorozva N-1 faktoriálisával.

Ha beteszünk a nagy faktoriális gépbe egy miniatűr faktoriális gépet (működjön az bárhogy is), egy jó megoldást kapunk.

A verem nevű memóriaterületre kerülnek függvényhíváskor a paraméterek és a visszatérés adatai. Ide kerülnek a lokális változók is.

int fakti(int mie) { 
   int szorzat, i;
   szorzat=1;    
   for (i=2; i<=mie; i+=1)    
      szorzat*=i;    
   return szorzat;    
}

int main() {
   int x=fakti(5);
   printf("%d", x);
   
   return 0;
}

Rekurzív függvény az, amely meghívja saját magát.

     ┌
     │ 1,        ha n=0
n! = ┤
     │ n·(n-1)!, ha n>0
     └

int fakt(int n)
{
   if (n==0)
      return 1;
   else
      return n*fakt(n-1);
}

Ezt a működést a verem teszi lehetővé!

léptetint fakt(int n) { 
   if (n<=1)   
      return 1;   
   else 
      return n*    
              fakt(n-1);   
} 
 
int main() { 
   int eredm; 
   
   eredm=fakt(3);   
   printf("3!=%d", eredm);   
   return 0;   
}

fakt(1)
n: 1
(vissza): 

fakt(2)
n: 2
(vissza): 

fakt(3)
n: 3
(vissza): 

main()
eredm: 

A lokális változók csak addig léteznek, amíg a faktoriálist számoló függvény belsejében van a végrehajtás. Amint visszatér abból a main()-be, azok megszűnnek.

Gondoljunk bele: most használjuk ki igazán, hogy a függvény után a gép onnan folytatja a végrehajtást, ahonnan meg lett hívva! Ha ez sok függvényhívással odébb volt, akkor is. Ha sok rekurzív függvényhívással beljebb (lejjebb) volt, akkor is! Ezért mindig tudja a gép, hogy épp a fakt(n-1) kiszámítása ért véget, és visszaugrik abba a példányba, ahol a fakt(n) kiszámítása folyik.

Leállási feltétel

• Kell legyen egy báziskritérium: egy olyan eset, amikor már nem hívja meg magát.
• Minden lépésben közeledni kell a báziskritériumhoz.

     ┌
     │ n, ha n<2   
F(n) ┤
     │ F(n-2)+F(n-1) amúgy
     └

int fib(int n)
{
  if (n<2)  // báziskritérium
    return n;
  else
    return fib(n-2)+fib(n-1);
}

A hívások rajzon

laboron még
lesz róla szó

Ez nem túl hatékony megvalósítás. Vegyük észre a rajzon: pl. a fib(2) értékét többször is kiszámoljuk.

void elore(char *sztring) {
   if (*sztring=='\0')
      return;
   putchar(*sztring);
   elore(sztring+1);
}

előre("InfoC") // InfoC
   putchar('I')
   előre("nfoC")
      putchar('n')
      előre("foC")
         putchar('f')
         előre("oC")
            putchar('o')
            előre("C")
               putchar('C')
               előre("")
                  /* semmi */

void hatra(char *sztring) {
   if (*sztring=='\0')
      return;
   hatra(sztring+1);
   putchar(*sztring);
}

hátra("InfoC") // CofnI
   hátra("nfoC")
      hátra("foC")
         hátra("oC")
            hátra("C")
               hátra("")
                  /* semmi */
               putchar('C')
            putchar('o')
         putchar('f')
      putchar('n')
   putchar('I')

Tömböket (és később: listákat) C-ben ciklusokkal dolgozunk fel, hiszen az a természetesen adódó eszköz erre a feladatra. Az itt bemutatott rekurzív sztringfeldolgozás célja kizárólag az, hogy a rekurzió működésére rávilágítson, és mindehhez egyszerű példát adjon. A sztring előre- és hátrafelé történő kiírása olyan egyszerű, magától értetődő iteratív feladat, amelyet C-ben rekurzív módon megvalósítani pazarlás (a sok függvényhívás mind időbe telik).

void kiir(char *sztring) {
   while (*sztring!='\0') {
      putchar(*sztring);
      sztring+=1;
   }
}

void kiir(char *sztring) {
   if (*sztring=='\0')
      return;
   putchar(*sztring);
   kiir(sztring+1);
}

int fib(int n) {
   int eloz=1, f=0, kov, i;
   for (i=0; i<n; ++i) {
      kov=f+eloz;
      eloz=f; f=kov;
   }
   return f;
}

int fib(int n) {
   if (n<2)
      return n;
   else
      return fib(n-2)
             +fib(n-1);
}

Némely rekurzív függvények egészen egyszerűen átírhatók ciklusra. Ugyanis ha a rekurzív hívás után már nem csinál semmit a függvény, hanem egyből visszatér, az végeredményben csak egy ciklus. Az kiir() pont ilyen, ún. jobbrekurzív függvény. Itt az átalakítás a másik irányban látható; iteratív függvényből rekurzív lett.

Tétel: minden rekurzív probléma megoldható iteratívan is, és minden iteráció átalakítható rekurzióvá.

Szabályok. Rakjuk át a korongokat az elsőről a harmadik oszlopra!
Egyszerre csak egyet, és kicsire nagyot nem tehetünk.

Ötlet. Rakjunk félre n-1 korongot… Akkor az alsó korong mozgatható!
Na de arról volt szó, hogy egyszerre csak egy korong mozoghat…

Lényege: egy elemet vezérelemnek választva két részre osztjuk a tömböt: annál kisebbekre és nagyobbakra.
Ezután az így keletkező két részt rendezzük.

Lényege: a tömb két végéről indulnak indexek.
Megkeressük balról az első pirosat, jobbról kéket, és megcseréljük őket.
Ezt folytatjuk, amíg a két index nem találkozik.

void szetvalogat(int *tomb, int meret) {
   int bal=0, jobb=meret-1;
   
   while (bal<jobb) {
      while (bal<jobb && tomb[bal]==0)  // pirosat keresünk
         bal++;
      while (bal<jobb && tomb[jobb]==1) // kéket keresünk
         jobb--;
         
      if (bal<jobb) {
         int temp=tomb[bal];   // csere
         tomb[bal]=tomb[jobb];
         tomb[jobb]=temp;
         bal++; jobb--;        // egyből a következőkre
      }
   }
}

void gyorsrendez(double tomb[], int min, int max) {
   int i=min, j=max;
   double vezer=tomb[(min+max)/2]; // vezérelem: középső

   while (i<=j) {                  // piros/kék válogatás
      while (tomb[i]<vezer) i++;
      while (tomb[j]>vezer) j--;
      if (i<=j) {
         double tmp=tomb[i];
         tomb[i]=tomb[j];
         tomb[j]=tmp;
         i++; j--;
      }
   }

   if (min<j) gyorsrendez(tomb, min, j); // rekurzió
   if (i<max) gyorsrendez(tomb, i, max);
}

void gyorsrendez_indit(double tomb[], int meret)
{
   gyorsrendez(tomb, 0, meret-1);
}