Labor, 7. hét: rekurzió
Czirkos Zoltán, Pohl László · 2024.10.12.
Rekurzió vizsgálata nyomkövetővel. Rekurzív algoritmusok írása: báziskritérium és egyszerűsítések.
A feladatok nagy része a rekurzió témakörét dolgozza fel. Itt fontos az, hogy a nyomkövetővel mindenki megvizsgálja a rekurzió működését, különösen a Fibonacci számokat kiszámoló programnál. A tömb előre-hátra feladatokhoz az előadás sztringes példája adhat ötletet. Ennek kidolgozása pedig rávezet a számrendszer váltó feladat megoldására.
Felkészülés a laborra:
- A rekurzióról szóló előadás átismétlése.
A Fibonacci-sorozat elemeit a következő egyszerű algoritmus adja:
F0 = 0F1 = 1Fn = Fn-1 + Fn-2
Írj rekurzív függvényt, amely kiszámítja ennek n-edik elemét! Próbáld ki a függvényt n=45-re! Mit tapasztalsz? (Ötlet: figyeld meg az előadás ide vonatkozó diáját.)
Kövesd a függvény működését a fejlesztőkörnyezet nyomkövetőjében (debugger)! Indítsd el a
programot, és figyeld a működést n=5 esetén. Esetleg használhatsz a programba írt
nyomkövetést is: pl. minden fib() függvényhívás esetén írja ki a függvény a
paraméterként kapott n értéket.
Megoldás
#include <stdio.h>
/* Fibonacci sorozat */
int fib(int n) {
/* báziskritériumok */
if (n == 0) return 0; /* 0. elem a 0 */
if (n == 1) return 1; /* 1. elem az 1 */
/* egyszerűsítés */
return fib(n - 1) + fib(n - 2); /* n-edik elem az előző kettő összege */
}
int main(void) {
for (int i = 0; i < 45; i++)
printf("%d\n", fib(i));
return 0;
}Próbáld ki az alábbi két programot! Mi a különbség az alábbi két függvény között? Mi a különbség a futási eredményben?
#include <stdio.h>
void sztringet_kiir_1(char *szoveg) {
if (szoveg[0] == '\0')
return;
putchar(szoveg[0]);
printf("%s", szoveg + 1); // !
}
void sztringet_kiir_2(char *szoveg) {
if (szoveg[0] == '\0')
return;
putchar(szoveg[0]);
sztringet_kiir_2(szoveg + 1); // !
}
int main(void) {
sztringet_kiir_1("alma");
sztringet_kiir_2("alma");
return 0;
}Megoldás
A futási eredményben semmi. Mindkettő ugyanazt a feladatot oldja meg. A gondolatmenetük: a sztring kiírásához ki kell írni a sztring első karakterét, utána pedig a sztring fennmaradó részét. Például alma = a+lma. Az előbbi függvény a fennmaradó részt printf-fel írja ki, az utóbbi rekurzívan. Rekurzívan pedig, lma = l+ma, és így tovább, amíg el nem fogy a sztring.
Írj a) iteratív b) rekurzív függvényt, amely kiírja egy tömb elemeit x) előrefelé y) hátrafelé. Vegye át mindegyik függvény paraméterként a kiírandó tömböt és annak méretét! Hozz létre a főprogramban egy tíz és egy öt elemű, egész értékekkel feltöltött tömböt. Hívd meg a függvényeket a tömbökre!
Figyeld meg, pontosan mit kér a feladat: összesen négy, egymástól független függvényt kell írnod, hogy a két feladatot két-két verzióban megoldd.
Megoldás
#include <stdio.h>
/*Az iteratív függvények triviálisak*/
void tomb_kiir_elore(int t[], int n) {
if(n > 0) { /* Ha van benne elem */
printf("%d ", t[0]); /* Kiírjuk az első elemet */
tomb_kiir_elore(t+1, n-1); /* Meghívjuk ugyanezt a függvényt, csak a tömb következő */
/* elemétől kezdve és eggyel kisebb mérettel */
}
}
void tomb_kiir_hatra(int t[], int n) {
if(n > 0) { /* Ha van benne elem */
tomb_kiir_hatra(t+1, n-1); /* Meghívjuk ezt a függvényt, egyel kisebb méret */
printf("%d ", t[0]); /* Kiírjuk az első elemet */
}
}
int main(void) {
int t5[] = {1,2,3,4,5}, t10[] = {1,2,3,4,5,6,7,8,9,10};
tomb_kiir_elore(t5, 5); printf("\n");
tomb_kiir_hatra(t5, 5); printf("\n");
tomb_kiir_elore(t10, 10); printf("\n");
tomb_kiir_hatra(t10, 10); printf("\n");
return 0;
}Írj függvényt, amely paraméterként kap egy pozitív egész számot valamint egy számrendszert, és kiírja a képernyőre a számot a megadott számrendszerben! A megoldáshoz használj rekurziót! Miért sokkal egyszerűbb ez a megoldás, mint az iteratív?
Tipp
Ennek a feladatnak a megoldásához a fordított kiírás ad ötletet. Pl. a 123-at 10-es számrendszerben úgy kell kiírni, hogy előbb kiírjuk a 123/10-et (12), utána pedig a 123%10-et (3). A rekurzióval ez a fordított sorrend könnyen előállítható.
Megoldás
#include <stdio.h>
/* Ez a függvény r<=10 számrendszerekre működik */
void atvalt(int n, int r) {
/* Ha n nem osztható az alapszámmal, akkor rekurzívan meghívjuk a függvényt */
if (n / r > 0)
atvalt(n / r, r);
/* Majd kiírjuk a maradékot */
printf("%d", n % r);
}
/* Ez a teljes angol ABC-t fel tudja használni (36-os számrendszerig) */
void atvalt2(int n, int r) {
/* Ha n osztható az alapszámmal, akkor rekurzívan meghívjuk a függvényt */
if (n / r > 0)
atvalt2(n / r, r);
/* Majd kiírjuk a maradékot */
if (n % r < 10)
printf("%c", n % r + '0');
else
printf("%c", n % r - 10 + 'A');
}
int main(void) {
atvalt(27, 5); /* 102 */
printf("\n");
atvalt(13, 2); /* 1101 */
printf("\n");
atvalt2(64519, 16); /* FC07 */
return 0;
}Írj függvényt, amely a paraméterként kapott pozitív egész számot három számjegyenként csoportosított formában írja ki. Pl.: 16 077 216. Próbáld ki más számokra is: 999, 1000, 12, 0, 1000222!
Tipp
Használj rekurziót! Ez olyan, mintha ezres számrendszerben írnál ki.
Megoldás
#include <stdio.h>
void kiir(int n) {
/* ha nincs 3 számjegyű, simán kiírjuk, nincs több teendő */
if (n < 1000) {
printf("%d", n);
return;
}
/* amúgy alsó 3 számjegyet eldobva, előbb kiírjuk az elejét. */
/* utána pedig az alsó 3 számjegyet, vezető nullákal */
kiir(n / 1000);
printf(" %03d", n % 1000);
}
int main(void) {
kiir(16077216);
return 0;
}