Rekurzíó - feladatok

1.

Bináris keresés rekurzívan: adott egy tömb és egy keresendő elem; Adjunk meg egy pozíciót, ahol ez megjelenik, vagy -1-et, ha nincs a tömbben.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <iostream>
using namespace std;

// keresi egy érték pozícióját a
// t[a] t[a+1] ... t[b-1] t[b] tartományban
// t növekvő
int kereses(int t[], int a, int b, int ertek)
{
    if (a > b)
        return -1;

    int kozep = (a + b) / 2;

    if (t[kozep] == ertek)
        return kozep;
    else if (t[kozep] < ertek)
        return kereses(t, kozep+1, b, ertek);
    else
        return kereses(t, a, kozep-1, ertek);

}


// rekurzív szekvenciális keresés
int nonbinary_search(int t[], int n, int ertek)
{
    if (t[n] == ertek)
        return n;

    return nonbinary_search(t, n-1, ertek);
}


int main()
{
    int t[] = {1,3,5,7,8};

    cout << kereses(t, 0, 4, 7) << endl; // 3
    cout << nonbinary_search(t, 5, 7) << endl; // 3

    return 0;
}

2.

https://www.pbinfo.ro/probleme/821/cmmdcrec
Legnagyobb közös osztót kell meghatározni rekurzívan.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
using namespace std;

int lnko(int a, int b)
{
    if (b == 0)
        return a;

    return lnko(b, a%b);
}


int main()
{
    cout << lnko(11,12) << endl; // 1
    cout << lnko(12,20) << endl; // 4
    cout << lnko(3,96) << endl; // 3
    return 0;
}

3.

https://www.pbinfo.ro/probleme/4207/sumprodrec
Rekurzív függvényt kell írni, ami adott n-re kiszámolja az 1*2 + 2*3 + … + (n-1)*n összeget.

1
2
3
4
5
6
7

long long SumProdRec(int n)
{
    if (n == 2)
        return 1*2;
    else
        return SumProdRec(n-1) + (n-1)*n;
}

4.

https://www.pbinfo.ro/probleme/822/nrcifrezerorec
Meg kell határozni rekurzívan, hogy egy számnak hány nullás számjegye van.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int nr_cif_zero(int n)
{
    if (n < 10) {
    	if (n == 0)
            return 1;
        else
            return 0;
    }
    else {
        int db = nr_cif_zero(n/10);
        
        if (n % 10 == 0) {
        	db++;
        }
        
        return db;
    }
}

5.

https://www.pbinfo.ro/probleme/1862/cntcifkrec
Rekurzív függvényt kell írni az n,k,c paraméterekkel, mely a c-n keresztül visszaküldi, hogy n-nek hány k-nál nagyobb vagy egyenlő számjegye van.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void cnt_cif(int n, int k, int &c)
{
    if (n < 10) {
        c = 0;
    }
    else {
        cnt_cif(n/10, k, c);
    }

    if (n%10 >= k)
        c++;
}

6.

https://www.pbinfo.ro/probleme/4208/existaimparerec
Rekurzív függvényt kell írni, ami adott paraméterre 1-et térít vissza, ha annak van legylább egy páratlan számjegye, illetve 0-t ha nincs.

1
2
3
4
5
6
7
8
9

int ExistaImpareRec(int n)
{
    if (n%2 == 1)
        return 1;
    else if (n == 0)
        return 0;
    else
        return ExistaImpareRec(n/10);
}

A párosakat megszámolni nehezebb (a 0 miatt:)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int ExistaPareRec(int n)
{
    if (n < 10) {
        if (n%2 == 0)
            return 1;
        else
            return 0;
    }
    else if (n%2 == 0)
        return 1;
    else
        return ExistaPareRec(n/10);
}

VAGY:

1
2
3
4
5
6
7
8
9

int ExistaPareRec(int n)
{
    if (n%2 == 0)
        return 1;
    else if (n < 10)
        return 0;
    else
        return ExistaPareRec(n/10);
}

7.

