diff options
| Commit | 2766c68912a2d463de1f5714569c2457c34d6215 (patch) | |
|---|---|---|
| Author | 2022-11-22 12:51:54 +0200 | |
| Committer | 2022-11-22 12:52:29 +0200 | |
| Files | 0a523542d830e7d6f16cc7b4a425d8ff47b9793b | |
| uni-projects-2766c68912a2d463de1f5714569c2457c34d6215.tar uni-projects-2766c68912a2d463de1f5714569c2457c34d6215.tar.gz uni-projects-2766c68912a2d463de1f5714569c2457c34d6215.zip | ||
| Parent | 59184db96d33777c4acd07f99d720a3133d4490e (diff) | |
[SDP/S03] Solved ex1 and ex2 from third seminar
1 files changed, 68 insertions, 0 deletions
| -rw-r--r-- | Year 2/Structures and data algorithms/03-Practicum-19.10.2022.cpp | 68 |
diff --git a/Year 2/Structures and data algorithms/03-Practicum-19.10.2022.cpp b/Year 2/Structures and data algorithms/03-Practicum-19.10.2022.cpp new file mode 100644 index 0000000..684bc63 --- /dev/null +++ b/Year 2/Structures and data algorithms/03-Practicum-19.10.2022.cpp @@ -0,0 +1,68 @@ +#include <iostream> +#include <queue> + +// Ex1 : Да се напише функция, която генерира всички двоични числа от 1 до n, използвайки опашка. + +void ex1() { + unsigned max = 0; + std::cin >> max; + + std::queue<uint> numbers, output; + numbers.push(1); + uint first; + for (unsigned i = 0; i < max; i++) { + first = numbers.front(); + numbers.pop(); + + output.push(first); + + numbers.push(first * 10); + numbers.push(first * 10 + 1); + } + + while (output.size() > 0) { + std::cout << output.front() << " "; + output.pop(); + } +} + +// Ex2: Конче стои върху шахматна дъска NxN. За начална и крайна позиция да се изведе с колко най - малко хода можем да стигнем от началната до крайната. + +void ex2() { + +} + +// Ex3: Даден е масив от цели числа. Представяме си, че имаме прозорец с дължина k който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец. + +void ex3() { + int numbers[] = {1, 3, -1, -3, 5, 3, 6, 7}; + int numLen = 8; + int k = 3; + + std::queue<int> window; + std::deque<int> maxes; + maxes.push_front(numbers[0]); + for (unsigned i = 0; i < k; i++) { + window.push(numbers[i]); + if (numbers[i] > maxes.front()) { + maxes.pop_front(); + maxes.push_front(numbers[i]); + } + } + + for (unsigned i = k; i < numLen; i++) { + window.pop(); + window.push(numbers[i]); + maxes.push_back((numbers[i] > maxes.back()) ? numbers[i] : maxes.back()); + } + + while(!maxes.empty()) { + std::cout << maxes.front() << " "; + maxes.pop_front(); + } +} + + +int main() { + ex3(); +} |
