Fibonacci számsor: olyan sorozat, amelynek minden eleme az őt megelőző két elem összege. Hogy ne a végtelenségig hivatkozzunk az előző elemekre, az első kettőt külön meg kell adni, vagyis:
- Fib0=0,
- Fib1=1, és
- Fibn=Fibn-1+Fibn-2.
Ez egy rekurzív definíció – a sorozat n. elemét önmagát felhasználva, az n-1. és n-2. elem segítségével definiáljuk. C-ben a verem miatt lehetőség van arra, hogy egy függvény meghívja saját magát. Ez a rekurzió. A rekurzió mélységében az egyes hívásokhoz tartozó paraméterek és lokális változók egymástól függetlenek.
A rekurzió lényege, hogy a megoldandó problémát saját magára vezetjük vissza, egy egyszerűbb részfeladatra.
#include <stdio.h>
/* a Fibonacci feladat rekurziv megoldasa. */
int fib(int n) {
if (n<2)
return n;
else
return fib(n-2)+fib(n-1);
}
/* az iterativ megoldas */
int fib_it(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 main(void) {
int i;
for (i=0; i<40; i++) {
printf("%d ", fib(i));
fflush(stdout); /* ezt azert, hogy egybol megjelenjen */
}
printf("\n");
for (i=0; i<40; i++) {
printf("%d ", fib_it(i));
fflush(stdout);
}
printf("\n");
return 0;
}Minden rekurzív problémának létezik iteratív megoldása is; amely azonban sokszor nem olyan triviális, mint a fenti. Ebben az esetben a rekurzív megoldás szép, de haszontalan, mert nagyon lassú tud lenni. Pl. a 4. fibonacci számhoz a függvény kiszámolja a 2.-at és a 3.-at. A 3. számhoz pedig kiszámolja a 1.-t és a 2.-at; nem véve figyelembe, hogy a 2-es már egyszer ki lett számolva.
Egyik legegyszerűbb rendező algoritmus a kiválasztásos rendezés. Lényege az ábrán látható.
- Megkeressük a legkisebb elemet a tömbből.
- Megcseréljük azt a tömb legelső elemével.
- Innentől kezdve a tömb első eleme a legkisebb; ahhoz már nem kell nyúlni.
- Tekintjük a tömböt a második elemétől a végéig, és megcsináljuk rá ugyanezt.
- Az első két elem a helyén van.
- Tekintjük a tömböt a harmadik elemtől a végéig stb.
A példaprogram feltölt egy tömböt véletlenszámokkal, rendezi és végül kiírja őket növekvő sorrendben. Szándékosan mindent külön függvénybe írtam; sőt, a főprogramban dinamikus memóriakezelést használok (a függvények egyébként nem tudják, hogy dinamikus memóriáról van-e szó). Ezek természetesen nem részei az algoritmusnak, hanem csakis az első függvény.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* KIVALASZTASOS RENDEZES - EZ ITT A FENTI ALGORITMUS */
void rendez(int *tomb, int meret) {
int i, j;
for (i=0; i<meret-1; ++i) {
int temp;
int minindex=i; /* ez a legkisebb :) */
/* vagy megis van kisebb? */
for (j=i+1; j<meret; ++j)
if (tomb[j]<tomb[minindex])
minindex=j;
/* csere 3 lepesben */
temp=tomb[minindex];
tomb[minindex]=tomb[i];
tomb[i]=temp;
}
}
/* randommal feltolt */
void feltolt(int *tomb, int meret) {
int i;
for (i=0; i<meret; ++i)
tomb[i]=rand()%100;
}
/* kiirja mindet */
void kiir(int *tomb, int meret) {
int i;
for (i=0; i<meret; ++i)
printf("%5d", tomb[i]);
}
int main(void) {
int *t;
int meret;
srand(time(0));
printf("meret? "); scanf("%d", &meret);
t=(int *) malloc(sizeof(int)*meret);
feltolt(t, meret);
rendez(t, meret);
kiir(t, meret);
free(t);
return 0;
}A buborékrendezés egymás melletti elemeket cserél:
- Hasonlítsuk össze az első két elemet. Ha nincsenek jó sorrendben, cseréljük meg.
- Hasonlítsuk össze a második párt (második és harmadik elem). Esetleg csere.
- Folytassuk így a tömb végéig.
- Így, ha a legnagyobb elem a tömb elején is volt akár, akkor a végére került: azzal már a végleges helye.
- Csináljuk meg ugyanezt még egyszer, a tömb elejétől az utolsó előttiig. Az utolsóhoz már nem nyúlunk.
- Aztán ugyanezt megint, de az utolsó kettőhöz már nem nyúlunk stb.
A buborékrendezés hatékonysága javítható azzal, ha megjegyezzük, hogy a vizsgált tömbrészletnél volt-e csere. Ha nem volt, akkor minden pár jó sorrendben van. Akkor a rövidebb részt vizsgálva ugyanerre az eredményre fogunk jutni, vagyis a külső ciklust már nem kell folytatni.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void buborek(int *tomb, int meret) {
int i, j;
/* egyre kisebb tombbel dolgozunk */
for (j=meret-1; j>0; j--) {
int voltcsere;
voltcsere=0;
/* belso ciklus, egymas mellettieket nezi */
for (i=0; i<j; i++)
/* ha az egymas mellettiek nem jok, csere */
if (tomb[i]>tomb[i+1]) {
int temp=tomb[i];
tomb[i]=tomb[i+1];
tomb[i+1]=temp;
/* jegyezzuk meg, hogy volt dolgunk */
voltcsere=1;
}
/* ha sehol nem csereltunk meg elemet, akkor
* le lehet loni a ciklust */
if (!voltcsere)
break;
}
}
#define MERET 15
int main(void) {
int tomb[MERET];
int i;
/* veletlen elemek */
srand(time(0));
for (i=0; i<MERET; i++)
tomb[i]=rand()%100;
/* rendezes es kiiras */
buborek(tomb, MERET);
for (i=0; i<MERET; i++)
printf("%d ", tomb[i]);
printf("\n");
return 0;
}
A fenti kódban a break utasítás egy kulturált használata látható.
A két egymásba ágyazott ciklus a buborékrendezés; for (j...j--)
az egyre rövidebb részletek ciklusa, és for (i...i++) az egymás
melletti párok ciklusa. Ezeknek a feltételeibe nem írjuk bele a „volt-e csere”
feltételt. Helyette ha egy tömbrészlet vizsgálata után kiderül, hogy nem volt csere,
akkor megszakítjuk a ciklust. Érezhető, hogy ez egy különleges körülmény,
ami menet közben derül ki, és nem kapcsolódik semmilyen módon az
„egyre rövidebb részletek” gondolathoz.