# Задачи - УПП, Седмица 10, 15.12.2023

\n

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

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

## Задача 1

Най-големия общ делител на числата `[a]` и `[b]` е най-голямото, число което ги дели без остатък.
Евклидовият алгоритъм се базира на факта, че за две положителни числа `[a]` и `[b]`, като `[a > b]`, НОД на `[a]` и `[b]` е същия като НОД на `[a - b]` и `[b]` и когато `[a = b]`, тогава НОД на `[a]` и `[b]` е тяхната стойност.

От входа получавате две цели положителни числа и трябва да изкарате техния НОД, чрез алгоритъма на Евклид =[имплементиран с рекурсия]=.

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

.table
|=Вход=||=Изход=|
|:6 6 :||:6    :|
|:48 18:||:6   :|

## Задача 2

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

.comment
\begin{align*}
F_n = \left\{ \begin{array}{ll}
0, & n=0 \\
1, & n=1 \\
F_{n-1} + F_{n-2} & \text{иначе} \\
\end{array} \right.
\end{align*}

[image ./img/fib.png F(0) = 0; F(1) = 1; F(n) = F(n-1) + F(n-2)]

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

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

## Задача 3

От входа получавате положително число `[N]`, трябва да изкарате на екрана "рисунка", показваща формата на пясъчен часовник с височина `[2N]` (вижте примерите).

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

.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>:|

## Задача 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

Получавате един ред от терминала, в който ще имате скоби, знакът `[+]` и `[*]`, шпации и числа.
Това е прост математически израз, трябва да изкарате резултата след неговото пресмятане, като винаги около `[число + число]` и `[число * число]` има скоби (тоест не е нужно да се притеснявате от приоритет и асоциативност).

За удобство спокойно може да ползвате `[atoi]` за конверитране на числовите части от низа в числа.

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

.table
|=Вход=||=Изход=|
|:(1 + 2):||:3 :|
|:((2 + 9) * 3):||:33:|
|:(((8 * 1) * (56 + 4)) + (19 * 2)):||:518:|