# Задачи - УПП, Седмица 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_2 |= Вход |= Изход |: 0 |: 0 |: 1 |: 1 |: 3 |: 4 |: 144 |: 12 |: 1597 |: 17 |: 46368 |: 24 ## Задача 2 От входа получавате положително число [`N`], трябва да изкарате на екрана "рисунка" на триъгълници. ### a) горен триъгълник Рисунката е един правоъгълен равнобедрен триъгълник от знака [`+`], като [`N`] определя размера на равнобедрените страни (вижте примерите). [=Примери:=] :table_2 |= Вход |= Изход |: 1 |: + |: 2 |: ``` + ++ |: 3 |: ``` + ++ +++ |: 5 |: ``` + ++ +++ ++++ +++++ ### б) долен триъгълник Подобно на предходната подточка, обаче обърнат по хоризонтала, и със знака [`#`]. [=Примери:=] :table_2 |= Вход |= Изход |: 1 |: ``` # |: 2 |: ``` ## # |: 3 |: ``` ### ## # |: 5 |: ``` ##### #### ### ## # ### в) пълен триъгълник [=Използвайки само една рекурсивна функция,=] сега трябва да изкарате първо горния триъгълник и след това долния. Ако просто извикате предходните две функции една след друга, задачата се обезсмисля. [=Примери:=] :table_2 |= Вход |= Изход |: 1 |: ``` + # |: 2 |: ``` + ++ ## # |: 3 |: ``` + ++ +++ ### ## # |: 5 |: ``` + ++ +++ ++++ +++++ ##### #### ### ## # ## Задача 3 Направете програма която разрешава проблема с [url https://en.wikipedia.org/wiki/Ages_of_Three_Children_puzzle възрастта на трите деца]. Една жена има три деца за които знаем три неща: умножението на техните възрасти, сбора на техните възрасти и факта, че има едно дете, което е най-голямо. Трябва да намерите възрастта на всяко дете, само по тази информация. Разбира се, от входа получавате две числа, съответно умножението и сбора на възрастите им. Трябва на екрана да изкарате три числа - възрастите на трите деца. [=Подсказка:=] най-лесното решение е да пробвате всички възможни възрасти, като избягвате техни пермутации [=Примери:=] :table_2 |= Вход |= Изход |: 72 14 |: 3 3 8 |: 36 13 |: 2 2 9 |: 350 42 |: 2 5 35 ## Задача 4 От входа получавате число [`N`], след това трябва да изкарате на нови редове, в нарастващ ред, всички двоични числа, които могат да се представят с [`N`]-бита. Вкарвате и водещи нули, тоест всяко число е съставено от точно [`N`] букви ([`N`] нули и единици). [=Примери:=] :table_2 |= Вход |= Изход |: 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 Направете програма която разрешава [url https://en.wikipedia.org/wiki/Takuzu Такузо пъзели]. Започвате с дъска 4х4, в тази дъска може да имате само цифрите 0 и 1, като няколко клетки вече идват с попълнени стойности (но повечето са празни). Обаче, на всяка колона и ред трябва да има еднакъв брой 0ли и 1ци, и не трябва да има повече от две последователни еднакви цифри (в реда или колоната). От входа получавате дъската, като с -1 обозначаваме празна клетка. [=Примери:=] :table_2 |= Вход |= Изход |: ``` -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