Kihagyás

9. gyakorlat

6. ZH

A gyakorlat elején 40 percben kerül megírásra a 6. zh. A feladatok témái:

  • algoritmus elkészítése
  • függvények megírása, bemenet/kimenet kezelés nélkül
  • ismétléses vezérléssel megoldható feladatok
  • számsorozatokhoz kapcsolódó számítások

Műveletek mátrixokkal

Az előző órán megtanultuk a dinamikus tömbök használatának módját, most pedig az ezekkel végezhető alapműveletek elmélyítésével foglalkozunk. Az első feladatban a célunk két mátrix szorzatának kiszámítása. Először megnézzük azt az esetet, amikor a mátrixokat 2D-s tömbök segítségével reprezentáljuk, utána pedig 1D-s tömbökkel igyekszünk hasonló funkcionalitást elérni.

Feladat (f0223)

A feladat két (kompatibilis) mátrix szorzatának kiszámítása. Ehhez foglalj dinamikusan helyet a két NxM-es mátrixnak, töltsd fel őket elemekkel és végezd el a mátrixok szorzását.

Feladat:

Egészítsd ki a matrixszorzas-2d.c programot a foglal() és megszuntet() függvények implementációjával úgy, hogy a program helyesen lefusson! A többi függvényt ne módosítsd! A cim() függvényből következtess vissza, hogy hogyan tárolódnak a mátrix értékei!

Példa bemenet/kimenet párok:

  1. példa

    • input: 
      1
      2 2 1 0 0 1 2 2 3 4 5 6
    • output: 
      1
2
3
      [2,2]
      3.00      4.00
      5.00      6.00

  2. példa

    • input: 
      1
      2 3 1 0 2 1 0 3 3 1 3 4 5
    • output: 
      1
2
3
      [2,1]
     13.00
     18.00

matrixszorzas-2d.c: 

 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
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai
 */

#include <stdio.h>
#include <stdlib.h>

typedef double** data_t;
typedef struct {
    int n, m;
    data_t data;
} matrix_t;

double* cim(matrix_t mx, int i, int j);
void foglal(matrix_t *mx);
void beolvas(matrix_t *mx);
void szoroz(matrix_t src1, matrix_t src2, matrix_t *dst);
void kiir(matrix_t mx);
void megszuntet(matrix_t *mx);

double* cim(matrix_t mx, int i, int j) {
    if (i < 0 || mx.n <= i || j < 0 || mx.m <= j || mx.data == NULL) {
        return NULL;
    }
    return &mx.data[i][j];
}

void foglal(matrix_t *mx) {
    /* memóriát kell foglalni az mx->n * mx->m méretű mátrix elemei számára */
}

void beolvas(matrix_t *mx) {
    int i, j;
    if (scanf("%d %d", &mx->n, &mx->m) != 2) {
        mx->n = 0;
        mx->m = 0;
        mx->data = NULL;
    }
    foglal(mx);
    for (i = 0; i < mx->n; ++i) {
        for (j = 0; j < mx->m; ++j) {
            scanf("%lf", cim(*mx, i, j));
        }
    }
}

void szoroz(matrix_t src1, matrix_t src2, matrix_t *dst) {
    int i, j, k;
    if (src1.m != src2.n) {
        dst->data = NULL;
        dst->n = dst->m = 0;
    }
    dst->n = src1.n;
    dst->m = src2.m;
    foglal(dst);
    for (i = 0; i < src1.n; ++i) {
        for (j = 0; j < src2.m; ++j) {
            *cim(*dst, i, j) = 0.0;
            for (k = 0; k < src1.m; ++k) {
                (*cim(*dst, i, j)) += *cim(src1, i, k) * *cim(src2, k, j);
            }
        }
    }
}

void kiir(matrix_t mx) {
    int i, j;
    printf("[%d,%d]\n", mx.n, mx.m);
    for (i = 0; i < mx.n; ++i) {
        for (j = 0; j < mx.m; ++j) {
            printf(" %10.2lf", *cim(mx, i, j));
        }
        putchar('\n');
    }
}

void megszuntet(matrix_t *mx) {
    /* törölni kell a mátrix elemei számára foglalt memóriát */
}

int main() {
    matrix_t a, b, c;
    beolvas(&a);
    beolvas(&b);
    szoroz(a, b, &c);
    kiir(c);
    megszuntet(&a);
    megszuntet(&b);
    megszuntet(&c);
    return 0;
}

Segítség

A mátrixszorzás menete:

multiply_matrices forrás: https://www.mscroggs.co.uk/blog/73

Wiki: mátrixszorzás

  • Dinamikus memóriafoglalás NxM-es 2D-s tömbnek: 

    1
2
3
4
5
6
    double** matrix;
int i;
matrix = (double**) malloc(N * sizeof(double*));
for (i = 0; i < N; ++i) {
    matrix[i] = (double*) malloc(M * sizeof(double));
}

  • Az így foglalt memóriaterület felszabadítása: 

    1
2
3
4
5
    int i;
for (i = 0; i < N ; ++i) {
    free(matrix[i]);
}
free(matrix);

Megoldás (m0223.c) 
  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
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai feladat megoldása
 *
 * Gergely Tamás, 2017. őszi félév.
 *
 * fordítás:
 *    gcc -o m0223 m0223.c
 *
 * futtatás:
 *    ./m0223
 */

