Задачи - УПП, Седмица 12, 05.01.2024
GitHub classroom: classroom.github.com/a/KEDSxDjl
Във всички задачи трябва да използвате рекурсия!
Алтернативни задачи
§Считайте задачите от семинара и тези от миналия път като част от днешните задачи. Тоест, за хората които се затрудняват повечко, решете ги и след това се върнете тук. Разбира се, ще помагам и с тях.
Задача 1
§Имате някакъв брой предмети, като всеки предмет има ценност (число) и тежест (число пак). Искате в раница да сложите предмети, като целта е ценността да бъде максимална, обаче раницата има капацитет на тежест, тоест тази ценност трябва да бъде спрямо максималната обща тежест.
От входа получавате число N, след това толкова на брой предмета (тоест 2N на брой числа, като броейки от нула, четните са ценностти, а нечетните тежести). Накрая получавате максималната обща тежест за раницата. Трябва да изкарате на екрана максималната възможна обща ценност.
Примери:
| Вход | Изход |
|---|---|
| 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 |
Задача 2
§Получавате N и M, съответно броя редове и колони в дъска.
Всяка клетка от дъската е пълна или празна.
След това получавате NxM на брой символа за всяка клетка, като - означава празна клетка, докато # означава пълна.
Накрая получавате две числа - координати (започващи от нула, като 0,0 е горния-ляв ъгъл) в дъската.
От подадените координати трябва да запълните “фигурата” в която се намира (фигурата която огражда) дадената плочка. С други думи, представете си че дъската е изображение, всяка клетка е пиксел, в изображението има бели и черни пиксели, и на дадените координати е кликнато с “Bucket fill” за да се оцвети в черно дадена фигура.
Оцветяването да се случва само в 4те прави посоки (без диагонали).
Пример:
| Вход | Изход |
|---|---|
5 11- - # # - - - - - - -2 2 |
- - # # - - - - - - - |
Задача 3
§Имате шахматна дъска (8 на 8) и върху нея имате 8 царици. Напомням, че царицата в шаха може да се движи вертикално, хоризонтално и диагонално произволен брой клетки в един ход.
Интересуваме се от такова поставяне на всички царици, че нито една няма да вземе никоя друга царица в един ход. Пример:
Напишете програма, която намира броя на възможните такива поставяния на цариците. От входа не получавате нищо.
Пример:
| Вход | Изход |
|---|---|
| 92 |
Бонус: направете програмата да изкарва всяко решение
Задача 4
§Нормално ние представяме математически операции чрез “инфиксен” запис, тоест операторът е по средата, между нещата върху които работи (пример: 1 + 2).
Обаче, това не е задължително, по обратната полска нотация винаги слагаме оператът след нещата върху които работи (пример: 1 2 +).
Бонусът на това, е че не ни трябва скобуване и ред на операциите.
В инфиксния израз (2 + 3) * (2 ^^ 2), без скобите, сбора ще се извърши след умножението и степенуването ще се извърши след умножението.
Обаче, ако искаме да изразим това в обратен полски запис, просто правим 2 3 + 2 2 ^^ *.
А ако искаме оригиналното действие, без скоби, записваме 2 3 2 * 2 ^^ +.
Ако изглежда объркващо, идеята е че всеки оператор работи върху предходните две стойности, изчисляваме изразите от ляво надясно и заместваме веднага.
Тоест, при последния пример, пропускаме първите три числа, стигаме до *, умножаваме последните две и заместваме трите неща (3 2 *) с резултата, следователно имаме 2 6 2 ^^ +, пропускаме две, стигаме до ^^ и так.нат.
Направете програма, която чисто рекурсивно изчислиява изрази в обратен полски запис, който поддържа цели числа и операциите събиране, умножение, деление, изваждане и степенуване (за степенуване ще използваме знакът ^).
Обаче, за едно извикване на рекурсивната функция, може да пазите само един елемент на израза (число или оператор)!
Изразът винаги завършва на знака $.
Относно вход/изход, понеже няма как да знаем дали i-тата стойност е число или знак (операция), трябва да използваме функцията std::cin.fail(), която връща булева стойност, която ни казва дали записването на входа е било успешно.
Тоест, може винаги да запазвате входа в целочислен тип, когато стигнете до знак std::cin.fail() ще върне true.
След това трябва да “забравите” за грешката чрез std::cin.clear() и може втори път да запазите входа (провалените данни ще се препрочетат) в променлива от знаков тип.
Но това поражда друг проблем, понеже записваме в целочислен тип, когато въведем + или -, std::cin ще очаква това да е водещ знак на число, и ще продължи да чака входа докато не въведем друг знак, тоест + и - ще бъдат пропуснати.
Като компромисен вариант, просто пред тях винаги ще слагаме ' и в кода ще го пропускаме.
Примери:
| Вход | Изход |
|---|---|
| 1 2 '+ 3 / $ | 1 |
| 1 4 3 2 ^ * '+ 14 7 / '- $ | 35 |