Mi volt eddig?

C++ nyelvi elemek:
- változók, kontroll-szerkezetek
- beolvasás/kiírás
Algoritmusok
- oszthatóság
- sorozatok
- számjegyekre bontás
Fájlműveletek
Tömbök, kétdimenziós tömbök
- rendezés
- összefésülés
- keresés / bináris keresés
- beszúrás, törlés
- tükrözések
- mátrix átlói

XI-es anyag

függvények
feladatmegoldási módszerek:
- divide et impera
- backtracking
szövegdarabok (string-ek)
struktúrák
gráfelmélet

HF: elolvasni/tudni

elágazás és ciklusok
adattípusok (egész szám, valós szám, logikai típus)
egydimenziós tömb használata
kétdimenziós tömb használata

Feladatok

1.

Adott az input.txt fájlban egy n természetes szám, majd a következő soron egy n elemű sorozat elemei (minden szám egész, legfeljebb ötjegyű, n ≤ 100).

a) írjuk ki a sorozat páros elemeit a megjenésük fordított sorrendjében

b) írjuk ki a prímek összegét

c) írjuk ki a sorozatot csökkenő sorrendben

    Példa   be: 5
                16 11 14 13 12

            ki: a) 12 14 16
                b) 24
                c) 16 14 13 12 11

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

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

    int n;
    fin >> n;

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

    // a)
    for (int i = n-1; i >= 0; i--)
        if (t[i] % 2 == 0)
            cout << t[i] << " ";

    cout << endl;

    // b)
    int primek_osszege = 0;

    for (int i = 0; i < n; i++) {
        // ha t[i] prím akkor
        //      primek_osszege += t[i];

        int osztok_szama = 0;

        for (int d = 1; d <= t[i]; d++)
            if (t[i] % d == 0)
                osztok_szama++;

        if (osztok_szama == 2)
            primek_osszege += t[i];
    }

    cout << primek_osszege << endl;

    // c)
    for (int bal = 0; bal < n; bal++)
        for (int jobb = bal+1; jobb < n; jobb++)
            if (t[bal] < t[jobb]) {
                // csere  t[bal] <-> t[jobb]
                int regi_bal = t[bal];
                t[bal] = t[jobb];
                t[jobb] = regi_bal;
            }


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

    cout << endl;
    return 0;
}

2.

Adottak legfeljebb kétjegyű term. számok az input.txt állományban. Szeretnénk kiírni, hogy:

a) melyik érték hányszor jelenik meg (feltéve, hogy megjelenik)

b) melyik a legnagyobb érték a [0,99] intervallumból, ami nem jelenik meg?

c) milyen hosszú, a legnagyobb hézag két megjelenő érték között?

    Pl. be: 10 20 22 10
        ki:
            a) 10  2 db
               20  1 db
               22  1 db
            b) 99
            c) 10 egyseg (10 ... 20 ... 22)
                             ***

 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <fstream>
using namespace std;


int main()
{

    ofstream fout("input.txt");
    for (int i = 0; i <= 99; i++)
        fout << i << " ";
    cout << endl;
    return 0;


    int frek[100] = {};

    ifstream fin("input.txt");

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


    // a)
    for (int i = 0; i <= 99; i++)
        if (frek[i] != 0)
            cout << i << ": "
                 << frek[i] << " db" << endl;

    // b)
    int melyik = -1;
    for (int i = 0; i <= 99; i++)
        if (frek[i] == 0)
            melyik = i;

    if (melyik == -1)
        cout << "mind megjelenik" << endl;
    else
        cout << melyik << endl;

    // c)
    bool volt_nem_nulla = false;

    int max_hany_nulla = -1;
    int hany_nulla = 0;

    for (int i = 0; i <= 99; i++)
        if (frek[i] == 0)
            hany_nulla++;
        else {
            if (volt_nem_nulla
                && hany_nulla > max_hany_nulla)
            {
                    max_hany_nulla = hany_nulla;
            }

            volt_nem_nulla = true;
            hany_nulla = 0;
        }


    if (max_hany_nulla == -1)
        cout << "nincs hezag";
    else
        cout << max_hany_nulla + 1 << endl;

    // c) másképp: (i,j) párokat keresünk,
    // ahol frek[i] != 0 és frek[j] != 0

    int i = 0;
    while (i <= 99 && frek[i] == 0)
        i++;

    int j = i+1;
    while (j <= 99 && frek[j] == 0)
        j++;

    if (j > 99)
        cout << "nincs hezag";
    else {
        int max_hezag = j - i;

        while (j <= 99) {
            i = j;
            j = i+1;
            while (j <= 99 && frek[j] == 0)
                j++;

            if (j <= 99 && max_hezag < j-i)
                max_hezag = j-i;
        }

        cout << max_hezag << endl;
    }

    return 0;
}

3.

Adott az input.txt fájlban egy n szám, majd egy n elemű tömb elemei.

a) Töröljük ki a tömbből az első 0-t, ha nincs, akkor írjuk ki, hogy “I love chemistry!”

b) Szúrjunk be az első 2-es után egy 3-ast, ha nincs, akkor írjuk ki, hogy “I don’t love chemistry anymore!”.

c) Töröljük ki az összes 1-est.

Minden lépés után írjuk ki a tömböt!

 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <fstream>