#include <stdio.h>
#include <stdlib.h>

typedef double** data_t;
typedef struct {
    int n, m;
    data_t data;
} matrix_t;

double* cim(matrix_t mx, int i, int j);
void foglal(matrix_t *mx);
void beolvas(matrix_t *mx);
void szoroz(matrix_t src1, matrix_t src2, matrix_t *dst);
void kiir(matrix_t mx);
void megszuntet(matrix_t *mx);

double* cim(matrix_t mx, int i, int j) {
    if (i < 0 || mx.n <= i || j < 0 || mx.m <= j || mx.data == NULL) {
        return NULL;
    }
    return &mx.data[i][j];
}

void foglal(matrix_t *mx) {
    /* memóriát kell foglalni az mx->n * mx->m méretű mátrix elemei számára */
    int i;
    mx->data = malloc(mx->n * sizeof(double*));
    for (i = 0; i < mx->n; ++i) {
        mx->data[i] = malloc(mx->m * sizeof(double));
    }
}

void beolvas(matrix_t *mx) {
    int i, j;
    if (scanf("%d %d", &mx->n, &mx->m) != 2) {
        mx->n = 0;
        mx->m = 0;
        mx->data = NULL;
    }
    foglal(mx);
    for (i = 0; i < mx->n; ++i) {
        for (j = 0; j < mx->m; ++j) {
            scanf("%lf", cim(*mx, i, j));
        }
    }
}

void szoroz(matrix_t src1, matrix_t src2, matrix_t *dst) {
    int i, j, k;
    if (src1.m != src2.n) {
        dst->data = NULL;
        dst->n = dst->m = 0;
    }
    dst->n = src1.n;
    dst->m = src2.m;
    foglal(dst);
    for (i = 0; i < src1.n; ++i) {
        for (j = 0; j < src2.m; ++j) {
            *cim(*dst, i, j) = 0.0;
            for (k = 0; k < src1.m; ++k) {
                (*cim(*dst, i, j)) += *cim(src1, i, k) * *cim(src2, k, j);
            }
        }
    }
}

void kiir(matrix_t mx) {
    int i, j;
    printf("[%d,%d]\n", mx.n, mx.m);
    for (i = 0; i < mx.n; ++i) {
        for (j = 0; j < mx.m; ++j) {
            printf(" %10.2lf", *cim(mx, i, j));
        }
        putchar('\n');
    }
}

void megszuntet(matrix_t *mx) {
    /* törölni kell a mátrix elemei számára foglalt memóriát */
    int i;
    for (i = 0; i < mx->n; ++i) {
        free(mx->data[i]);
    }
    free(mx->data);
    mx->data = NULL;
    mx->n = mx->m = 0;
}

int main() {
    matrix_t a, b, c;
    beolvas(&a);
    beolvas(&b);
    szoroz(a, b, &c);
    kiir(c);
    megszuntet(&a);
    megszuntet(&b);
    megszuntet(&c);
    return 0;
}

Az előző a példában a mátrixokat - intuitív módon - 2D-s tömbökkel reprezentáltuk: egy olyan tömbbel, amelynek elemei a sorok(at reprezentáló tömbökre mutató pointerek). Mint láttuk, ez a megoldás odafigyelést igényel a szükséges memóriaterület foglalásakor és felszabadításakor, azonban a tömbök kezelése kényelmes (valóban kétdimenziós tömbként tudjuk indexelni). Lehetőségünk van azonban a (logikailag) 2D-s tömböket (fizikailag) 1D-s tömbökként is tárolni.

Feladat (f0222)

Az előző feladatot oldjuk meg úgy, hogy a 2D-s mátrixokat 1D-s tömbökbe tároljuk el.

Feladat:

Egészítsd ki a matrixszorzas-1d.c programot a foglal() és megszuntet() függvények implementációjával úgy, hogy a program helyesen lefusson. A többi függvényt ne módosítsd! A cim() függvényből következtess vissza, hogy hogyan tárolódnak a mátrix értékei!

Példa bemenet/kimenet párok:

  1. példa

    • input: 
      1
      2 2 1 0 0 1 2 2 3 4 5 6
    • output: 
      1
2
3
      [2,2]
      3.00      4.00
      5.00      6.00

  2. példa

    • input: 
      1
      2 3 1 0 2 1 0 3 3 1 3 4 5
    • output: 
      1
2
3
      [2,1]
     13.00
     18.00

matrixszorzas-1d.c: 

 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
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai
 */

#include <stdio.h>
#include <stdlib.h>

typedef double* data_t;
typedef struct {
    int n, m;
    data_t data;
} matrix_t;

double* cim(matrix_t mx, int i, int j);
void foglal(matrix_t *mx);
void beolvas(matrix_t *mx);
void szoroz(matrix_t src1, matrix_t src2, matrix_t *dst);
void kiir(matrix_t mx);
void megszuntet(matrix_t *mx);

double* cim(matrix_t mx, int i, int j) {
    if (i < 0 || mx.n <= i || j < 0 || mx.m <= j || mx.data == NULL) {
        return NULL;
    }
    return mx.data + ((i * mx.m) + j);
}

void foglal(matrix_t *mx) {
    /* memóriát kell foglalni az mx->n * mx->m méretű mátrix elemei számára */
}

