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
|
# Задачи - УПП, Седмица 12, 05.01.2024
\n
GitHub classroom: [url https://classroom.github.com/a/KEDSxDjl classroom.github.com/a/KEDSxDjl]
.important Във всички задачи [=трябва=] да използвате рекурсия!
## Алтернативни задачи
Считайте [url https://github.com/ivanahristova/introduction-to-programming-2023-2024/tree/main/sem12 задачите от семинара] и [url ../week11/ тези от миналия път] като част от днешните задачи.
Тоест, за хората които се затрудняват повечко, решете ги и след това се върнете тук.
Разбира се, ще помагам и с тях.
## Задача 1
Имате някакъв брой предмети, като всеки предмет има ценност (число) и тежест (число пак).
Искате в раница да сложите предмети, като целта е ценността да бъде максимална, обаче раницата има капацитет на тежест, тоест тази ценност трябва да бъде спрямо максималната обща тежест.
От входа получавате число N, след това толкова на брой предмета (тоест 2N на брой числа, като броейки от нула, четните са ценностти, а нечетните тежести).
Накрая получавате максималната обща тежест за раницата.
Трябва да изкарате на екрана максималната възможна обща ценност.
[=Примери:=]
:table_2
|= Вход
|= Изход
|:
```
3
1 4
2 5
3 1
4
|: 3
|:
```
3
1 4
2 5
3 6
3
|: 0
|:
```
6
50 56
50 59
64 80
46 64
50 75
5 17
190
|: 150
.comment https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html
## Задача 2
Получавате N и M, съответно броя редове и колони в дъска.
Всяка клетка от дъската е пълна или празна.
След това получавате NxM на брой символа за всяка клетка, като [`-`] означава празна клетка, докато [`#`] означава пълна.
Накрая получавате две числа - координати (започващи от нула, като 0,0 е горния-ляв ъгъл) в дъската.
От подадените координати трябва да запълните "фигурата" в която се намира (фигурата която огражда) дадената плочка.
С други думи, представете си че дъската е изображение, всяка клетка е пиксел, в изображението има бели и черни пиксели, и на дадените координати е кликнато с "Bucket fill" за да се оцвети в черно дадена фигура.
Оцветяването да се случва само в 4те прави посоки (без диагонали).
[image https://upload.wikimedia.org/wikipedia/commons/7/7e/Recursive_Flood_Fill_4_%28aka%29.gif]
[=Пример:=]
:table_2
|= Вход
|= Изход
|:
```
5 11
- - # # - - - - - - -
- # - - # - - - - - -
\# - - - - # # # # # #
- # - - # - - - # - #
- - # # - - - - - - -
2 2
|:
```
- - # # - - - - - - -
- # # # # - - - - - -
\# # # # # # # # # # #
- # # # # - - - # - #
- - # # - - - - - - -
## Задача 3
Имате шахматна дъска (8 на 8) и върху нея имате 8 царици.
Напомням, че царицата в шаха може да се движи вертикално, хоризонтално и диагонално произволен брой клетки в един ход.
Интересуваме се от такова поставяне на всички царици, че нито една няма да вземе никоя друга царица в един ход.
Пример:
[image https://upload.wikimedia.org/wikipedia/commons/6/69/Solution_A_for_8_Queen_Puzzles.png]
Напишете програма, която намира броя на възможните такива поставяния на цариците.
От входа не получавате нищо.
[=Пример:=]
:table_2
|= Вход
|= Изход
|:
|: 92
[=Бонус:=] направете програмата да изкарва всяко решение
## Задача 4
.comment https://mathcenter.oxford.emory.edu/site/cs171/probSetUsingStacks/
Нормално ние представяме математически операции чрез "инфиксен" запис, тоест операторът е по средата, между нещата върху които работи (пример: [`1 + 2`]).
Обаче, това не е задължително, по обратната полска нотация винаги слагаме оператът след нещата върху които работи (пример: [`1 2 +`]).
Бонусът на това, е че не ни трябва скобуване и ред на операциите.
В инфиксния израз [`(2 + 3) * (2 ^^ 2)`], без скобите, сбора ще се извърши след умножението и степенуването ще се извърши след умножението.
Обаче, ако искаме да изразим това в обратен полски запис, просто правим [`2 3 + 2 2 ^^ *`].
А ако искаме оригиналното действие, без скоби, записваме [`2 3 2 * 2 ^^ +`].
Ако изглежда объркващо, идеята е че всеки оператор работи върху предходните две стойности, изчисляваме изразите от ляво надясно и заместваме веднага.
Тоест, при последния пример, пропускаме първите три числа, стигаме до [`*`], умножаваме последните две и заместваме трите неща ([`3 2 *`]) с резултата, следователно имаме [`2 6 2 ^^ +`], пропускаме две, стигаме до [`^^`] и так.нат.
Направете програма, която чисто рекурсивно изчислиява изрази в обратен полски запис, който поддържа цели числа и операциите събиране, умножение, деление, изваждане и степенуване (за степенуване ще използваме знакът [`^`]).
.important Обаче, за едно извикване на рекурсивната функция, може да пазите само един елемент на израза (число или оператор)!
Изразът винаги завършва на знака [`$`].
:warn
.p
Относно вход/изход, понеже няма как да знаем дали i-тата стойност е число или знак (операция), трябва да използваме функцията [`std::cin.fail()`], която връща булева стойност, която ни казва дали записването на входа е било успешно.
.p
Тоест, може винаги да запазвате входа в целочислен тип, когато стигнете до знак [`std::cin.fail()`] ще върне [`true`].
След това трябва да "забравите" за грешката чрез [`std::cin.clear()`] и може втори път да запазите входа (провалените данни ще се препрочетат) в променлива от знаков тип.
.p
Но това поражда друг проблем, понеже записваме в целочислен тип, когато въведем [`+`] или [`-`], [`std::cin`] ще очаква това да е водещ знак на число, и ще продължи да чака входа докато не въведем друг знак, тоест [`+`] и [`-`] ще бъдат пропуснати.
Като компромисен вариант, просто пред тях винаги ще слагаме [`'`] и в кода ще го пропускаме.
[=Примери:=]
:table_2
|= Вход
|= Изход
|: 1 2 '+ 3 / $
|: 1
|: 1 4 3 2 ^ * '+ 14 7 / '- $
|: 35
## Attribution
.bulleted
- Анимация в [url #2 Задача 2] от André Karwath (Aka) на [url https://commons.wikimedia.org/w/index.php?curid=481651 Уикипедия] под лиценз CC BY-SA 2.5
- Изображение на шахматна дъска в [url #3 Задача 3] от Encik Tekateki в [url https://commons.wikimedia.org/w/index.php?curid=77832290 Уикипедия] под лиценз CC BY-SA 4.0
|
