Rekurzió
Feldatok:
I. Írjunk rekurzív függvényt,
mely
meghatározza
1. egy adott n egész szám
faktoriális értékét. (
Forráskód
)
2. két szám legnagyobb közös
osztóját
3. x^n hatvány értékét,
gyorshatványozási módszerrel
4. az n ik Fibonacci szám
értékét (hatványozással)
5. egy szám számjegyeinek összegét (
Forráskód )
6. egy szám számjegyeinek szorzatát
7. egy szám számjegyei közül a maximumot
II. Írjunk rekurzív függvényt mely
1. egy egész elemű tömb
elemeit kiírja fordított sorrendbe a képernyőre
2. meghatározza egy egész elemű tömb elemeinek az
összegét
3. meghatározza egy egész elemű tömb elemei
közül a maximumot (
Forráskód
)
4. meghatározza, hogy hány páros szám van
egy egész elemű tömbben
5. meghatározza, hogy hány prímszám van
egy egész elemű tömbben
III.. Írjunk rekurzív függvényt mely
bináris kereséssel meghatározza, egy elem, adott
tömbbeli előfordulási pozícióját, ahol
a tömb elemei rendezve vannak.
IV. Írjunk rekurzív függvényt mely
meghatározza a Pascal féle háromszög egy
adott sorát.
Példa:. ha n=6, akkor 1, 5, 10,
10, 5, 1, ahol a háromszög a következő:
1
1 1
1 2 1
1 3 3 1
1 4 6
4 1
1 5 10
10 5 1
Majd ezt a függvényt
felhasználva határozzuk meg 2n
értékét, illetve n elem k-ad rendű
kombinációját.
I. 1. feladat
A feladat megoldása
háromféleképpen a fakt1, fakt2, fakt3
függvényekben.
#include
<stdio.h>
#include
<stdlib.h>
int
fakt1(int szam);
int
fakt2(int szam, int osz);
void
fakt3(int szam, int *osz);
main()
{
int szam = 5;
int m;
m = fakt1(szam);
printf("Faktorialis: %i\n", m);
m = fakt2(szam, 1);
printf("Osszeg: %i\n", m);
// a cím szerinti
paraméter átadás miatt a függvény
második argumentuma egy
//
memória cím (pointer) típusú
változó kell legyen
m = 1;
fakt3(szam, &m);
printf("Osszeg: %i\n", m);
return 0;
}
// a függvény
visszatérítési értékében
számoljuk ki az összeget
int fakt1(int
n)
int fakt1(int
n)
{
{
int t;
if(n ==0) retunr 1;
if (n == 0) return 1;
return n * fakt1(n-1);
t = fakt1(n-1);
}
return n * t;
}
// az ered változóban,
azaz a rekurzív függvény második
argumentumában számoljuk az
// összeget, majd ez fogja képezni a függvény
visszatérítési értékét
int
fakt2(int n, int ered)
{
if (n==0) return ered;
return fakt2(n-1,
n*ered);
}
// az ered változóban,
azaz a rekurzív függvény második
argumentumában számoljuk az
// összeget, melyet cím szerinti paraméter
átadást alaklmazva, tudjuk megváltoztatni
void
fakt3(int n, int *ered)
{
if (n<=0) return;
(*ered) = n * (*ered);
fakt3(n-1, ered);
}
Vissza
I. 5. feladat
A feladat megoldása
háromféleképpen az szj1, szj2, szj3
függvényekben.
#include
<stdio.h>
#include
<stdlib.h>
int
szj1(int szam);
int
szj2(int szam, int osz);
void
szj3(int szam, int *osz);
main()
{
int szam = 12345;
int m;
m = szj1(szam);
printf("Osszeg: %i\n", m);
m = szj2(szam, 0);
printf("Osszeg: %i\n", m);
m = 0;
szj3(szam, &m);
printf("Osszeg: %i\n", m);
return 0;
}
int
szj1(int
szam)
int szj1(int
szam)
{
{
int t;
if
(szam<=0) return 0;
if (szam<=0) return 0;
return
(szam%10) + szj1(szam/10);
t = sz1(szam/10);
}
return (szam%10) + t;
}
int szj2(int szam, int osz)
{
if (szam<=0) return osz;
return szj2(szam/10,
osz+szam%10);
}
void szj3(int szam, int *osz)
{
if (szam<=0) return;
(*osz) = szam%10 + (*osz);
szj3(szam/10, osz);
}
Vissza
II. 3. feladat
A feladat megoldása háromféleképpen az mmax1, mmax2, mmax3
függvényekben.
#include
<stdio.h>
#include
<stdlib.h>
int
mmax1(int t[], int n);
int
mmax2(int t[], int n, int m);
void
mmax3(int t[], int n, int *m);
main()
{
int t [] = {1034,6,912,356,11,8,99};
int n = sizeof(t)/sizeof(t[0]);
int m;
m = mmax1 (t,n-1);
printf("Maximum: %i\n", m);
m = mmax2 (t, n-1, t[0]);
printf("Maximum: %i\n", m);
// a
cím szerinti paraméter átadás miatt a
függvény harmadik argumentuma egy
//memória cím (pointer) típusú
változó kell legyen
m = t[0];
mmax3 (t, n-1, &m);
printf("Maximum: %i\n", m);
return 0;
}
// a maximum
kiválasztása akkor történik amikor a
rekurzív hívásokból lépünk
visszafele
int mmax1(int t[], int n)
{
int m;
if (n == 0) return t[0];
m = mmax1(t, n-1);
if (m < t[n]) return t[n];
else return m;
}
// a maximum
kiválasztása a rekurzív hívás előtt
történik és aszerint változik a
rekurzív // függvény paramétere hogy melyik
az aktuálisan nagyobb elem. A maximum értéket a
return // parancson keresztül térítem vissza
int mmax2(int t[], int n, int m)
{
if (n == 0) return m;
if (m < t[n]) return mmax2(t,
n, t[n]);
else return mmax2(t, n,
m);
}
// a
maximum kiválasztása a rekurzív
hívás előtt történik és aszerint
változik a rekurzív // függvény
paramétere hogy melyik az aktuálisan
nagyobb elem. A maximum érték cím
// szerinti paraméter átadás
segítségével változik meg
void mmax3(int t[], int n, int *m)
{
if (n == 0) return;
if ((*m) < t[n]) (*m) = t[n];
mmax3(t, n, m);
}
Vissza