https://www.pbinfo.ro/probleme/926/fsumdiv3rec
Kell egy rekurzív függvény, ami kap egy tömböt és annak elemszámát, majd visszatéríti a 3-mal osztható elemek összegét.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int sum3(int v[], int n)
{
    if (n == 0)
        return 0;

    int s = sum3(v, n-1);

    if (v[n-1] % 3 == 0)
        s += v[n-1];

    return s;
}

8.

https://www.pbinfo.ro/probleme/916/factorialrec1
Egy factorial nevű rekurzív függvényt kell írni n és f paraméterekkel, amely f-en keresztül visszaküldi n faktoriálisát.

1
2
3
4
5
6
7
8
9

void factorial(int n, int &f)
{
    if (n == 0)
        f = 1;
    else {
        factorial(n-1, f);
        f = f * n;
    }
}

9.

https://www.pbinfo.ro/probleme/4206/cifdiv3rec
Rekurzív függvényt kell írni, ami egy paraméterként kapott szám 3-mal osztható számjegyeinek számát téríti vissza.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int CifDiv3Rec(int n){
    if (n < 10) {
    	if (n % 3 == 0)
            return 1;
        else
            return 0;
    }
    else {
    	int db = CifDiv3Rec(n/10);
        
        if ((n%10) % 3 == 0)
        	return db + 1;
        else
            return db;
    }
}

10.

https://www.pbinfo.ro/probleme/4210/fcrescrec
Rekurzív függvényt kell írni, ami 1-et vagy 0-t térít vissza annak függvényében, hogy a paraméterként kapott számban jobbról balra haladva növekvő sorrendben vannak-e a számjegyek.

HF!

11.

https://www.pbinfo.ro/probleme/4537/cifegalerec
Rekurzív függvényt kell írni két (n és k) paraméterrel, ami 1-et vagy 0-t térít vissza annak függvényében, hogy az n minden számjegye egyenlő-e k-val.

HF!

12.

https://www.pbinfo.ro/probleme/4209/difparimpar
Rekurzív függvényt kell írni, ami adott n paraméterre visszatéríti az n páros és páratlan számjegyei összegének különbségét (párosak összege - páratlanok összege).

13.

https://www.pbinfo.ro/probleme/1842/crearenumarrec
Rekurzív függvényt kell írni, amely adott n, a, k paraméterekre visszaküldi a k paraméteren keresztül azt a számot, ami az n elemű a tömbben levő páros számjegyekből áll ezek megjelenésének sorrendjében.

14.

https://www.pbinfo.ro/probleme/920/cifmaxminrec
Rekurzív függvényt kell írni, ami adott n szám esetén két másik paraméteren keresztül visszaküldi ennek legnagyobb és legkisebb számjegyét.

15.

https://www.pbinfo.ro/probleme/834/elimcifrec
Rekurzív függvényt kell írni, ami adott n és c paraméterekre visszatéríti azt a számot, amit n-ből kapunk, ha a c-vel egyenlő számjegyeit elhagyjuk.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int elimcif(int n, int c)
{
    if (n == 0)
        return 0;

    int resz = elimcif(n/10, c);

    if (n%10 == c)
        return resz;
    else
        return resz*10 + n%10;
}

16.

https://www.pbinfo.ro/probleme/4211/elimztrec
Adott n paraméterre egy rekurzív függvény térítse vissza azt a számot, amit az n végén levő nulla számjegyek elhagyásával kapunk.

1
2
3
4
5
6
7
8
9

int ElimZTRec(int n)
{
    if (n == 0)
        return 0;
    else if (n%10 != 0)
        return n;
    else
        return ElimZTRec(n/10);
}

17.

https://www.pbinfo.ro/probleme/1863/numararerec
Rekurzív függvényt kell írni, amely adott v tömb és n elemszám esetén visszatéríti azt, hogy hány egymás melletti elemekből álló pár van a v-ben, amiben a számok egyenlőek.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int numarare(int v[], int n)
{
    if (n < 2)
        return 0;

    int resz = numarare(v, n-1);

    if (v[n-1] == v[n-2])
        return resz+1;
    else
        return resz;
}