Лекция 12
Задача 1. Найти факториал целого числа (исходный текст)
...
fact(N);
...
int fact(int N) {
if (N <= 1)
return N;
else
return N * fact(N-1);
}
Рекурсия небезопасна, так как на каждый вызов функции тратится место в стеке вызовов функций и может произойти выход за границу сегмента памяти (Segmentation Fault).
GDB – команды:
bt – показать стек вызовов функций
frame <номер уровня в стеке вызовов> - перейти на заданный уровень в стеке вызовов функций
Игра в 15. - квадрат 4*4, квадратики 1-15, 16-я клетка свободна. Надо двигать квадратики так, чтобы они стали упорядочены.
Премия за решение следующей позиции:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14
Решать программно:
3*3 – рекурсия работала
4*4 — рекурсия не работала :-)
Задача 2. Слить два отсортированных массива (исходный текст)
void merge(double *a, int na, double *b, int nb, double *c) {
int i = 0, j = 0, k, nc = na + nb;
for (k = 0; k < nc; k++) {
if ((i < na) && ((j >= nb) || (a[i] < b[j]))) {
c[k] = a[i++];
} else {
c[k] = b[j++];
}
}
}
Задача 3. Отсортировать массив при помощи функции merge() (рекурсивное слияние) (исходный текст)
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
5 |
12 |
-3 |
8 |
11 |
-7 |
1 |
9 |
-1 |
8’ |
15 |
21 |
-24 |
6 |
3 |
-3’ |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
5 |
12 |
-3 |
8 |
-7 |
11 |
1 |
9 |
-1 |
8’ |
15 |
21 |
-24 |
6 |
-3’ |
3 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
-3 |
5 |
8 |
12 |
-7 |
1 |
9 |
11 |
-1 |
8’ |
15 |
21 |
-24 |
-3’ |
3 |
6 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
-7 |
-3 |
1 |
5 |
8 |
9 |
11 |
12 |
-24 |
-3’ |
-1 |
3 |
6 |
8’ |
15 |
21 |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
-24 |
-7 |
-3 |
-3’ |
-1 |
1 |
3 |
5 |
6 |
8 |
8’ |
9 |
11 |
12 |
15 |
21 |
#include <stdlib.h>
...
void sort(double *a, int n) {
double *b = (double*)malloc(n * sizeof(double));
if (b == NULL) {
exit(-1);
}
copy(a, b, n);
splitMerge(b, 0, n, a);
free(b);
}
/* Write fragment of array b starting from index beg till index end to array a in sorted order */
/* Записать фрагмент массива b [beg, end) в массив a в отсортированном виде */
void splitMerge(double *b, int beg, int end, double *a) {
int mid;
if ((end - beg) >= 2) {
mid = (beg + end) / 2;
splitMerge(a, beg, mid, b);
splitMerge(a, mid, end, b);
merge(&b[beg], mid - beg, &b[mid], end - mid, &a[beg]);
}
}
/* Copy array A of size N to array B */
void copy(double *A, double *B, int N) {
double *endA = &A[N];
while (A < endA)
*(B++) = *(A++);
}