Ëåêöèÿ 13
Çàäà÷à 1. Íàéòè ôàêòîðèàë öåëîãî ÷èñëà (èñõîäíûé òåêñò)
#define MAX_COUNT 1000
/* int counter = 0; */
...
fact(N);
...
int fact(int N) {
static int counter = 0;
if (++counter > MAX_COUNT) {
printf(“Call stack overflow\n”);
exit(-1);
}
if (N <= 1)
return N;
else
return N * fact(N-1);
}
Ðåêóðñèÿ íåáåçîïàñíà, òàê êàê íà êàæäûé âûçîâ ôóíêöèè òðàòèòñÿ ìåñòî â ñòåêå âûçîâîâ ôóíêöèé è ìîæåò ïðîèçîéòè âûõîä çà ãðàíèöó ñåãìåíòà ïàìÿòè (Segmentation Fault).
Ñòåê âûçîâà ôóíêöèé:
fact(1)
fact(2)
fact(3) - ...
fact(4) – frame 2
fact(5) – frame 1
main() - frame 0
Íà êàæäîì ñëîå ñîäåðæèòñÿ èíôîðìàöèÿ î ïàðàìåòðàõ âûçîâà ôóíêöèè, çíà÷åíèÿ ëîêàëüíûõ ïåðåìåííûõ è àäðåñ âîçâðàòà.
Êîãäà ìåñòî â ñòåêå çàêîí÷èòñÿ, òî âñÿ èíôîðìàöèÿ áóäåò ïèñàòüñÿ ìèìî ñòåêà è ïîâåäåíèå ïðîãðàììû ñòàíåò íåêîððåêòíûì.
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 — ðåêóðñèÿ íå ðàáîòàëà :-)
Çàäà÷à ïðî îáõîä øàõìàòíîé äîñêè êîäîì êîíÿ.
|
28 |
19 |
|
|
6 |
|
|
|
|
|
|
5 |
|
|
|
7 |
|
|
18 |
27 |
20 |
|
|
|
|
|
|
21 |
4 |
|
|
|
|
|
8 |
|
|
17 |
26 |
3 |
|
9 |
|
|
|
25 |
22 |
|
|
|
|
13 |
10 |
|
16 |
|
2 |
23 |
14 |
11 |
|
|
|
1 |
24 |
15 |
|
|
|
|
12 |
1) Çàïîëíèòü âñþ òàáëèöó ÷èñëîì 0
2) Ðåàëèçîâàòü ôóíêöèþ «ñëåäóþùèé õîä» - èñêàòü âñå âîçìîæíûå õîäû (ìàêñèìóì 8), ïî î÷åðåäè (â öèêëå) ïèñàòü â ñîîòâåòñòâóþùóþ êëåòêó ñëåäóþùåå ÷èñëî è âûçûâàòü ñàìó ñåáÿ, ïîñëå âûçîâà ïðîâåðÿòü, çàêîí÷åí ëè ïóòü, è åñëè íåò, òî çàòèðàòü çàïèñàííîå ÷èñëî íóëåì.
Äåðåâî îáõîäà:
|
| |
| | | | | | | | | | | |
Ñïèðàëü Óëàìà (ïðîñòûå ÷èñëà îòìåòèòü çâåçäî÷êàìè):
7 8 9 10
6 1 2 11
5 4 3 12
14 13
Çàäà÷à 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 |
Ñëèâàåì ïî äâà ôðàãìåíòà â áÎëüøèé ôðàãìåíò, 2 → 4:
|
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 |
Ñëèâàåì ïî äâà ôðàãìåíòà â áÎëüøèé ôðàãìåíò, 4 → 8:
|
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 |
Ñëèâàåì ïî äâà ôðàãìåíòà â áÎëüøèé ôðàãìåíò, 8 → 16:
|
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 |
Ïîðÿäîê îäèíàêîâûõ ýëåìåíòîâ ïðè òàêîé ñîðòèðîâêå ñîõðàíÿåòñÿ, òàê êàê â ôóíêöèè merge() èç îäèíàêîâûõ ýëåìåíòîâ ñíà÷àëà äîáàâëÿåòñÿ ëåâûé (èç ìàññèâà a).
#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;
/* ??? copy(&b[beg], &a[beg], end – beg); */
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++);
}