void beolvas(matrix_t *mx) {
    int i, j;
    if (scanf("%d %d", &mx->n, &mx->m) != 2) {
        mx->n = 0;
        mx->m = 0;
        mx->data = NULL;
    }
    foglal(mx);
    for (i = 0; i < mx->n; ++i) {
        for (j = 0; j < mx->m; ++j) {
            scanf("%lf", cim(*mx, i, j));
        }
    }
}

void szoroz(matrix_t src1, matrix_t src2, matrix_t *dst) {
    int i, j, k;
    if (src1.m != src2.n) {
        dst->data = NULL;
        dst->n = dst->m = 0;
    }
    dst->n = src1.n;
    dst->m = src2.m;
    foglal(dst);
    for (i = 0; i < src1.n; ++i) {
        for (j = 0; j < src2.m; ++j) {
            *cim(*dst, i, j) = 0.0;
            for (k = 0; k < src1.m; ++k) {
                (*cim(*dst, i, j)) += *cim(src1, i, k) * *cim(src2, k, j);
            }
        }
    }
}

void kiir(matrix_t mx) {
    int i, j;
    printf("[%d,%d]\n", mx.n, mx.m);
    for (i = 0; i < mx.n; ++i) {
        for (j = 0; j < mx.m; ++j) {
            printf(" %10.2lf", *cim(mx, i, j));
        }
        putchar('\n');
    }
}

void megszuntet(matrix_t *mx) {
    /* törölni kell a mátrix elemei számára foglalt memóriát */
}

int main() {
    matrix_t a, b, c;
    beolvas(&a);
    beolvas(&b);
    szoroz(a, b, &c);
    kiir(c);
    megszuntet(&a);
    megszuntet(&b);
    megszuntet(&c);
    return 0;
}

Segítség

Gondoljunk bele, hogy a 2D-s változat sorait egymás mögé fűzve egy 1D-s reprezentációt kapunk, ahogy az alábbi ábra is mutatja:

2D_1D_conversion

Az 1D-s reprezentáció indexelése sorfolytonos feltöltés esetén tehát az M sorhossz felhasználásával a kövekezőképpen képezhető: i. sor j. oszlopának indexe i*M+j (i darab teljes sort követően kell még j darab elem).

  • Dinamikus memóriafoglalás N*M-es 1D-s tömbnek: 
    1
2
    double* matrix;
matrix = (double*) malloc(N * M * sizeof(double))
  • Az így foglalt memóriaterület felszabadítása: 
    1
    free(matrix);
Megoldás (m0222.c) 
  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
103
104
105
106
107
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai feladat megoldása
 *
 * Gergely Tamás, 2017. őszi félév.
 *
 * fordítás:
 *    gcc -o m0222 m0222.c
 *
 * futtatás:
 *    ./m0222
 */

#include <stdio.h>
#include <stdlib.h>

typedef double* data_t;
typedef struct {
    int n, m;
    data_t data;
} matrix_t;

double* cim(matrix_t mx, int i, int j);
void foglal(matrix_t *mx);
void beolvas(matrix_t *mx);
void szoroz(matrix_t src1, matrix_t src2, matrix_t *dst);
void kiir(matrix_t mx);
void megszuntet(matrix_t *mx);

double* cim(matrix_t mx, int i, int j) {
    if (i < 0 || mx.n <= i || j < 0 || mx.m <= j || mx.data == NULL) {
        return NULL;
    }
    return mx.data + ((i * mx.m) + j);
}

void foglal(matrix_t *mx) {
    /* memóriát kell foglalni az mx->n * mx->m méretű mátrix elemei számára */
    mx->data = malloc(mx->n * mx->m * sizeof(double));
}

void beolvas(matrix_t *mx) {
    int i, j;
    if (scanf("%d %d", &mx->n, &mx->m) != 2) {
        mx->n = 0;
        mx->m = 0;
        mx->data = NULL;
    }
    foglal(mx);
    for (i = 0; i < mx->n; ++i) {
        for (j = 0; j < mx->m; ++j) {
            scanf("%lf", cim(*mx, i, j));
        }
    }
}

void szoroz(matrix_t src1, matrix_t src2, matrix_t *dst) {
    int i, j, k;
    if (src1.m != src2.n) {
        dst->data = NULL;
        dst->n = dst->m = 0;
    }
    dst->n = src1.n;
    dst->m = src2.m;
    foglal(dst);
    for (i = 0; i < src1.n; ++i) {
        for (j = 0; j < src2.m; ++j) {
            *cim(*dst, i, j) = 0.0;
            for (k = 0; k < src1.m; ++k) {
                (*cim(*dst, i, j)) += *cim(src1, i, k) * *cim(src2, k, j);
            }
        }
    }
}

void kiir(matrix_t mx) {
    int i, j;
    printf("[%d,%d]\n", mx.n, mx.m);
    for (i = 0; i < mx.n; ++i) {
        for (j = 0; j < mx.m; ++j) {
            printf(" %10.2lf", *cim(mx, i, j));
        }
        putchar('\n');
    }
}

void megszuntet(matrix_t *mx) {
    /* törölni kell a mátrix elemei számára foglalt memóriát */
    free(mx->data);
    mx->data = NULL;
    mx->n = mx->m = 0;
}

