Çàäà÷à
2. Îòñîðòèðîâàòü ýëåìåíòû ìàññèâà è îïðåäåëèòü, åñòü ëè â íåì
÷èñëî x
Çàäà÷à 1. Îòñîðòèðîâàòü ýëåìåíòû ìàññèâà ïî âîçðàñòàíèþ
Ïðèìåð 1:
1 2 7 3 4 5 6 8 9 10
Êàê îòñîðòèðîâàòü òàêîé ìàññèâ? Ïåðåñòàâèòü 7 âïðàâî íà 4 ìåñòà.
Åñëè ñäâèíóòü 3 4 6 7 âëåâî íà 1 ìåñòî, òî îíè îêàæóòñÿ íà ñâîèõ ìåñòàõ.
Ìåòîä «ïóçûðüêà». Ïóçûðåê ãàçà ïîäíèìàåòñÿ ñî äíà ñòàêàíà ââåðõ íà ïîâåðõíîñòü æèäêîñòè.
1 2 3 7 4 5 6 8 9 10
1 2 3 4 7 5 6 8 9 10
1 2 3 4 5 7 6 8 9 10
1 2 3 4 5 6 7 8 9 10
Ðåøàåì çàäà÷ó 1:
1) 9 ñðàâíåíèé è ïåðåñòàíîâîê:
10 9 8 7 6 5 4 3 2 1
9 10 8 7 6 5 4 3 2 1
9 8 10 7 6 5 4 3 2 1
…
9 8 7 6 5 4 3 2 1 10
2) 8 ñðàâíåíèé è ïåðåñòàíîâîê:
9 8 7 6 5 4 3 2 1 10
8 9 7 6 5 4 3 2 1 10
…
8 7 6 5 4 3 2 1 9 10
3)…
9)
2 1 3 4 5 6 7 8 9 10
…
1 2 3 4 5 6 7 8 9 10
Ñêîëüêî ðàç íàäî ýëåìåíò ïðîãíàòü ïî âñåìó ìàññèâó, ÷òîáû îí âñòàë íà ñâîå ìåñòî? 9 = 10 – 1
#include <stdio.h>
void sort(double ar[], int sz);
int main(void) {
double array[1000];
int i, size = 0;
FILE *IN, *OUT;
IN = fopen("input.txt", "r");
if (IN == NULL) {
printf("File not opened\n");
return -1;
}
/* while (fscanf(...) == 1) {
if (N >= 1000) { */
for (i = 0; i < 1000; i++) {
if (fscanf(IN, "%lf", &array[i]) != 1)
break;
++size;
}
fclose(IN);
sort(array, size); /* Èìÿ ìàññèâà == àäðåñ ìàññèâà */
OUT = fopen("output.txt", "w");
if (OUT == NULL) {
printf("File output.txt not opened\n");
return -1;
}
for (i = 0; i < size; i++) {
fprintf(OUT, "%lf\n", array[i]);
}
fclose(OUT);
return 0;
}
/* Ñîðòèðîâêà ìåòîäîì ïóçûðüêà */
void sort(double ar[], int sz) {
double tmp;
int i, j;
for (i = 0; i < sz - 1; i++) {
for (j = 0; j < sz - 1 - i; j++) {
if (ar[j] > ar[j+1]) {
tmp = ar[j];
ar[j] = ar[j+1];
ar[j+1] = tmp;
}
}
}
}
Ðåçóëüòàò âûïîëíåíèÿ:
Çàäà÷à
2. Îòñîðòèðîâàòü ýëåìåíòû ìàññèâà è îïðåäåëèòü, åñòü ëè â íåì
÷èñëî x
Ïîèñê ýëåìåíòà â îòñîðòèðîâàííîì ìàññèâå — ìåòîäîì äåëåíèÿ ïîïîëàì.
Begin = 0, end = 9
1 2 3 4 5 6 7 8 9 10
Èùåì ýëåìåíò 7. Ñåðåäèíà ìàññèâà — ýëåìåíò ñ èíäåêñîì 4 (èëè 5). middle = (0 + 9) / 2 = 4
Ýëåìåíò ñ èíäåêñîì 4 ðàâåí 5.
5 < 7 => 7 ìîæåò íàõîäèòüñÿ òîëüêî ñïðàâà îò 5, òî åñòü â ïðàâîé ïîëîâèíå ìàññèâà.
Begin = 4 + 1 = 5, end = 9, middle = (5 + 9) / 2 = 7
Ýëåìåíò ñ èíäåêñîì 7 ðàâåí 8. 8 > 7 => èùåì ñëåâà.
Begin = 5, end = 7 – 1 = 6, middle = (5 + 6) / 2 = 5
Ýëåìåíò ñ èíäåêñîì 5 ðàâåí 6. 6 < 7 => èùåì ñïðàâà.
Begin = 6, end = 6, middle = (6 + 6) / 2 = 6
Ýëåìåíò ñ èíäåêñîì 6 ðàâåí 7 => óñïåõ!!!
Åñëè áû ýëåìåíò áûë íå 7 (íàïðèìåð, 6.5), òî ÷òî äàëüøå?
Åñòü äâà âàðèàíòà, ÷òî äåëàòü äàëüøå:
1) Begin == end => ïîèñê ïðåêðàùàåì
èëè
2) Ïîïðîáîâàòü ïîèñêàòü ñïðàâà.
Begin 7, end = 6 – îòðåçîê âûðîæäåííûé => ïîèñê çàâåðøåí (íåóäà÷à).
#include <stdio.h>
void sort(double ar[], int sz);
int find(double ar[], int sz, double x);
int main(void) {
double array[1000], x;
int i, size = 0, found;
FILE *IN, *OUT;
IN = fopen("input.txt", "r");
if (IN == NULL) {
printf("File not opened\n");
return -1;
}
/* while (fscanf(...) == 1) {
if (N >= 1000) { */
for (i = 0; i < 1000; i++) {
if (fscanf(IN, "%lf", &array[i]) != 1)
break;
++size;
}
fclose(IN);
sort(array, size); /* Èìÿ ìàññèâà == àäðåñ ìàññèâà */
printf("Input number\n");
scanf("%lf", &x);
found = find(array, size, x);
printf("Found: %d\n", found);
return 0;
}
/* Ñîðòèðîâêà ìåòîäîì ïóçûðüêà */
void sort(double ar[], int sz) {
double tmp;
int i, j;
for (i = 0; i < sz - 1; i++) {
for (j = 0; j < sz - 1 - i; j++) {
if (ar[j] > ar[j+1]) {
tmp = ar[j];
ar[j] = ar[j+1];
ar[j+1] = tmp;
}
}
}
}
int find(double ar[], int sz, double x) {
int first = 0, last = sz, middle, i;
while (first + 1 < last) {
middle = (first + last) / 2;
if (ar[middle] == x)
return 1;
else if (x < ar[middle]) {
last = middle;
} else {
first = middle + 1;
}
}
if (first < last) {
return (ar[first] == x);
}
return 0;
}
Ðåçóëüòàò ðàáîòû ïðîãðàììû:
