Hányféleképpen lehet egy adott hosszúságú járdát kikövezni 1 és 2 méter hosszúságú járdalapokkal? Például ha 3 méteres a járda, a lehetőségek: 1+1+1, 1+2, 2+1, tehát összesen 3.
Megoldás
A megoldás alapötlete a következő. Kétféle járdalapunk van (az 1 és a 2 méter hosszú), ami azt jelenti, hogy induláskor két lehetőségünk van: vagy egy 1 méteressel, vagy egy 2 méteressel kezdünk. Ha összesen 10 métert kell haladni, az első esetben már csak 9, a második esetben pedig már csak 8 métert kell majd haladnunk.
A 9 méteres és a 8 méteres szakasz kövezése is megoldható valahányféleképpen. A 10 méter hosszú járdához a megoldások számát a kettő összege fogja adni.
A rekurzióban az egyszerűsítési lépést így ez a kódrészlet adja:
int jarda(int hossz) {
/* ... */
return jarda(hossz - 1) + jarda(hossz - 2);
}Már csak alkalmas báziskritériumok kellenek. A függvény egyre kisebb számokkal fogja
meghívni magát (a hossz - 1 és a hossz - 2). Írjuk fel báziskritériumként
azokat az eseteket, amelyeket már nem lehetne tovább egyszerűsíteni, mivel nulla vagy negatív hossz
keletkezne a hívásban! Ezek:
- 1 hosszúságú járdát egyféleképpen tudunk kirakni (1 méteres lappal), illetve
- 2 hosszúságú járdát pedig kétféleképpen (2 méteres és 1+1 méteres lapokkal).
A megoldás:
#include <stdio.h>
/**
* Visszaadja, hányféleképpen lehet lekövezni egy
* <hossz> méret hosszú járdát 1 és 2 méteres kövekkel.
*/
int jarda(int hossz) {
if (hossz == 1)
return 1; /* 1 */
if (hossz == 2)
return 2; /* 1+1 és 2 */
return jarda(hossz - 1) + jarda(hossz - 2);
}
int main() {
int h;
printf("Hossz?\n");
scanf("%d", &h);
printf("%d lehetőség.\n", jarda(h));
}A báziskritériumok meghatározásakor másképp is gondolkodhatunk. A jelenlegi megoldás nem túl általános, mivel ezek a báziskritériumok függenek az egyszerűsítési lépésektől is (a lapok hosszától). Helyettük vehetjük báziskritériumnak azokat az eseteket, amikor az egyszerűsítés ténylegesen 0 értékű, vagy akár negatív hosszhoz jut:
- Ha 0 hosszúságú járdánk van, az egy (vigyázat, nem nulla!) módon kövezhető csak: úgy, hogy nem csinálunk semmit.
- A fenti függvény láthatóan meghívja magát negatív hosszakra is, negatív hosszúságú járda viszont nem létezhet, ezért olyankor 0 megoldás van.
A feladatnak ez is jó megoldása:
int jarda(int hossz) {
if (hossz < 0)
return 0; /* lehetetlen */
if (hossz == 0)
return 1; /* nem csinálunk semmit */
return jarda(hossz - 1) + jarda(hossz - 2);
}Ez azért is jobb, mert a lapok hosszai most csak az egyszerűsítési lépésben szerepelnek. Így akár vehetnénk azokat tömbből is, vagy megadhatná azt akár a felhasználó is, futási időben.
Hogyan kell módosítani a programot, ha 3 egység hosszú lapunk is van?
Hogyan, ha paraméterként kapjuk, hogy hányféle lap van? (Pl. 5 → 1, 2, 3, 4, 5 hosszú lapok vannak.)
Megoldás
A lényeg: mindig összegezni kell a lehetséges megoldásokat. A báziskritériumok változatlanok, ha negatívra és nullára építettük őket:
int jarda(int hossz, int hanyfele) {
if (hossz < 0)
return 0;
if (hossz == 0)
return 1;
int osszeg = 0;
for (int i = 1; i <= hanyfele; ++i)
osszeg += jarda(hossz - i, hanyfele);
return osszeg;
}