using namespace std;


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

    int t[100];
    int n;

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

    int poz = -1;
    for (int i = 0; i < n; i++)
        if (t[i] == 0 && poz == -1)
            poz = i;

    if (poz == -1)
        cout << "I love chemistry!" << endl;
    else {
        // törlés
        for (int i = poz; i <= n-2; i++)
            t[i] = t[i+1];
        n--;


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

    }

    // b
    poz = -1;
    for (int i = 0; i < n; i++)
        if (t[i] == 2 && poz == -1)
            poz = i;


    if (poz == -1)
        cout << "I don't love chemistry anymore!" << endl;
    else {
        for (int i = n-1; i>= poz+1; i--)
            t[i+1] = t[i];

        t[poz+1] = 3;
        n++;

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

    // c
    int i = 0;
    while (i < n)
        if (t[i] == 1) {
            for (int j = i+1; j < n; j++)
                t[j-1] = t[j];
            n--;
        }
        else {
            i++;
        }

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

    return 0;
}

4.

Adott az input.txt fájlban egy n és m term. szám, majd n x m darab egész, melyek egy mátrix elemei.

a) cseréljük fel egymás között a szemközti sarkokban levő elemeket, és írjuk ki a mátrixot.

b) az egyes sorokon számolt összegek közül mennyi a legkisebb

c) a kereten (első és utolsó sor/oszlop) levő elemet állítsuk 0-ra és írjuk ki a mátrixot

  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
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <iostream>
#include <fstream>
#include <climits>
using namespace std;

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


    int n, m;
    int matrix[100][100];

    fin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            fin >> matrix[i][j];


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << matrix[i][j] << " ";
        cout << endl;
    }

    cout << endl;

    // a)

    // matrix[0][0] <-> matrix[n-1][m-1]
    int seged = matrix[0][0];
    matrix[0][0] = matrix[n-1][m-1];
    matrix[n-1][m-1] = seged;

    // matrix[0][m-1] <-> matrix[n-1][0]
    seged = matrix[0][m-1];
    matrix[0][m-1] = matrix[n-1][0];
    matrix[n-1][0] = seged;


    cout << "csere utan: " << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << matrix[i][j] << " ";
        cout << endl;
    }

    cout << endl;

    // b)

    cout << "b)" << endl;

    int minimum = INT_MAX;

    for (int i = 0; i < n; i++) {
        int sorosszeg = 0;

        for (int j = 0; j < m; j++)
            sorosszeg += matrix[i][j];

        //cout << sorosszeg << endl;
        if (sorosszeg < minimum)
            minimum = sorosszeg;
    }

    cout << "legkisebb sorosszeg: "
         << minimum << endl;


    cout << endl << "c)" << endl;
    // c)

    // első sor
    for (int j = 0; j < m; j++)
        matrix[0][j] = 0;

    // utolsó sor
    for (int j = 0; j < m; j++)
        matrix[n-1][j] = 0;

    // első oszlop
    for (int i = 0; i < n; i++)
        matrix[i][0] = 0;

    // utolsó oszlop
    for (int i = 0; i < n; i++)
        matrix[i][m-1] = 0;


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << matrix[i][j] << " ";
        cout << endl;
    }

    cout << endl;


    return 0;
}

5.

Adott egy n természetes szám. Építsünk fel a memóriában és írjunk ki egy olyan n x n-es négyzetes mátrixot, melynek a főátlóján és az alatt 0-k, a főátlója felett egyesével növekvő értékek találhatók (mint a példában).

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

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

    int matrix[100][100];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i >= j)
                matrix[i][j] = 0;
            else
                matrix[i][j] = j-i;

    // vagy:
    /*for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++)
            matrix[i][j] = 0;

        int ertek = 1;
        for (int j = i+1; j < n; j++) {
            matrix[i][j] = ertek;
            ertek++;
        }
    }
    */

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << matrix[i][j] << " ";
        cout << endl;
    }

    return 0;
}

6.

Adott egy n természetes szám, majd egy n x n-es négyzetes mátrix elemei. Írjuk ki a mellékátló feletti elemek összegét és a mellékátló alatti elemek maximumát!

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

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

    int n;
    fin >> n;

    int matrix[100][100];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            fin >> matrix[i][j];

    int osszeg = 0;

    /*
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i+j < n-1)
                osszeg += matrix[i][j];
    */

    // vagy:
    // i+j < n-1  <=> j < n-1-i

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n-1-i; j++)
            osszeg += matrix[i][j];

    cout << osszeg << endl;

    int maximum = INT_MIN;

    /*
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i+j > n-1 && matrix[i][j] > maximum)
                maximum = matrix[i][j];
    */

    // vagy:
    // i+j > n-1  <=>  j > n-1-i
    for (int i = 0; i < n; i++)
        for (int j = (n-1-i)+1; j < n; j++)
            if (matrix[i][j] > maximum)
                maximum = matrix[i][j];

    cout << maximum << endl;
    return 0;
}

7. (Jázmin-féle feladat)

Adott két nem nulla természetes szám. Keressük meg azt a legnagyobb prímszámot, ami közös osztójuk.

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

int main()
{
    int a, b;
    cin >> a >> b;

    int eddigi = -1;

    for (int i = 1; i <= a; i++) {
        if (a%i == 0 && b%i == 0) {

            int db = 0;

            for (int j = 1; j <= i; j++)
                if (i % j == 0)
                    db++;

            // ha i prím
            if (db == 2)
                eddigi = i;
        }
    }

    cout << eddigi << endl;

    // Más ötlet:
    // minden közös osztó osztója az lnko-nak
    /*
    while (b != 0) {
        int regi = a;
        a = b;
        b = regi%b;
    }
    int lnko = a;
    
    // kell az lnko legnagyobb prímtényezője
    if (lnko == 1)
        cout << "nincs" << endl;
    else {
        int d = 2;
        int eddigi = -1;

        while (lnko > 1) {
            while (lnko % d == 2) {
                lnko /= d;
                eddigi = d;
            }
            d++;
        }

        cout << eddigi << endl;
    }
    */

    return 0;
}