int main() {
    matrix_t a, b, c;
    beolvas(&a);
    beolvas(&b);
    szoroz(a, b, &c);
    kiir(c);
    megszuntet(&a);
    megszuntet(&b);
    megszuntet(&c);
    return 0;
}

Feladat (f0227)

Problémafelvetés:

Számítsuk ki egy mátrix skalárral való szorzatát.

Specifikáció:

A program inputja egy s valós szám (a skalár), a mátrix mérete (n,m) alakban (ahol n a sorok, m az oszlopok száma), majd a mátrix valós elemei sorfolytonosan [a_11,a_12,...,a_1m,a_21,...,a_n1,...,a_nm] alakban. A program kimenete a skalárszorzás eredménye az input mátrixhoz hasonló (n,m)[b_11,b_12,...,b_1m,b_21,...,b_n1,...,b_nm] alakban.

Algoritmustervezés:

Dinamikus memóriafoglalással dolgozzunk.

Segítség

Ha egy mátrixot egy skalárral (egyszerű számmal) szorzunk, akkor az eredmény mátrixban minden érték az eredeti mátrix azonos pozíciójában lévő értékének skalárszorosa lesz. Vagyis gyakorlatilag a mátrix minden elemét külön-külön meg kell szorozni a számmal.

Wiki: mátrix szorzása skalárral

Lehetséges megoldás - 1D-s tömbbel (m0227-1.c) 
  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
103
104
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai feladat megoldása
 *
 * Gergely Tamás, 2018. őszi félév.
 *
 * fordítás:
 *    gcc -o m0227-1 m0227-1.c
 *
 * futtatás:
 *    ./m0227-1
 */

#include <stdio.h>
#include <stdlib.h>

typedef double* data_t;
typedef struct {
    int n, m;
    data_t data;
} matrix_t;

double* cim(matrix_t mx, int i, int j);
void foglal(matrix_t *mx);
void beolvas(matrix_t *mx);
void skalar(double skalar, matrix_t mx, matrix_t *eredmeny);
void kiir(matrix_t mx);
void megszuntet(matrix_t *mx);

double* cim(matrix_t mx, int i, int j) {
    if (i < 0 || mx.n <= i || j < 0 || mx.m <= j || mx.data == NULL) {
        return NULL;
    }
    return mx.data + ((i * mx.m) + j);
}

void foglal(matrix_t *mx) {
    /* memóriát kell foglalni az mx->n * mx->m méretű mátrix elemei számára */
    mx->data = malloc(mx->n * mx->m * sizeof(double));
}

void beolvas(matrix_t *mx) {
    int i, j;
    if (scanf("(%d,%d)[", &mx->n, &mx->m) != 2) {
        mx->n = 0;
        mx->m = 0;
        mx->data = NULL;
    }
    foglal(mx);
    for (i = 0; i < mx->n; ++i) {
        for (j = 0; j < mx->m; ++j) {
            scanf("%lf,", cim(*mx, i, j));
        }
    }
    scanf("]");
}

void skalar(double s, matrix_t mx, matrix_t *eredmeny) {
    int i, j;
    eredmeny->n = mx.n;
    eredmeny->m = mx.m;
    foglal(eredmeny);
    for (i = 0; i < mx.n; ++i) {
        for (j = 0; j < mx.m; ++j) {
            *cim(*eredmeny, i, j) = s * *cim(mx, i, j);
        }
    }
}

void kiir(matrix_t mx) {
    int i, j;
    printf("(%d,%d)[", mx.n, mx.m);
    for (i = 0; i < mx.n; ++i) {
        for (j = 0; j < mx.m; ++j) {
            if (i || j) {
                putchar(',');
            }
            printf("%lf", *cim(mx, i, j));
        }
    }
    printf("]\n");
}

void megszuntet(matrix_t *mx) {
    /* törölni kell a mátrix elemei számára foglalt memóriát */
    free(mx->data);
    mx->data = NULL;
    mx->n = mx->m = 0;
}

int main() {
    matrix_t a, b;
    double s;
    scanf("%lf%*[^(]", &s); // A "%*[^(]" beolvas mindent az inputról a következő '(' karakter előtt
    beolvas(&a);
    skalar(s, a, &b);
    kiir(b);
    megszuntet(&a);
    megszuntet(&b);
    return 0;
}
Lehetséges megoldás - 2D-s tömbbel (m0227-2.c) 
  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
103
104
105
106
107
108
109
110
111
112
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai feladat megoldása
 *
 * Gergely Tamás, 2018. őszi félév.
 *
 * fordítás:
 *    gcc -o m0227-2 m0227-2.c
 *
 * futtatás:
 *    ./m0227-2
 */

#include <stdio.h>
#include <stdlib.h>

typedef double** data_t;
typedef struct {
    int n, m;
    data_t data;
} matrix_t;

double* cim(matrix_t mx, int i, int j);
void foglal(matrix_t *mx);
void beolvas(matrix_t *mx);
void skalar(double skalar, matrix_t mx, matrix_t *eredmeny);
void kiir(matrix_t mx);
void megszuntet(matrix_t *mx);

double* cim(matrix_t mx, int i, int j) {
    if (i < 0 || mx.n <= i || j < 0 || mx.m <= j || mx.data == NULL) {
        return NULL;
    }
    return &mx.data[i][j];
}

