Задачи - УПП, Седмица 11, 22.12.2023
GitHub classroom: classroom.github.com/a/cZRnZj9y
Във всички задачи трябва да използвате рекурсия!
Някои задачи се повтарят с тези от миналия път, ако преди не сте ги решили, сега ги решете
Алтернативни задачи
§Считайте задачите от семинара като задачи преди тези. Тоест, за хората които се затрудняват повечко, решете семинарните и след това се върнете тук. Разбира се, ще помагам и със семинарните задачи.
Задача 1
§От входа получавате неотрицателно число N, което ще бъде някое число на Фибоначи.
Трябва да върнете кое по ред е, като 0 е нулевото, 1 е първото, 2 е третото, 3 е четвъртото и так. нат.
Напомням, че нормално Фибоначи се дефинира като редица, която започва с числата 0 и 1, и всяко следващо е сумата на предходните две.
Тоест, нулевото число е 0, първото 1, второто е 0 + 1 = 1 (понеже 1 се повтаря, зачитаме го за първото число), третото е 1 + 1 = 2, четвъртото е 1 + 2 = 3 и так. нат.
Примери:
| Вход | Изход |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 3 | 4 |
| 144 | 12 |
| 1597 | 17 |
| 46368 | 24 |
Задача 2
§От входа получавате положително число N, трябва да изкарате на екрана “рисунка” на триъгълници.
a) горен триъгълник
§Рисунката е един правоъгълен равнобедрен триъгълник от знака +, като N определя размера на равнобедрените страни (вижте примерите).
Примери:
| Вход | Изход |
|---|---|
| 1 | + |
| 2 | + |
| 3 | + |
| 5 | + |
б) долен триъгълник
§Подобно на предходната подточка, обаче обърнат по хоризонтала, и със знака #.
Примери:
| Вход | Изход |
|---|---|
| 1 | # |
| 2 | ## |
| 3 | ### |
| 5 | ##### |
в) пълен триъгълник
§Използвайки само една рекурсивна функция, сега трябва да изкарате първо горния триъгълник и след това долния. Ако просто извикате предходните две функции една след друга, задачата се обезсмисля.
Примери:
| Вход | Изход |
|---|---|
| 1 | + |
| 2 | + |
| 3 | + |
| 5 | + |
Задача 3
§Направете програма която разрешава проблема с възрастта на трите деца.
Една жена има три деца за които знаем три неща: умножението на техните възрасти, сбора на техните възрасти и факта, че има едно дете, което е най-голямо. Трябва да намерите възрастта на всяко дете, само по тази информация.
Разбира се, от входа получавате две числа, съответно умножението и сбора на възрастите им. Трябва на екрана да изкарате три числа - възрастите на трите деца.
Подсказка: най-лесното решение е да пробвате всички възможни възрасти, като избягвате техни пермутации
Примери:
| Вход | Изход |
|---|---|
| 72 14 | 3 3 8 |
| 36 13 | 2 2 9 |
| 350 42 | 2 5 35 |
Задача 4
§От входа получавате число N, след това трябва да изкарате на нови редове, в нарастващ ред, всички двоични числа, които могат да се представят с N-бита.
Вкарвате и водещи нули, тоест всяко число е съставено от точно N букви (N нули и единици).
Примери:
| Вход | Изход |
|---|---|
| 1 | 0 1 |
| 2 | 00 01 10 11 |
| 3 | 000 001 010 011 100 101 110 111 |
| 4 | 0000 0001 … 0111 1000 1001 … 1101 1110 1111 |
Задача 5
§Направете програма която разрешава Такузо пъзели.
Започвате с дъска 4х4, в тази дъска може да имате само цифрите 0 и 1, като няколко клетки вече идват с попълнени стойности (но повечето са празни). Обаче, на всяка колона и ред трябва да има еднакъв брой 0ли и 1ци, и не трябва да има повече от две последователни еднакви цифри (в реда или колоната).
От входа получавате дъската, като с -1 обозначаваме празна клетка.
Примери:
| Вход | Изход |
|---|---|
| -1 1 -1 0 -1 -1 0 -1 -1 0 -1 -1 1 1 -1 0 |
0 1 1 0 1 0 0 1 0 0 1 1 1 1 0 0 |
| -1 0 1 -1 1 -1 0 -1 0 1 -1 -1 0 0 1 -1 |
1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 |
| -1 0 -1 -1 -1 0 0 -1 0 -1 -1 -1 -1 -1 -1 0 |
0 0 1 1 1 0 0 1 0 1 1 0 1 1 0 0 |