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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
#include <iostream>
// Задача първа:
// Напишете функция filter, която приема масив от цели числа, дължината му и
// булева функция с един аргумент цяло число. В масива, елементите които не
// изпълняват условието на булевата функция променят стойността си на -1.
// Пример:
//
// #include <iostream>
// bool isEven(int n) {
// return (n % 2) == 0;
// }
// void filter(array, length, predicate) {
// ...
// }
// int main() {
// int arr[] = {1, 2, 3, 4, 5};
// filter(arr, 5, isEven);
// for(int i = 0; i < 5; i++){
// std::cout << arr[i] << " ";
// }
// }
// Изход: -1 2 -1 4 -1
bool isEven(int n) {
return (n % 2) == 0;
}
void filter(int *array, int length, bool (predicate)(int)) {
if (length == 0) return;
if(!predicate(array[0]))
array[0] = -1;
filter(array + 1, length - 1, predicate);
}
void ex1() {
int arr[] = {1, 2, 3, 4, 5};
filter(arr, 5, isEven);
for(int i = 0; i < 5; i++){
std::cout << arr[i] << " ";
}
}
// Задача втора:
// Напишете функция map, която приема масив от цели числа, дължината му и
// функция, която приема число по референция, и приложете функцията върху всеки
// елемент на масива.
// Пример:
// #include <iostream>
// int plusFive(int& n){
// n += 5;
// }
// void map(array, length, func) {
// ...
// }
// int main() {
// int arr[] = {1, 2, 3, 4, 5};
// map(arr, 5, plusFive);
// for(int i = 0; i < 5; i++){
// std::cout << arr[i] << " ";
// }
// }
// Изход: 6 7 8 9 10
void plusFive(int& n){
n += 5;
}
void map(int *array, int length, void (func)(int&)) {
if (length == 0) return;
func(array[0]);
map(array + 1, length - 1, func);
}
void ex2() {
int arr[] = {1, 2, 3, 4, 5};
map(arr, 5, plusFive);
for(int i = 0; i < 5; i++){
std::cout << arr[i] << " ";
}
}
// Задача трета:
// Да се дефинира рекурсивна функция, която заменя всяко срещане на цифрата 5 в
// дадено неотрицателно цяло число с 8.
int replFives(int n) {
return (n == 5) ? 8 : n;
}
int modifyNum(int n, int (modifier)(int)) {
int curr = modifier(n % 10);
if (n == 0) return 0;
return modifyNum(n / 10, modifier) * 10 + curr;
}
void ex3() {
int n = 52553847;
std::cout << modifyNum(n, replFives) << std::endl;
}
// Задача четвърта:
// Да се напише рекурсивна функция, която извършва двоично търсене в
// предварително сортиран масив от цели числа.
int binarySearch(int *arr, int len, int elem) {
if (len == 0) return -1;
if (arr[len / 2] == elem)
return len / 2;
else if (arr[len / 2] < elem)
return binarySearch(arr + (len / 2 + 1), len / 2, elem) + (len / 2 + 1);
else
return binarySearch(arr, len / 2, elem);
}
void ex4() {
int nums[] = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 101 };
std::cout << binarySearch(nums, 11, 16) << std::endl;
}
// Задача пета:
// Имаме лабиринт, с размери nхm, в който проходимите клетки се бележат с 0 а
// непроходимите с 1. Да се напише програма, която проверява дали съществува път
// от подадени като аргументи начална и крайна точка.
bool insideBoundaries(int x, int y, int n, int m) {
return x >= 0 && y >= 0 && x < n && y < m;
}
bool pathExists(int lab[][4], int n, int m, int stX, int stY, int endX, int endY) {
if (stX == endX && stY == endY)
return true;
bool res = false;
if (insideBoundaries(stX + 1, stY, n, m) && lab[stX + 1][stY] == 0) {
lab[stX][stY] = 2;
res = pathExists(lab, n, m, stX + 1, stY, endX, endY);
lab[stX][stY] = 0;
}
if (res) return true;
if (insideBoundaries(stX, stY + 1, n, m) && lab[stX][stY + 1] == 0) {
lab[stX][stY] = 2;
res = pathExists(lab, n, m, stX, stY + 1, endX, endY);
lab[stX][stY] = 0;
}
if (res) return true;
if (insideBoundaries(stX - 1, stY, n, m) && lab[stX - 1][stY] == 0) {
lab[stX][stY] = 2;
res = pathExists(lab, n, m, stX - 1, stY, endX, endY);
lab[stX][stY] = 0;
}
if (res) return true;
if (insideBoundaries(stX, stY - 1, n, m) && lab[stX][stY - 1] == 0) {
lab[stX][stY] = 2;
res = pathExists(lab, n, m, stX, stY - 1, endX, endY);
lab[stX][stY] = 0;
}
return res;
}
void ex5() {
int lab[][4] = {
{ 0, 1, 1, 1 },
{ 0, 1, 0, 1 },
{ 0, 0, 0, 1 },
{ 1, 1, 0, 1 },
{ 0, 0, 0, 1 }
};
std::cout << pathExists(lab, 5, 4, 0, 0, 4, 0) << std::endl;
}
// Задача шеста:
// Дадена е квадратна матрица с размери n x m от цели числа. Да се намери пътят от
// горния ляв ъгъл до долния десен ъгъл с най - голяма сума от елементите, като
// имаме право да се движим само надолу и надясно.
int main() {
ex5();
}
|
