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

# {title}

\n

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

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

## Задача 1

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

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

{b Примери:}

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

|: 6 6
|: 6

|: 48 18
|: 6



## Задача 2

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

.comment
'emplace
\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*}
'endemplace

{img F(0) = 0\; F(1) = 1\; F(n) = F(n-1) + F(n-2);./img/fib.png}

{b Примери:}

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

|: 0
|: 0

|: 1
|: 1

|: 3
|: 4

|: 144
|: 12

|: 1597
|: 17

|: 46368
|: 24



## Задача 3

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

{b Примери:}

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

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

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

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

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



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

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

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

{b Примери:}

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

|: (1 + 2)
|: 3

|: ((2 + 9) * 3)
|: 33

|: (((8 * 1) * (56 + 4)) + (19 * 2))
|: 518