path: root / src / teaching / upp-2023 / week11 / index.du

'def title Задачи - УПП, Седмица 11, 22.12.2023
'def  desc Условия на задачите за упражнение

# {title}

\n

GitHub classroom: {url classroom.github.com/a/cZRnZj9y;https://classroom.github.com/a/cZRnZj9y}

.important Във всички задачи {b трябва} да използвате рекурсия!

.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} и так. нат.

{b Примери:}

:table
:2
|= Вход
|= Изход

|: 0
|: 0

|: 1
|: 1

|: 3
|: 4

|: 144
|: 12

|: 1597
|: 17

|: 46368
|: 24



## Задача 2

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

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

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

{b Примери:}

:table
:2
|= Вход
|= Изход

|: 1
|: +

|: 2
|:
```
+
++

|: 3
|:
```
+
++
+++

|: 5
|:
```
+
++
+++
++++
+++++



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

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

{b Примери:}

:table
:2
|= Вход
|= Изход

|: 1
|:
```
'emplace
#
'endemplace

|: 2
|:
```
'emplace
##
#
'endemplace

|: 3
|:
```
'emplace
###
##
#
'endemplace

|: 5
|:
```
'emplace
#####
####
###
##
#
'endemplace



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

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

{b Примери:}

:table
:2
|= Вход
|= Изход

|: 1
|:
```
'emplace
+
#
'endemplace

|: 2
|:
```
'emplace
+
++
##
#
'endemplace

|: 3
|:
```
'emplace
+
++
+++
###
##
#
'endemplace

|: 5
|:
```
'emplace
+
++
+++
++++
+++++
#####
####
###
##
#
'endemplace



## Задача 3

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

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

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

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

{b Примери:}

:table
:2
|= Вход
|= Изход

|: 72 14
|: 3 3 8

|: 36 13
|: 2 2 9

|: 350 42
|: 2 5 35



## Задача 4

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

{b Примери:}

:table
:2
|= Вход
|= Изход

|: 1
|:
```
0
1

|: 2
|:
```
00
01
10
11

|: 3
|:
```
000
001
010
011
100
101
110
111

|: 4
|:
```
0000
0001
{i ...}
0111
1000
1001
{i ...}
1101
1110
1111



## Задача 5

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

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

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

{b Примери:}

: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