void foglal(matrix_t *mx) {
    /* memóriát kell foglalni az mx->n * mx->m méretű mátrix elemei számára */
    int i;
    mx->data = malloc(mx->n * sizeof(double*));
    for (i = 0; i < mx->n; ++i) {
        mx->data[i] = malloc(mx->m * sizeof(double));
    }
}

void beolvas(matrix_t *mx) {
    int i, j;
    if (scanf("(%d,%d)[", &mx->n, &mx->m) != 2) {
        mx->n = 0;
        mx->m = 0;
        mx->data = NULL;
    }
    foglal(mx);
    for (i = 0; i < mx->n; ++i) {
        for (j = 0; j < mx->m; ++j) {
            scanf("%lf,", cim(*mx, i, j));
        }
    }
    scanf("]");
}

void skalar(double s, matrix_t mx, matrix_t *eredmeny) {
    int i, j;
    eredmeny->n = mx.n;
    eredmeny->m = mx.m;
    foglal(eredmeny);
    for (i = 0; i < mx.n; ++i) {
        for (j = 0; j < mx.m; ++j) {
            *cim(*eredmeny, i, j) = s * *cim(mx, i, j);
        }
    }
}

void kiir(matrix_t mx) {
    int i, j;
    printf("(%d,%d)[", mx.n, mx.m);
    for (i = 0; i < mx.n; ++i) {
        for (j = 0; j < mx.m; ++j) {
            if (i || j) {
                putchar(',');
            }
            printf("%lf", *cim(mx, i, j));
        }
    }
    printf("]\n");
}

void megszuntet(matrix_t *mx) {
    /* törölni kell a mátrix elemei számára foglalt memóriát */
    int i;
    for (i = 0; i < mx->n; ++i) {
        free(mx->data[i]);
    }
    free(mx->data);
    mx->data = NULL;
    mx->n = mx->m = 0;
}

int main() {
    matrix_t a, b;
    double s;
    scanf("%lf%*[^(]", &s); // A "%*[^(]" beolvas mindent az inputról a következő '(' karakter előtt
    beolvas(&a);
    skalar(s, a, &b);
    kiir(b);
    megszuntet(&a);
    megszuntet(&b);
    return 0;
}

Rekurzió vagy iteráció?

Feladat (f224)

Feladat:

Általánosítsd a Fibonacci sorozatot: tekintsük azt a \(k\)-ad rendű Fibonacci sorozatot, melynek első \(k\) eleme 1 (azaz \(a_0=...=a_{k-1}=1\)), a többi elemét pedig az előző \(k\) elem összegeként kapjuk, (azaz \(a_n=a_{n-1}+...+a_{n-k}\)). Írj programot, mely bekér egy \(k\) és egy \(n\) természetes számot, és kiszámítja a \(k\)-ad rendű Fibonacci-sorozat \(n\)-ik elemét! Készíts kétféle algoritmust két külön függvényben, és mindkettővel számoltasd ki az eredményt:

  • Az első egy rekurzív algoritmus legyen.
  • A másik átgondolt, ciklust használó algoritmus legyen.

Hasonlítsd össze a két megoldás futásidejét különféle \(k\) és \(n\) értékekre.

Lehetséges megoldás - rekurzió (m0224-1.c) 
 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
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai
 *
 * Gergely Tamás, 2018. őszi félév.
 *
 * Algoritmustervezés:
 *    Az általánosított k-ad rendű Fibonacci sorozat n-ik elemét egy rekurzív
 *    függvény számolja ki.
 *
 * fordítás:
 *    gcc -Wall -o m0224-1 m0224-1.c
 *
 * futtatás:
 *    ./m0224-1
 */

#include <stdio.h>

int fibonacci(int k, int n) {
    if (n <= k) {
        return 1;
    }
    int ossz = 0;
    for (int i = n - k; i < n; ++i) {
        ossz += fibonacci(k, i);
    }
    return ossz;
}

int main() {
    int k, n;
    scanf("%d%d", &k, &n);
    printf("fibonacci(%d, %d) = %d\n", k, n, fibonacci(k, n));
    return 0;
}
Lehetséges megoldás - rekurzió (videó)

Fibonacci tömbös megoldás

Lehetséges megoldás - tömb, teljes sorozat (m0224-2.c) 
 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
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai
 *
 * Gergely Tamás, 2018. őszi félév.
 *
 * Algoritmustervezés:
 *    Az általánosított k-ad rendű Fibonacci sorozat n-ik elemét egy nemrekurzív
 *    függvény számolja ki.
 *
 * fordítás:
 *    gcc -Wall -o m0224-2 m0224-2.c
 *
 * futtatás:
 *    ./m0224-2
 */

#include <stdio.h>
#include <stdlib.h>

int fibonacci(int k, int n) {
    int *tomb, osszeg;
    tomb = malloc(n * sizeof(int));
    for (int i = 0; i < k; ++i) {
        tomb[i] = 1;
    }
    for (int i = k; i < n; ++i) {
        tomb[i] = 0;
        for (int j = i - k; j < i; ++j) {
            tomb[i] += tomb[j];
        }
    }
    osszeg = tomb[n - 1];
    free(tomb);
    return osszeg;
}

int main() {
    int k, n;
    scanf("%d%d", &k, &n);
    printf("fibonacci(%d, %d) = %d\n", k, n, fibonacci(k, n));
    return 0;
}
Lehetséges megoldás - tömb, utolsó k elem (m0224-3.c) 
 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
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai
 *
 * Gergely Tamás, 2018. őszi félév.
 *
 * Algoritmustervezés:
 *    Az általánosított k-ad rendű Fibonacci sorozat n-ik elemét egy nemrekurzív
 *    függvény számolja ki. Az elemek kiszámolásához csak egy minimális méretű
 *    tömböt használunk.
 *
 * fordítás:
 *    gcc -Wall -o m0224-3 m0224-3.c
 *
 * futtatás:
 *    ./m0224-3
 */

#include <stdio.h>
#include <stdlib.h>

int fibonacci(int k, int n) {
    int *tomb, actidx, nextval;
    tomb = malloc(n * sizeof(int));
    for (int i = 0; i < k; ++i) {
        tomb[i] = 1;
    }
    nextval = k;
    actidx = k - 1;
    for (int i = k; i < n; ++i) {
        int tmp;
        actidx = (actidx + 1) % k;
        tmp = tomb[actidx];
        tomb[actidx] = nextval;
        nextval = 2 * nextval - tmp;
    }
    nextval = tomb[actidx];
    free(tomb);
    return nextval;
}

int main() {
    int k, n;
    scanf("%d%d", &k, &n);
    printf("fibonacci(%d, %d) = %d\n", k, n, fibonacci(k, n));
    return 0;
}
Lehetséges megoldás - tömb, utolsó k elem (videó)

Fibonacci iteratív megoldás

Sorting - Beszúró rendezés

Feladat (f0225)

Problémafelvetés:

Írj egy programot ami sorbarendezi a bekért értékeket.

Specifikáció:

A program inputjának első eleme egy egész szám, a sorozat elemeinek száma, ezt követi a megadott számú valós érték. A program kimenetének első eleme egy egész szám, a sorozat elemeinek száma, utána pedig a sorozat elemei növekvő sorrendben, 3 tizedesjegy pontossággal. A kimeneten az értékek egy-egy szóközzel vannak elválasztva.

Algoritmustervezés:

A sorozat elemeit egy tömbben tároljuk, eleve rendezett formában. Ez azt jelenti, hogy minden újabb elemet a neki akkor éppen megfelelő helyre szúrunk be a tömbbe. A beszúrást egy külön függvény végezze.

Segítség

A beszúró rendezés algoritmusa: multiply_matrices

forrás: https://hu.wikipedia.org/wiki/Besz%C3%BAr%C3%A1sos_rendez%C3%A9s

Lehetséges megoldás (m0225.c) 
 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
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai
 *
 * Keleti Márton, 2018. őszi félév.
 *
 * Specifikáció:
 *    Input: egy N pozitív egész és N darab valós szám
 *    Output: az N egész szám, és a beolvasott valós számok növekvő sorrendben
 *            3 tizedesjegy pontossággal szóközzel elválasztva
 *
 * Algoritmustervezés:
 *    A sorozat elemeit egy tömbben tároljuk, eleve rendezett formában. Ez azt
 *    jelenti, hogy minden újabb elemet a neki akkor éppen megfelelő helyre
 *    szúrunk be a tömbbe. A beszur() függvény paraméterként kapja a rendezett
 *    tömböt, a beszúrandó számot, és az új számmal együtt vett méretet. Az új
 *    számot a tömb végére teszi, hiszen ott eddig nem volt hasznos elem, majd
 *    addig cserélgeti az előtte lévő elemekkel, ezáltal előrébb hozva a
 *    tömbben, amíg azok nagyobbak nála.
 *
 * Fordítás:
 *    gcc -Wall -o m0225 m0225.c
 *
 * Futtatás:
 *    ./m0225
 */

#include <stdio.h>

void beszur(double tomb[], double szam, int meret) {
    tomb[meret] = szam;
    for (int i = meret; i > 0 && tomb[i-1] > tomb[i]; --i) {
        double tmp = tomb[i];
        tomb[i] = tomb[i-1];
        tomb[i-1] = tmp;
    }
}

int main() {
    int n;
    scanf("%d", &n);

    double tomb[n];
    for (int i = 0; i < n; ++i) {
        double r;
        scanf("%lf", &r);
        beszur(tomb, r, i);
    }

    printf("%d ", n);
    for (int i = 0; i < n; ++i) {
        printf("%.3lf ", tomb[i]);
    }
    printf("\n");

    return 0;
}
Lehetséges megoldás (videó)

beszúró rendezés

Feladatok

Feladat (f0121)

Problémafelvetés:

Írj egy programot ami kiírja 1-től 12-ig az \(n!\) értékét!

Algoritmustervezés:

Kétféle algoritmust készíts! Az elsőben egy külön függvény számítsa ki \(n!\) értékét, majd ezt felhasználva a főprogramból írasd ki a megfelelő értékeket. A másik verzióban optimalizáld a programot, és egyetlen ciklus segítségével oldd meg a feladatot!

Feladat (f0210)

Problémafelvetés:

Adottak síkidomok (kör, ellipszis, háromszög, négyzet, téglalap) a jellemző értékeikkel. Készíts egy tömböt ilyen alakzatok tárolására, olvasd be az adataikat, majd írd ki az összterületüket. Ezután írd ki mindegyik fajtából a legnagyobb területű síkidom kerületét.

