# Задачи - УПП, Седмица 11, 22.12.2023

\n

GitHub classroom: [url https://classroom.github.com/a/cZRnZj9y classroom.github.com/a/cZRnZj9y]

.important Във всички задачи =[трябва]= да използвате рекурсия!

.warn Някои задачи се повтарят с тези от миналия път, ако преди не сте ги решили, сега ги решете

## Алтернативни задачи

Считайте [url https://github.com/ivanahristova/introduction-to-programming-2023-2024/tree/main/sem11#%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8 задачите от семинара] като задачи преди тези.
Тоест, за хората които се затрудняват повечко, решете семинарните и след това се върнете тук.
Разбира се, ще помагам и със семинарните задачи.

## Задача 1

От входа получавате неотрицателно число `[N]`, което ще бъде някое число на Фибоначи.
Трябва да върнете кое по ред е, като 0 е нулевото, 1 е първото, 2 е третото, 3 е четвъртото и так. нат.

Напомням, че нормално Фибоначи се дефинира като редица, която започва с числата 0 и 1, и всяко следващо е сумата на предходните две.
Тоест, нулевото число е 0, първото 1, второто е `[0 + 1 = 1]` (понеже 1 се повтаря, зачитаме го за първото число), третото е `[1 + 1 = 2]`, четвъртото е `[1 + 2 = 3]` и так. нат.

=[Примери:]=

.table
|=Вход=||=Изход=|
|:0    :||:0   :|
|:1    :||:1   :|
|:3    :||:4   :|
|:144  :||:12  :|
|:1597 :||:17  :|
|:46368:||:24  :|

## Задача 2

От входа получавате положително число `[N]`, трябва да изкарате на екрана "рисунка" на триъгълници.

### a) горен триъгълник

Рисунката е един правоъгълен равнобедрен триъгълник от знака `[+]`, като `[N]` определя размера на равнобедрените страни (вижте примерите).

=[Примери:]=

.table
|=Вход=||=Изход=|
|:1   :||:<pre>+</pre>:|
|:2   :||:<pre>+\n++</pre>:|
|:3   :||:<pre>+\n++\n+++</pre>:|
|:5   :||:<pre>+\n++\n+++\n++++\n+++++</pre>:|

### б) долен триъгълник

Подобно на предходната подточка, обаче обърнат по хоризонтала, и със знака `[#]`.

=[Примери:]=

.table
|=Вход=||=Изход=|
|:1   :||:<pre>#</pre>:|
|:2   :||:<pre>##\n#</pre>:|
|:3   :||:<pre>###\n##\n#</pre>:|
|:5   :||:<pre>#####\n####\n###\n##\n#</pre>:|

### в) пълен триъгълник

=[Използвайки само една рекурсивна функция,]= сега трябва да изкарате първо горния триъгълник и след това долния.
Ако просто извикате предходните две функции една след друга, задачата се обезсмисля.

=[Примери:]=

.table
|=Вход=||=Изход=|
|:1   :||:<pre>+\n#</pre>:|
|:2   :||:<pre>+\n++\n##\n#</pre>:|
|:3   :||:<pre>+\n++\n+++\n###\n##\n#</pre>:|
|:5   :||:<pre>+\n++\n+++\n++++\n+++++\n#####\n####\n###\n##\n#</pre>:|

## Задача 3

Направете програма която разрешава проблема с [url https://en.wikipedia.org/wiki/Ages_of_Three_Children_puzzle възрастта на трите деца].

Една жена има три деца за които знаем три неща: умножението на техните възрасти, сбора на техните възрасти и факта, че има едно дете, което е най-голямо.
Трябва да намерите възрастта на всяко дете, само по тази информация.

Разбира се, от входа получавате две числа, съответно умножението и сбора на възрастите им.
Трябва на екрана да изкарате три числа - възрастите на трите деца.

=[Подсказка:]= най-лесното решение е да пробвате всички възможни възрасти, като избягвате техни пермутации

=[Примери:]=

.table
|=Вход=||=Изход=|
|:72 14:||:3 3 8:|
|:36 13:||:2 2 9:|
|:350 42:||:2 5 35:|

## Задача 4

От входа получавате число `[N]`, след това трябва да изкарате на нови редове, в нарастващ ред, всички двоични числа, които могат да се представят с `[N]`-бита.
Вкарвате и водещи нули, тоест всяко число е съставено от точно `[N]` букви (`[N]` нули и единици).

=[Примери:]=

.table
|=Вход=||=Изход=|
|:1   :||:0\n1:|
|:2   :||:00\n01\n10\n11:|
|:3   :||:000\n001\n010\n011\n100\n101\n110\n111:|
|:4   :||:0000\n0001\n...\n0111\n1000\n1001\n...\n1101\n1110\n1111:|

## Задача 5

Направете програма която разрешава [url https://en.wikipedia.org/wiki/Takuzu Такузо пъзели].

Започвате с дъска 4х4, в тази дъска може да имате само цифрите 0 и 1, като няколко клетки вече идват с попълнени стойности (но повечето са празни).
Обаче, на всяка колона и ред трябва да има еднакъв брой 0ли и 1ци, и не трябва да има повече от две последователни еднакви цифри (в реда или колоната).

От входа получавате дъската, като с -1 обозначаваме празна клетка.

=[Примери:]=

.table
|=Вход=||=Изход=|
|:-1 1 -1 0\n-1 -1 0 -1\n-1 0 -1 -1\n1 1 -1 0:||:0 1 1 0\n1 0 0 1\n0 0 1 1\n1 1 0 0:|
|:-1 0 1 -1\n1 -1 0 -1\n0 1 -1 -1\n0 0 1 -1:||:1 0 1 0\n1 1 0 0\n0 1 0 1\n0 0 1 1:|
|:-1 0 -1 -1\n-1 0 0 -1\n0 -1 -1 -1\n-1 -1 -1 0:||:0 0 1 1\n1 0 0 1\n0 1 1 0\n1 1 0 0:|