A frekvenciatömb egy olyan tömb, aminek az i indexű eleme azt mondja meg, hogy az i érték hányszor fordult elő (a bemeneten).

Pl. Adott egy sorozat 10-nél nem nagyobb term. számokból. Számoljuk meg és írjuk ki, hogy melyik érték hányszor fordult elő!

Megoldás “kézzel”:

    12
    0 1 2 0 1 5 2 1 6 9 1 2

    frekv[i] == hányszor láttuk eddig az i értéket

    beolvasva:    0   1   2   0   1   5 ....

     frekv[0]: 0->1---------->2
     frekv[1]: 0----->1---------->2
     frekv[2]: 0--------->1
     frekv[3]: 0
     frekv[4]: 0
     frekv[5]: 0--------------------->1
     frekv[6]: 0
     frekv[7]: 0
     frekv[8]: 0
     frekv[9]: 0
    frekv[10]: 0

    12
    0 1 2 0 1 5 2 1 6 9 1 2

    a végén:
               0  1  2  3  4  5  6  7  8  9 10
        frekv: 2  4  3  0  0  1  1  0  0  1  0

Implementáció:

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

int main()
{
    ifstream bemenet("input.txt");

    int n;
    bemenet >> n;

    int frekv[11] = {}; // 0,0,...,0

    for (int i = 0; i < n; i++) {
        int szam;
        bemenet >> szam;

        frekv[szam]++;
    }

    for (int i = 0; i <= 10; i++)
        cout << i << ": " << frekv[i] << " db" << endl;


    return 0;
}

Feladatok

1. https://www.pbinfo.ro/probleme/267/unice
Adott n darab legfeljebb kétjegyű természetes szám. Ki kell írni azokat, amik csak egyszer jelennek meg.

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

int main()
{
    ifstream bemenet("unice.in");
    ofstream kimenet("unice.out");

    int n;
    bemenet >> n;

    int frekv[100] = {}; // 0,0,...,0

    for (int i = 0; i < n; i++) {
        int szam;
        bemenet >> szam;

        frekv[szam]++;
    }

    for (int i = 0; i <= 99; i++)
        if (frekv[i] == 1)
            kimenet << i << " ";
    kimenet << endl;

    return 0;
}

2. https://www.pbinfo.ro/probleme/525/numere1
Adott egy n elemű sorozat. Melyik az a két legnagyobb háromjegyű természetes szám, ami nem jelenik meg benne?

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >>n;
    int frekv[1000] = {};

    for(int i = 0; i < n; i++)
    {
        int szam;
        cin>>szam;
        if(szam>99 && szam<1000)
        {
            frekv[szam]++;
        }
    }
    int legnagyobb=0;
    int leg2nagyobb=0;
    for(int i=100; i<1000; i++)
    {
        if (frekv[i]==0)
        {
            leg2nagyobb=legnagyobb;
            legnagyobb=i;
        }
    }
    if(leg2nagyobb==0)
        cout<<"NU EXISTA";
    else
        cout<<leg2nagyobb<<" "<<legnagyobb<<endl;

    return 0;
}

// tesztgenerálás
/*
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ofstream fout("input.txt");

    fout << 676 << endl;
    for (int i = 100; i <= 999; i++)
        if (i != 677 && i != 676)
            fout << i << " ";
    fout << endl;

    return 0;
}
*/

3. https://www.pbinfo.ro/probleme/264/maxcif
Adottak egyjegyű számok, ki kell írni a legtöbbször megjelenő számjegy(ek)et.

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

int main()
{
    ifstream fin("maxcif.in");
    ofstream fout("maxcif.out");

    int f[10] = {};

    int szam;
    while (fin >> szam) {
        f[szam]++;
    }

    int maximum = 0;
    for (int i = 0; i <= 9; i++)
        if (maximum < f[i])
            maximum = f[i];

    for (int i = 0; i <= 9; i++)
        if (f[i] == maximum)
            fout << i << " ";
    fout << endl;

    return 0;
}

4. https://www.pbinfo.ro/probleme/187/ciffrecv
Adottak egyjegyű számok, ki kell írni, hogy melyik a legnagyobb prím és hányszor jelent meg.

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

int main()
{
    ifstream fin("ciffrecv.in");
    ofstream fout("ciffrecv.out");

    int f[10] = {};

    int szam;
    while (fin >> szam) {
        f[szam]++;
    }

    int legnagyobb = -1;

    for (int i = 0; i <= 9; i++) {
        if (f[i] != 0) {
            int hany_oszto = 0;
            for (int oszto = 1; oszto <= i; oszto++)
                if (i % oszto == 0)
                    hany_oszto++;

            if (hany_oszto == 2)
                legnagyobb = i;
        }
    }

    fout << legnagyobb << " " << f[legnagyobb] << endl;

    return 0;
}

Másképp:

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

int main()
{
    ifstream fin("ciffrecv.in");
    ofstream fout("ciffrecv.out");

    int f[10] = {};

    int szam;
    while (fin >> szam) {
        f[szam]++;
    }

    if (f[7] != 0)
        fout << 7 << " " << f[7] << endl;
    else if (f[5] != 0)
        fout << 5 << " " << f[5] << endl;
    else if (f[3] != 0)
        fout << 3 << " " << f[3] << endl;
    else if (f[2] != 0)
        fout << 2 << " " << f[2] << endl;
    else
        fout << "nincs" << endl;

    return 0;
}

Még másképp:

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

int main()
{
    ifstream fin("ciffrecv.in");
    ofstream fout("ciffrecv.out");

    int f[10] = {};

    int szam;
    while (fin >> szam) {
        if (szam == 2 || szam == 3 || szam == 5
            || szam == 7)
        {
            f[szam]++;
        }
    }

    int maximum = 0;
    for (int i = 0; i <= 9; i++)
        if (f[i] > 0)
            maximum = i;

    fout << maximum << " " << f[maximum] << endl;
    return 0;
}

5. https://www.pbinfo.ro/probleme/2837/intervale5
Adottak 100-nál nem negyobb természetes számok. Meg kell határozni az összes olyan (x,y) számpárt a sorozat elemeiből, amelyre y - x ≥ 2 és a sorozat egyetlen tagja sem eleme az (x,y) intervallumnak (ha nincsenek ilyen párok, akkor kiírjuk, hogy „nu exista”).

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

int main()
{
    ifstream fin("intervale5.in");
    ofstream fout("intervale5.out");

    int f[101] = {};

    int szam;
    while (fin >> szam) {
        f[szam]++;
    }

    bool volt = false;

    int x = 0;
    while (x <= 100 && f[x] == 0)
        x++;

    while (x <= 100) {
        int y = x+1;
        while (y <= 100 && f[y] == 0)
            y++;

        if (y <= 100 && y - x >= 2) {
            fout << x << " " << y << endl;
            volt = true;
        }

        x = y;
    }

    if (!volt)
        fout << "nu exista" << endl;

    return 0;
}

6. https://www.pbinfo.ro/probleme/1744/nrlipsa2
Adottak egész számok. Meg kell mondani, hogy a [-100, 100] intervallumnak melyik az a legkisebb egész szám eleme, amelyik nem jelenik meg (ha mind megjelenik, akkor a “nu exista” üzenetet kell kiírni).

Ötlet az indexeléshez:

    érték: -100 -99 ... -1   0   1 ...  99 100
    index:    0   1 ... 99 100 101 ... 199 200
    
    index == érték + 100

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

int main()
{
    ifstream be("nrlipsa2.in");
    ofstream ki("nrlipsa2.out");

    int f[201] = {};

    int szam;
    while (be >> szam) {
        if (szam >= -100 && szam <= 100) {
            f[szam+100]++;
        }
    }

    int i = -100;
    while (i <= 100 && f[i+100] != 0)
        i++;

    if (i > 100)
        ki << "nu exista" << endl;
    else
        ki << i << endl;


    return 0;
}

Eratosthenész szitája

Feladat: Adott határig (pl. 1 000 000-ig) határozzuk meg mindenkiről, hogy prím-e!

Első ötlet: szokványos prímteszt rendre minden számra.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    int db = 0;

    for (int i = 2; i <= 1000*1000; i++) {
        bool van_oszto = false;

        for (int d = 2; d * d <= i && !van_oszto; d++)
            if (i % d == 0)
                van_oszto = true;

        if (!van_oszto)
            db++;
    }

    cout << db << endl;
    return 0;
}

Gyorsabb megoldási ötlet: Eratoszthenész szitája

kezdetben minden 1-nél nagyobb szám prímként van megjelölve
végigmegyünk a listán és minden prímnek titulált elem többszöröseit kihúzzuk (mert nem prímek)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    bool kihuzva[1000*1000+1] = {};

    int db = 0;

    for (int i = 2; i <= 1000*1000; i++) {
        if (!kihuzva[i]) {
            db++; // i egy prim

            for (int j = 2; j*i <= 1000*1000; j++)
                kihuzva[j*i] = true;
        }
    }

    cout << db << endl;
    return 0;
}

7. https://www.pbinfo.ro/probleme/303/eratostene

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

