Tétel

2 pont jár hivatalból. Munkaidő: 45 perc.

1.

Milyen értékeket térítenek vissza az f(15,20), f(2,10), f(1000,1), f(1000000, 57) hívások az alábbi f függvény esetén? Az első kettőt kövessük nyomon, a másik kettőnél indokoljuk, hogy miért! – 4 x 0.5p

1
2
3
4
5
6

int f(int a, int b) 
{ 
    if (a == b) return a; 
    else if (a > b) return f(a-b, b); 
    else return f(a, b-a); 
}

Megoldás:

    f(15, 20) = f(15, 5) = f(10, 5) = f(5, 5) = 5
    f(2, 10) = f(2, 8) = f(2, 6) = f(2, 4) = f(2, 2) = 2

A függvény a két argumentum legnagyobb közös osztóját téríti vissza (euklideszik algoritmus), tehát:

    f(1000, 1) = 1
    f(1000000, 57) = 1

2.

Mit írnak ki és mi a visszatérített értéke az g(3), illetve g(1) hívásoknak? Kövessük nyomon! – 1p

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

int g(int n) 
{ 
    cout << "a"; 

    int k; 
    if (n <= 10) k = g(n+3); 
    else k = n; 

    cout << "b";
 
    return k; 
    cout << "c"; 
}

Megoldás:

    g(3)
    |    cout << "a"
    |    k = g(6)
    |        |    cout << "a"
    |        |    k = g(9)
    |        |        |    cout << "a"
    |        |        |    k = g(12)
    |        |        |        |    cout << "a"
    |        |        |        |    k = 12
    |        |        |        |    cout << "b"
    |        |        |        |    return 12
    |        |        |        []
    |        |        |    k = 12
    |        |        |    cout << "b"
    |        |        |    return 12
    |        |        []
    |        |    k = 12
    |        |    cout << "b"
    |        |    return 12
    |        []
    |    k = 12
    |    cout << "b"
    |    return 12
    []
    
    Kimenet: aaaabbbb
    Visszatérített érték: 12

    g(1)
    |    cout << "a"
    |    k = g(4)
    |        |    cout << "a"
    |        |    k = g(7)
    |        |        |    cout << "a"
    |        |        |    k = g(10)
    |        |        |        |    cout << "a"
    |        |        |        |    k = g(13)
    |        |        |        |        |    cout << "a"
    |        |        |        |        |    k = 13
    |        |        |        |        |    cout << "b"
    |        |        |        |        |    return 13
    |        |        |        |        []
    |        |        |        |    k = 13
    |        |        |        |    cout << "b"
    |        |        |        |    return 13
    |        |        |        []
    |        |        |    k = 13
    |        |        |    cout << "b"
    |        |        |    return 13
    |        |        []
    |        |    k = 13
    |        |    cout << "b"
    |        |    return 13
    |        []
    |    k = 13
    |    cout << "b"
    |    return 13
    []
    
    Kimenet: aaaaabbbbb
    Visszatérített érték: 13

3.

Kövessük nyomon a kiir(5) hívást! Mi kerül a képernyőre? – 1p

1
2
3
4
5
6
7

void kiir(int n) { 
    cout << n << " ";
    if (n != 0) {
        kiir(n-1); 
        cout << n << " ";
    }
}

Megoldás:

    KIMENET:  5 4 3 2 1 0 1 2 3 4 5

    kiir(5)
    |    cout << 5
    |    kiir(4)
    |    |    cout << 4
    |    |    kiir(3)
    |    |    |    cout << 3
    |    |    |    kiir(2)
    |    |    |    |    cout << 2
    |    |    |    |    kiir(1)
    |    |    |    |    |    cout << 1
    |    |    |    |    |    kiir(0)
    |    |    |    |    |    |    cout << 0
    |    |    |    |    |    []
    |    |    |    |    |    cout << 1
    |    |    |    |    []
    |    |    |    |    cout << 2
    |    |    |    []
    |    |    |    cout << 3 
    |    |    []
    |    |    cout << 4
    |    []
    |    cout << 5
    []

4.

Adott egy n elemű sorozat, határozzuk meg a páros elemeinek összegét rekurzívan két különböző megoldással: utolsó elem leválasztása, illetve kettévágva a tömböt (divide et impera)! Az alábbi függvényeket kell megírni: – 2x1p

    int sum_paros_rek(int n, int t[]);
    int sum_paros_divimp(int t[], int bal, int jobb);

(Az utóbbi esetén sum_paros_divimp(t, 0, n-1), lenne kezdetben a hívás, ahol n az elemek száma.)

Megoldás:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int sum_paros_rek(int n, int t[]){
    if(n==0){
        return 0;
    }
    if(t[n-1]%2 == 0){
        return t[n-1] + sum_paros_rek(n-1, t);
    }
    return sum_paros_rek(n-1, t);
}

int sum_paros_divimp(int t[], int bal, int jobb){
    if(bal>jobb) return 0;
    if(bal==jobb) {
        if(t[bal] % 2 == 0)
            return t[bal];
        else 
            return 0;
    }
    
    int kozep = (bal+jobb)/2;
    int bal_osszeg = sum_paros_divimp(t,bal,kozep);
    int jobb_osszeg = sum_paros_divimp(t,kozep+1,jobb);
    return jobb_osszeg + bal_osszeg;
}

5.

Adott egy természetes szám. Adjuk meg a legnagyobb számjegyét rekurzívan kétféleképpen: egyszer visszatérített érték legyen, aztán pedig egy második paraméteren keresztül visszaküldött érték! Teljes programot kell írni a két függvénnyel, a main hívja meg mindkettőt a felhasználó által beírt értékre. – 2x1p

Megoldás:

 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

#include <iostream>
using namespace std;

int legnagyobb1(int n)
{
    if (n < 10)
        return n;

    int eddig = legnagyobb1(n/10);
    if (n%10 > eddig)
        return n % 10;
    else
        return eddig;
}

void legnagyobb2(int n, int &eredmeny)
{
    if (n < 10) {
        eredmeny = n;
    }
    else {
        legnagyobb2(n/10, eredmeny);
        if (n%10 > eredmeny)
            eredmeny = n % 10;
    }
}

int main()
{
    int n;
    cin >> n;

    cout << legnagyobb1(n) << endl;

    int szj;
    legnagyobb2(n, szj);
    cout << szj << endl;

    return 0;
}