Tétel

3 pont jár hivatalból, a 8 pontból 7-et kell még elérni.

1.

A bemeneten adott az n természetes szám, majd n darab egyjegyű pozitív egész.

Olvassuk be az elemeket, építsünk frekvenciatömböt! (1 pont)
Írjuk ki, hogy hány olyan érték van, ami kevesebb, mint háromszor jelenik meg a sorozatban! (0.5 pont)
Írjuk ki, hogy melyik az az érték, ami a legtöbbször jelenik meg! (0.5 pont)

Példa:

    bemenet: 9
             1 1 2 2 2 1 2 2 3
    kimenet: 1 2

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
#include <iostream>
using namespace std;

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

    int f[10] = {}; // 0, 0, 0, ...

    // a)
    for (int i = 0; i < n; i++) {
        int szam;
        cin >> szam;
        f[szam]++;
    }

    // b)
    int db = 0;
    for (int i = 0; i <= 9; i++)
        if (f[i] != 0 && f[i] < 3)
            db++;
    cout << db << " ";

    // c)
    int max_f = -1;
    int max_elem;

    for (int i = 0; i <= 9; i++)
        if (f[i] > max_f) {
            max_f = f[i];
            max_elem = i;
        }
    cout << max_elem << endl;

    return 0;
}

2.

Adott az n természetes szám, majd egy n elemű sorozat.

Írjuk ki az elemeit csökkenő sorrendben! (0.5 pont)
Cseréljünk le minden elemet a 100-zal való osztási maradékára, majd írjuk ki a tömböt növekvő sorrendben! (0.5 pont)

Példa:

    bemenet: 3
             101 25 318
    kimenet: 318 101 25
             1 18 25

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
41
42
#include <iostream>
using namespace std;

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

    int t[1000];

    for (int i = 0; i < n; i++)
        cin >> t[i];

    // b)
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (t[i] < t[j]) {
                int seged = t[i];
                t[i] = t[j];
                t[j] = seged;
            }
    for (int i = 0; i < n; i++)
        cout << t[i] << " ";
    cout << endl;

    // c)
    for (int i = 0; i < n; i++)
        t[i] = t[i] % 100;

    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (t[i] > t[j]) {
                int seged = t[i];
                t[i] = t[j];
                t[j] = seged;
            }
    for (int i = 0; i < n; i++)
        cout << t[i] << " ";
    cout << endl;

    return 0;
}

3.

Adottak az (1, 2, 5, 5, 6, 15, 23, 48, 56) növekvő és (32, 8, 7, 5, 3, 3, 2) csökkenő sorozatok.

Írjuk le azon összehasonlításokat, amelyek a két sorozat növekvő sorrendbe történő összefésülése során megtörténnek, illetve adjuk meg a rendezett sorozatot. (1 pont)
Írjuk le azon összehasonlításokat, amelyek a két sorozat csökkenő sorrendbe történő összefésülése során megtörténnek, illetve adjuk meg a rendezett sorozatot. (1 pont)

Megoldás

a)
Az első sorozatot balról jobbra, a másodikat jobbról balra járjuk be. A következő elempárok lesznek összehasonlítva (ha egyenlőség esetén a bal oldali sorozatból vesszük az elemet):

Az eredmény: 1, 2, 2, 3, 3, 5, 5, 5, 6, 7, 8, 15, 23, 32, 48, 56.

b)
Az első sorozatot jobbról balra, a másodikat balról jobbra járjuk be. A következő elempárok lesznek összehasonlítva (ha egyenlőség esetén a bal oldali sorozatból vesszük az elemet):

Az eredmény: 56, 48, 32, 23, 15, 8, 7, 6, 5, 5, 5, 3, 3, 2, 2, 1.

4.

Adott az (50, 220, 340, 500, 662, 1023, 50000) növekvő sorozat.

Írjuk le azon összehasonlításokat, melyek az x = 22 szám megkeresésekor megtörténnek ha a bináris keresés algoritmusát alkalmazzuk! (1 pont)
Adjunk meg x azon értékeit, amelyeket ha bináris kereséssel megkeresnénk a tömbben, háromnál kevesebb összehasonlítás történne! (1 pont)

Megoldás

a)
Az alábbi összehasonlítások történnek:

    22 ? 500
    22 ? 220
    22 ? 50

b)
Ha x nincs a tömbben, akkor 3 összehasonlítás történik, tehát mindenképp a tömb valamely elemeit keressük. Ilyen elemek a 220, 500, 1023 (a többire 3-3 összehasonlítás lesz).

5.

Hány olyan (x,y) természetes számokból álló elempár létezik, amelyek esetén az (5, x, 10, y, 20, 30, 40) tömbben a 7-es és 15-ös számok bináris kereséssel történő megkeresése 3-3 összehasonlítást végez? Indokoljuk! (1 pont)

Megoldás:

Mivel bináris keresést alkalmazunk, a tömb növekvő kell legyen, tehát 5 ≤ x ≤ 10 és 10 ≤ y ≤ 20. Továbbá x nem lehet 7 (mert akkor a 7-est két összehasonlításból megtalálnánk) és y nem lehet 15 (mert akkor a 15-öt egyetlen összehasonlításból találnánk meg). Minden más számpár jó (x eleme az {5, 6, 8, 9, 10} halmaznak, y pedig a {10, 11, 12, 13, 14, 16, 17, 18, 19, 20} halmaznak).

Ilyen x és y értékekből összesen 5 x 10 = 50 darab számpárt alkothatunk.