/
main.cpp
154 lines (139 loc) · 5.44 KB
/
main.cpp
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
using namespace std;
void arrayExamples() {
int a[10] = {1, 2, 3, 4};
int b[10] = {1, 2, 3, 4};
cout << a[1] << endl;
// !!! cout << a[1000000] << endl;
// !!! a = b;
cout << (a == b) << endl;
cout << (a == a) << endl;
// !!! cin >> a;
cout << a << endl;
}
void testArrays() {
const int N = 100;
int a[N];
int n;
do {
cout << "Въведете брой на елементите: ";
cin >> n;
} while (n <= 0 || n > N);
for(int i = 0; i < n; i++) {
cout << "a[" << i << "] = ";
cin >> a[i];
}
int sum = 0;
for(int i = 0; i < n; i++)
sum += a[i];
cout << "Сумата на елементите е: " << sum << endl;
cout << "Въведете число за търсене: ";
int x;
cin >> x;
/* for е по-подходящ за задачи за всяко
for(int i = 0; i < n; i++)
if (a[i] == x)
cout << "Числото " << x << " се среща в масива";
*/
// цикъл за търсене
int i = 0;
// n == N, x не се среща в масива, тогава i == n, a[100]!!!
while(i < n && a[i] != x)
// инвариант: x не е равно на нито едно от a[0], a[1], ..., a[i]
i++;
// добър вариант (да): a[i] == x
// лош вариант (не): i >= n
cout << "Числото " << x;
if (i == n)
cout << " НЕ";
cout << " се среща в масива" << endl;
i = 0;
while (i < n - 1 && a[i] <= a[i+1])
i++;
// добър вариант (да): i == n - 1 (няма нарушение)
// лош вариант (не): a[i] > a[i+1] (има нарушение)
cout << "Редицата от елементите ";
if (i < n - 1)
cout << "НЕ ";
cout << "е монотонно растяща" << endl;
i = 0;
int j = 1;
while(i < n - 1 && a[i] != a[j]) {
// инвариант: ???
// сега трябва да проверим дали a[i] се среща в масива
// от a[i+1] нататък
j = i + 1;
while(j < n && a[i] != a[j])
// инвариант: a[i] не е равно на нито едно от a[0], a[1], ..., a[j]
j++;
//if (j == n) // не сме намерили съвпадение на a[i] с a[j] и трябва да продължим търсенето
i++;
}
// добър вариант (да): i == n - 1, по-добре дали j == n
// лош вариант (не): a[i] == a[j]
if (j == n)
cout << "Числата в редицата са различни" << endl;
else
cout << "В редицата има повтарящи се числа" << endl;
// сортиране по метода на пряката селекция
for(int i = 0; i < n - 1; i++) {
// инвариант: a[i] е първият елемент на неподредената част
// сега трябва да намерим най-малкия елемент на неподредената част
int imin = i;
for(int j = i + 1; j < n; j++)
// инвариант: ???
if (a[j] < a[imin])
imin = j;
// вече знаем, че imin е индексът на най-малкия елемент в неподредената част
// разменяме този елемент с първия елемент от неподредената част, a[i]
int tmp = a[i];
a[i] = a[imin];
a[imin] = tmp;
}
// можем да спрем при i == n - 1
for(int i = 0; i < n; i++)
cout << "a[" << i << "] = " << a[i] << endl;
}
int main() {
const int N = 100;
int a[N] = { 0 }, b[N] = { 0 };
int na, nb;
do {
cout << "Въведете брой на елементите в първия масив: ";
cin >> na;
} while (na <= 0 || na > N);
for(int i = 0; i < na; i++) {
cout << "a[" << i << "] = ";
cin >> a[i];
}
do {
cout << "Въведете брой на елементите във втория масив: ";
cin >> nb;
} while (nb <= 0 || nb > N);
for(int i = 0; i < nb; i++) {
cout << "b[" << i << "] = ";
cin >> b[i];
}
// считаме, че елементите им са подредени в нарастващ ред
int c[2*N];
int i = 0, j = 0, k = 0;
while (i < na && j < nb) // докато и в двата масива има още необработени елементи
// инвариант: k е първият незаписан индекс в c и ... ???
if (a[i] < b[j])
// ще вземем от a
c[k++] = a[i++];
else
// ще вземем от b
c[k++] = b[j++];
// i == na || j == nb
// трябва да прехвърлим останалите елементи
// a е свършил, трябва да прехвърлим оставащите от b
while(j < nb)
c[k++] = b[j++];
// b е свършил, трябва да прехвърлим оставащите от a
while(i < na)
c[k++] = a[i++];
for(int i = 0; i < na + nb; i++)
cout << "c[" << i << "] = " << c[i] << endl;
return 0;
}