int main()
{
    bool kihuzva[1000*1000+1] = {};

    for (int i = 2; i <= 1000*1000; i++) {
        if (!kihuzva[i]) {
            for (int j = 2; j*i <= 1000*1000; j++)
                kihuzva[j*i] = true;
        }
    }

    ifstream be("eratostene.in");
    ofstream ki("eratostene.out");
    int n;
    be >> n;

    int db = 0;

    for (int i = 0; i < n; i++) {
        int szam;
        be >> szam;

        if (!kihuzva[szam])
            db++;
    }

    ki << db << endl;
    return 0;
}

Karakterisztikus tömbök

a frekvenciatömbtől abban különbözik, hogy az egyes értékekre nem az elemek frekvenciáját, hanem valamilyen más információt tárol (pl. hol jelent meg legutóbb)

Feladat: Adottak egyjegyű term. számok. Minden érékre írjuk ki az utolsó pozíciót, ahol megjelent.

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

int main()
{
    ifstream be("input.txt");

    int t[10];
    for (int i = 0; i <= 9; i++)
        t[i] = -1;

    int x;
    int poz = 1;
    while (be >> x) {
        t[x] = poz;
        poz++;
    }

    for (int i = 0; i <= 9; i++)
        if (t[i] == -1)
            cout << i << ": nincs" << endl;
        else
            cout << i << ": " << t[i]
                 << ". helyen legutobb" << endl;

    return 0;
}

Feladat: Adott az input.txt fájlban egy sorozat, ami legfeljebb kétjegyű természetes számokból áll. Határozzuk meg, hogy melyik az az érték, amelyiknek az első és utolsó előfordulása a legmesszebb van egymástól! Holtverseny esetén válasszuk a kisebbik elemet.

Példa:

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

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

int main()
{
    ifstream be("input.txt");

    int eloszor[100];
    int legutobb[100];
    for (int i = 0; i <= 99; i++) {
        eloszor[i] = -1;
        legutobb[i] = -1;
    }

    int x;
    int poz = 1;
    while (be >> x) {
        if (eloszor[x] == -1)
            eloszor[x] = poz;
        else
            legutobb[x] = poz;

        poz++;
    }

    // ... HF: ide még kell egy maximumkeresés

    return 0;
}

Leszámláló rendezés

Egy frekvenciatömböt használhatunk a sorozat elemeinek rendezésére is (ha az értékek ezt megengedik).

Feladat: Adott egy sorozat, rendezzük növekvő sorrendbe. Az elemek 0 és 100 közöttiek.

 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
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream fin("input.txt");

    int f[101] = {};

    int n;
    fin >> n;

    for (int i = 0; i < n; i++) {
        int szam;
        fin >> szam;

        f[szam]++;
    }

    // növekvő sorrend
    for (int ertek = 0; ertek <= 100; ertek++) {
        // cout << ertek   f[ertek]-szer
        for (int i = 1; i <= f[ertek]; i++) {
            cout << ertek << " ";
        }
    }
    cout << endl;

    // csökkenő sorrend
    for (int ertek = 100; ertek >= 0; ertek--) {
        for (int i = 1; i <= f[ertek]; i++) {
            cout << ertek << " ";
        }
    }
    cout << endl;

    // ha egy tömbbe akarjuk tenni
    // a rendezett sorozatot:
    int t[1000];
    int k = 0;

    for (int ertek = 0; ertek <= 100; ertek++) {
        for (int i = 1; i <= f[ertek]; i++) {
            t[k] = ertek;
            k++;
        }
    }

    for (int i = 0; i < n; i++)
        cout << t[i] << " ";
    cout << endl;
    return 0;
}

További feladatok érettségi tételekből

A tételek magyar nyelvű változatai (is) megtalálhatók itt.

2019, augusztus, III.3.

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

int main()
{
    ifstream fin("input.txt");

    int frek[1001] = {}; // 0, 0, ... 0

    int szam;
    while (fin >> szam) {
        frek[szam]++;
    }

    for (int i = 1; i <= 1000; i += 2) {
        // frek[i]-szer kellene kiírni i-t
        /*for (int j = 1; j <= frek[i]; j++) {
            cout << i << " ";
        }*/
        // VAGY:
        while (frek[i] > 0) {
            cout << i << " ";
            frek[i]--;
        }
    }

    for (int i = 2; i <= 1000; i += 2) {
        // frek[i]-szer kellene kiírni i-t
        /*for (int j = 1; j <= frek[i]; j++) {
            cout << i << " ";
        }*/

        while (frek[i] > 0) {
            cout << i << " ";
            frek[i]--;
        }
    }

    cout << endl;
    return 0;
}

2024, próbaérettségi, III.3.
2023, július, III.3.
2025, próbaérettségi, III.3.
2023, augusztus, III.3.
2021, próbaérettségi, III.3.
2021, augusztus, III.3.