Çàäà÷à 1. Öèêëè÷åñêè ñäâèíóòü ìàññèâ íà k ýëåìåíòîâ âïðàâî
(íåëüçÿ ïîëüçîâàòüñÿ äîïîëíèòåëüíûìè ìàññèâàìè)
Ïðèìåð. N = 10
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Äëÿ k = 2:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
9 |
10 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
3 ñïîñîáà ðåøåíèÿ:
Ñïîñîá 0. k ðàç ñäâèíóòü íà 1 ýëåìåíò âïðàâî. Ìîæåò îêàçàòüñÿ î÷åíü äîëãî ðàáîòàþùèì. Åñëè ÷èñåë 1 ìèëëèîí, à ñäâèíóòü íàäî íà 100 òûñÿ÷, òî ïîëó÷àåòñÿ 1000000 * 100000 îïåðàöèé = 100000000000 — 100 ìèëëèàðäîâ îïåðàöèé.
Ñïîñîá 1. (1 ìèëëèîí îïåðàöèé)
buf = ar[0];
ar[0] = ar[8]; /* 0 – 2 – èíäåêñ ýëåìåíòà, êîòîðûé íàäî çàïèñàòü íà ìåñòî 0-ãî. ×òîáû íàéòè èíäåêñà â ìàññèâà, âû÷èñëÿåì îñòàòîê îò äåëåíèÿ (0-2) íà 10. (0-2)%10 = 8. cur = 0, next = 8 */
ar[8] = ar[6]; /* cur = 8, next = 6 */
ar[6] = ar[4]; /* cur = 6, next = 4 */
ar[4] = ar[2]; /* cur = 4, next = 2 */
ar[2] = buf; /* cur = 2, next = 0 */
Öèêëè÷åñêè ñäâèíóëè 5 ýëåìåíòîâ. Ïîëó÷èëàñü îðáèòà, íà êîòîðîé âðàùàþòñÿ 5 ýëåìåíòîâ èç 10 (ïîòîìó, ÷òî 10 äåëèòñÿ íà 2 íàöåëî).
buf = ar[1];
ar[1] = ar[9];
ar[9] = ar[7];
ar[7] = ar[5];
ar[5] = ar[3];
ar[3] = buf;
Ñäâèíóëè åùå 5 ýëåìåíòîâ.
Åñëè ìû ñ÷èòàåì ñäâèãè, òî íàñ÷èòàëè 10 ñäâèãîâ. Ýòîãî äîñòàòî÷íî.
#include <stdio.h>
void shiftRight(double ar[], int N, int k);
int main() {
int N, k, i;
double array[100]; /* = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; */
for (i = 0; i < 100; i++)
array[i] = i + 1;
printf("Input N and k\n");
scanf("%d%d", &N, &k);
if (N > sizeof(array)/sizeof(array[0])) {
printf("Too big N\n");
return -1;
}
shiftRight(array, N, k);
for (i = 0; i < N; i++)
printf("%lf ", array[i]);
printf("\n");
return 0;
}
void shiftRight(double ar[], int N, int k) {
int start = 0; /* Start element for shifting orbit */
int cur; /* Index of current element to which to write cur - k */
int next; /* Index of the element which we write to the place of cur */
double buf;
int i;
cur = start;
buf = ar[start];
for (i = 0; i < N; i++) {
/* Ñäâèã âíóòðè îäíîé îðáèòû */
next = (cur - k + N) % N;
if (next == start)
ar[cur] = buf; /* Äîïèñûâàåì ñòàðóþ îðáèòó */
else
ar[cur] = ar[next];
cur = next;
if (next == start) { /* Ïðîøëè âñþ îðáèòó, íàäî ïåðåéòè ê ñëåäóþùåé */
++start;
cur = start;
buf = ar[start];
}
}
}
×òî, åñëè N è k – âçàèìíî ïðîñòûå? Ìû ïðîõîäèì ïî âñåìó ìàññèâó çà îäíó îðáèòó (ïåðåõîä íà äðóãóþ îðáèòó — ëèøíèé êîä, îí íå ïîíàäîáèòñÿ)
Ïðèìåð: N = 7, k = 3 (èíäåêñû 0, 1, 2, 3, 4, 5, 6)
start = 0;
cur = 0;
ar[0] = ar[4];
ar[4] = ar[1];
ar[1] = ar[5];
ar[5] = ar[2];
ar[2] = ar[6];
ar[6] = ar[3];
ar[3] = buf;
Ñïîñîá 2.
Äàíî:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Íàäî:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
9 |
10 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Ìîæíî çàìåòèòü, ÷òî ÷àñòè ìàññèâà ñèììåòðè÷íî îòîáðàæàþòñÿ ïðè ñäâèãå: îñåâàÿ ñèììåòðèÿ îòíîñèòåëüíî ñåðåäèíû ìàññèâà
Íî ïðè ñèììåòðèè ìåíÿåòñÿ ïîðÿäîê ýëåìåíòîâ:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
Çàìå÷àåì, ÷òî ïðàâèëüíûé ïîðÿäîê ìîæíî âîññòàíîâèòü ïðåîáðàçîâàíèåì ñèììåòðèè îòíîñèòåëüíî ñåðåäèí ýòèõ ÷àñòåé. Ïðèìåíÿåì ñèììåòðèþ â ðîçîâîé ÷àñòè îòíîñèòåëüíî åå ñåðåäèíû (ãðàíèöà 0-ãî è 1-ãî ýëåìåíòîâ) è â çåëåíîé ÷àñòè îòíîñèòåëüíî åå ñåðåäèíû (ãðàíèöà 5-ãî è 6-ãî ýëåìåíòîâ).
#include <stdio.h>
void mirror(double *array, int size); /* ïåðâûé àðãóìåíò — àäðåñ */
void shiftRight(double ar[], int N, int k);
void mirror(double *array, int size) {
double buffer;
int i;
for (i = 0; i < size/2; i++) {
/* îáìåíèâàåì çíà÷åíèÿ äâóõ ýëåìåíòîâ ìàññèâà: i-ãî è ñèììåòðè÷íîãî åìó */
buffer = array[i];
array[i] = array[size – 1 – i]; /* size – 1 – èíäåêñ ïîñëåäíåãî ýëåìåíòà */
array[size – 1 – i] = buffer;
}
}
void shiftRight(double ar[], int N, int k) {
mirror(ar, N);
mirror(ar, k);
mirror(&ar[k], N-k);
}
int main(void) {
double array[100];
int i;
for (i = 0; i < 100; i++) {
array[i] = i;
}
mirror(array, 100);
for (i = 0; i < 100; i++) {
printf("%lf ", array[i]);
}
printf("\n");
return 0;
}
Ðåçóëüòàò âûïîëíåíèÿ:
Ìàññèâ ðàçìåðà, êîòîðûé íåèçâåñòåí çàðàíåå (âî âðåìÿ íàïèñàíèÿ ïðîãðàììû).
×òî äåëàòü?
Èñïîëüçîâàòü ôóíêöèþ çàõâàòà ïàìÿòè malloc(<ñêîëüêî áàéòîâ ïàìÿòè>) (Memory ALLOCation). Ôóíêöèÿ malloc() âîçâðàùàåò àäðåñ çàõâà÷åííîé ïàìÿòè èëè NULL, åñëè íå óäàëîñü çàõâàòèòü ïàìÿòü.
Ïîñëå èñïîëüçîâàíèÿ ýòîé ïàìÿòè åå íàäî îñâîáîäèòü ïðè ïîìîùè ôóíêöèè free(<àäðåñ çàõâà÷åííîé ïàìÿòè>).
Åñòü ïóë (pool) ñâîáîäíîé ïàìÿòè. Êîãäà çàõâàòûâàåì ïàìÿòü â êàêîì-òî êîëè÷åñòâå áàéòîâ, òî âûäåëÿåòñÿ ñòåïåíü äâîéêè áàéòîâ ïàìÿòè è èíôîðìàöèÿ îá ýòî ó÷àñòêå (àäðåñ è êîëè÷åñòâî áàéòîâ) ñîõðàíÿåòñÿ â äèñïåò÷åðå ïàìÿòè.
Òðóäíîñòè:
1. Âûçîâ ôóíêöèè malloc() òðåáóåò çíà÷èòåëüíûõ ðåñóðñîâ (íàïðèìåð, âðåìåíè).
2. Åñëè íå îñâîáîäèòü çàõâà÷åííóþ ïàìÿòü, òî ïóë ñâîáîäíîé ïàìÿòè ìîæåò îêàçàòüñÿ èñ÷åðïàííûì è ïðîãðàììà áîëüøå íå ñìîæåò çàõâàòûâàòü ïàìÿòü è, òàêèì îáðàçîì, ïðîäîëæàòü ðàáîòó. Ñèòóàöèÿ, êîãäà çàõâà÷åííàÿ ïàìÿòü íå îñâîáîæäàåòñÿ, íàçûâàåòñÿ óòå÷êà ïàìÿòè (memory leak).
Çàäà÷à 2.  ôàéëå input.txt íàõîäÿòñÿ ÷èñëà. Èõ íàäî îòñîðòèðîâàòü è âûâåñòè ðåçóëüòàò â ôàéë output.txt.
×èñëà ïðåäâàðèòåëüíî ïåðåñ÷èòàòü è çàõâàòèòü äëÿ íèõ îäèí ìàññèâ ïàìÿòè.
#include <stdio.h>
#include <stdlib.h>
void sort(double *array, int N);
/* void sort(double array[], int N); */
int main(void) {
FILE *IN, *OUT;
double x, *array;
int N = 0, i;
IN = fopen("input.txt", "r");
if (IN == NULL) {
printf("File not opened\n");
return -1;
}
while (fscanf(IN, "%lf", &x) == 1) {
++N;
}
fclose(IN);
if (N == 0) {
printf("File is empty\n");
return -1;
}
IN = fopen("input.txt", "r");
if (IN == NULL) {
printf("File not opened\n");
return -1;
}
/* (double*) - ÿâíîå ïðåîáðàçîâàíèå òèïà ê double* */
array = (double*)malloc(N * sizeof(double)); /* sizeof(double) - returns number of bytes in double variables */
if (array == NULL) {
printf("Not enough memory\n");
fclose(IN);
return -1;
}
for (i = 0; i < N; i++) {
if (fscanf(IN, "%lf", &array[i]) != 1) {
printf("Missed numbers\n");
fclose(IN);
free(array);
return -1;
}
}
fclose(IN);
sort(array, N);
OUT = fopen("output.txt", "w");
if (OUT == NULL) {
printf("File output.txt not opened\n");
return -1;
}
for (i = 0; i < N; i++) {
fprintf(OUT, "%lf ", array[i]);
}
fclose(OUT);
free(array);
return 0;
}
void sort(double *array, int N) {
double buf;
int i, j;
for (j = 0; j < N; j++) {
for (i = 0; i < N - 1; i++) {
if (array[i] > array[i+1]) {
buf = array[i];
array[i] = array[i+1];
array[i+1] = buf;
}
}
}
}