Algoritmustervezés/Megvalósítás:

A főprogram csak az input/output műveleteket végezze, a számolást külön függvény(ek)ben oldd meg. Az adatok tárolására használj összetett adatszerkezetet, ha van értelme.

További feladatok

Feladat (f0208)

Problémafelvetés:

Adottak pontok a síkon. Írj programot, ami meghatározza azokat a pontokat, amelyek a ponthalmaz konvex burkát alkotják.

Algoritmustervezés/Megvalósítás:

A főprogram csak az input/output műveleteket végezze, a számolást külön függvény(ek)ben oldd meg. Az adatok tárolására használj összetett adatszerkezetet, ha van értelme.

Feladat (f0209)

Problémafelvetés:

Adottak pontok a síkon. Írj programot, ami meghatározza azokat a pontokat, amelyek a ponthalmaz konvex burkát alkotják.

Algoritmustervezés/Megvalósítás:

A főprogram csak az input/output műveleteket végezze, a számolást külön függvény(ek)ben oldd meg. Az adatok tárolására használj összetett adatszerkezetet, ha van értelme. A program a bemenet.txt nevű fájlból olvassa be az adatokat és a kimenet.txt nevű fájlba írja ki az eredményt.

Feladat (f0212)

Problémafelvetés:

Adottak a háromdimenziós térben töltéssel és tömeggel rendelkező pontszerű részecskék. Készíts egy programot, ami beolvassa több ilyen részecske adatait, majd mindre külön-külön kiszámolja a rá ható gravitációs illetve elektromos erőket, illetve ezek eredőjét.

Algoritmustervezés/Megvalósítás:

A főprogram csak az input/output műveleteket végezze, a számolást külön függvény(ek)ben oldd meg. Az adatok tárolására használj összetett adatszerkezetet, ha van értelme.

Feladat (f0213)

Problémafelvetés:

Adottak a háromdimenziós térben töltéssel és tömeggel rendelkező pontszerű részecskék. Készíts egy programot, ami beolvassa több ilyen részecske adatait, majd mindre külön-külön kiszámolja a rá ható gravitációs illetve elektromos erőket, illetve ezek eredőjét.

Algoritmustervezés/Megvalósítás:

A főprogram csak az input/output műveleteket végezze, a számolást külön függvény(ek)ben oldd meg. Az adatok tárolására használj összetett adatszerkezetet, ha van értelme. A program a bemenet.txt nevű fájlból olvassa be az adatokat és a kimenet.txt nevű fájlba írja ki az eredményt.

Feladat (f0280)

Feladat:

A feladatunk egy adott, számokat tartalmazó tömbről kiíratni a képernyőre, hogy melyik értékből hány darab van benne, és mindezt egy hisztogram formájában is jelenítsük meg. (A hisztogram egy olyan oszlopdiagram, ahol nem az egyes adatpontok értékét ábrázoljuk, hanem agy oszlop az egy értéknek felel meg, a magassága pedig azt mutatja, hogy hány adatpontnak volt ennyi az értéke.)

Algoritmustervezés:

A tömb mérete legyen konstans, és a számokat egy \([0,N)\) tartományból válasszuk (véletlenszerűen). Az egyes értékek darabszámát és a hisztogram "kirajzolását" külön-külön függvények valósítsák meg.

Lehetséges megoldás (m0280.c) 
 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
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai
 *
 * Kalmár György, 2020. őszi félév.
 *
 * Fordítás:
 *    gcc -Wall -o m280 m0280.c
 *
 * Futtatás:
 *    ./m0280
 */

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define N    300
#define RMAX 18

// hisztogram kirajzolása
void draw_histogram(int t[], int meret) {
    /* Vízszintesen fogunk rajzolni, vagyis az oszlopok egymás alatt/fölött
     * vízszintesen lesznek kirajzolva a karakteres képernyőn.
     */
    for (int i = 0; i < meret; ++i) {           // végigmegyünk az egész tömbön, és minden számhoz rajzolunk
        printf("%3d: ", i);                     // kiírjuk, hogy melyik számról van szó
        for (int j = 0; j < t[i]; ++j) {        // majd annyi '|' karaktert írunk ki, amennyi az érték
            printf("|");
        }
        printf("\n");
    }
}

// hisztogram számító függvény
void histogram(int t[], int meret, int random) {
    int *szamok,        // pointer a segédtömbre
        i;      // indexváltozó
    szamok = malloc(random * sizeof(int));
    printf("\n");

    // feltöltjük 0-val a segédtömböt, mivel majd növelgetni szeretnénk az elemeinek az értekeit,
    // az alápjan, hogy milyen számokat találtunk a kapott tömbben
    for (i = 0; i < random; ++i) {
        szamok[i] = 0;
    }

    // növeljük az adott elem darabszámát a segédtömbben,
    // így a ciklus végén pl. a 0. pozíción az lesz látható, hogy hány 0 volt,
    // az 1. pozíción, hogy hány 1-es, és így tovább.
    for (i = 0; i < meret; ++i) {
        ++szamok[t[i]];
    }

    printf("\n");

    // a segédtömb kiíratása, hogy lássuk melyik számból hány darab van
    for (i = 0; i < random; ++i) {
        printf("%2d ", szamok[i]);
    }
    printf("\n\n");
    draw_histogram(szamok, random);
    free(szamok);
}

int main() {
    srand(time(NULL));
    int t[N],           // tömb a random számokhoz
        i;              // indexváltozó

    // feltöltjük a tömböt random értékekkel a [0, RMAX] tartományon
    for (i = 0; i < N; ++i) {
        t[i] = rand() % RMAX;
    }

    // kiíratjuk a tömböt, hogy tudjunk a végén ellenőrizni
    for (i = 0; i < N; ++i) {
        printf("%d ", t[i]);
    }
    printf("\n");

    // hisztogram kiszámító függvény meghívása
    /*
     * Argumentumok:
     *   - a tömb
     *   - a tömb mérete
     *   - hány féle számunk van
     * Bár a tömb méretét, és a számok intervallumának felső korlátját konstanssal adtuk meg,
     * a függvényeket érdemes általánosabban úgy tervezni, hogy ne ezeket a konstansokat
     * használják, hanem argumentumként kapják meg ezeket az értékeket.
     */
    histogram(t, N, RMAX);

    return 0;
}
Feladat (f0281)

Feladat:

Készíts egy, az "akasztófa" nevű játékhoz hasonló szókitaláló játékprogramot. A program egy fix listából véletlenszerűen válasszon egy szót, amit majd ki kell találni. A játékos a szó minden betűjére sorban tippel, a következő betűre akkor tippelhet, ha az előzőt eltalálta. Minden betűre legfeljebb 6 alkalommal lehet tippelni, ha ennyiből nincs helyes tipp, akkor a játéknak vége, a játékos veszített.

Specifikáció:

Példajáték: 

 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
_______
Tippelj egy betűt: l
Eltaláltad az adott karaktert, léphetsz tovább!
l______
Tippelj egy betűt: v
Nem talált! Még 5 lehetőség az adott karakterre!
l______
Tippelj egy betűt: m
Nem talált! Még 4 lehetőség az adott karakterre!
l______
Tippelj egy betűt: o
Eltalaltad az adott karaktert, léphetsz tovább!
lo_____
Tippelj egy betűt: v
Eltaláltad az adott karaktert, léphetsz tovább!
lov____
Tippelj egy betűt: a
Eltaláltad az adott karaktert, léphetsz tovább!
lova___
Tippelj egy betűt: t
Nem talált! Még 5 lehetőség az adott karakterre!
lova___
Tippelj egy betűt: r
Nem talált! Még 4 lehetőség az adott karakterre!
lova___
Tippelj egy betűt: e
Nem talált! Még 3 lehetőség az adott karakterre!
lova___
Tippelj egy betűt: g
Eltaláltad az adott karaktert, léphetsz tovább!
lovag__
Tippelj egy betűt: o
Eltalaltad az adott karaktert, léphetsz tovább!
lovago_
Tippelj egy betűt: n
Nem talált! Még 5 lehetőség az adott karakterre!
lovago_
Tippelj egy betűt: k

Gratulálok! Kitaláltad a keresett szót, amely "lovagok" volt!

Lehetséges megoldás (m0281.c) 
 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
/*
 * Szegedi Tudományegyetem
 * Informatikai Tanszékcsoport
 * Szoftverfejlesztés Tanszék
 *
 * Programozás Alapjai
 *
 * Kalmár György, 2020. őszi félév.
 *
 * Fordítás:
 *    gcc -Wall -o m281 m0281.c
 *
 * Futtatás:
 *    ./m0281
 */

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define N 30
#define L 20
#define ELET 6

char szavak[N][L] = {
    "alma",
    "biro",
    "cica",
    "dezso",
    "elemer",
    "fiok",
    "godeny",
    "hupikektorpikek",
    "ingyombingyom",
    "juhturo",
    "kalahari",
    "lemur",
    "lyuk",
    "morcos",
    "nap",
    "nyunyoka",
    "otthon",
    "pointer",
    "rovasiras",
    "rovarsiras",
    "santa",
    "szombat",
    "tehen",
    "tyukanyo",
    "ugrodeszka",
    "vagodeszka",
    "walter",
    "xilofon",
    "zebra",
    "zsak"
};

int main () {
    srand(time(NULL));

    char eredmeny[N], *szo, tipp;
    int i, testreszek = ELET;

    szo = szavak[random() % N];

    for (i = 0; szo[i] != 0; ++i) {
        eredmeny[i] = '_';
    }
    eredmeny[i] = 0;

    for (i = 0; szo[i] != 0;) {
        printf("%s\nTippelj egy betűt: ", eredmeny);
        tipp = getchar();
        getchar();      // A '\n' "lenyelése"
        if (szo[i] == tipp) {
            printf("Talált!\n");
            eredmeny[i++] = tipp;
            printf("%s\n", eredmeny);
            testreszek = ELET;
        } else {
            if (--testreszek == 0) {
                printf("\n\nSajnos vesztettél... \nA szó <<< %s >>> lett volna.\n", szo);
                return 0;
            }
            printf("Nem talált! Még %d életed van.\n", testreszek);
        }
    }

    printf("\n\nGratulálunk! Kitaláltad a szót! <<< %s >>>\n", szo);
    return 0;
}

Kapcsolódó linkek

Utolsó frissítés: 2022-11-25 15:25:14