1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
# Задачи - УПП, Седмица 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_2
|= Вход
|= Изход
|: 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_2
|= Вход
|= Изход
|: 0
|: 0
|: 1
|: 1
|: 3
|: 4
|: 144
|: 12
|: 1597
|: 17
|: 46368
|: 24
## Задача 3
От входа получавате положително число [`N`], трябва да изкарате на екрана "рисунка", показваща формата на пясъчен часовник с височина [`2N`] (вижте примерите).
[=Примери:=]
:table_2
|= Вход
|= Изход
|: 1
|:
```
+
#
|: 2
|:
```
+++
+
#
###
|: 3
|:
```
+++++
+++
+
#
###
#####
|: 5
|:
```
+++++++++
+++++++
+++++
+++
+
#
###
#####
#######
#########
## Задача 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
Получавате един ред от терминала, в който ще имате скоби, знакът [`+`] и [`*`], шпации и числа.
Това е прост математически израз, трябва да изкарате резултата след неговото пресмятане, като винаги около [`число + число`] и [`число * число`] има скоби (тоест не е нужно да се притеснявате от приоритет и асоциативност).
За удобство спокойно може да ползвате [`atoi`] за конверитране на числовите части от низа в числа.
[=Примери:=]
:table_2
|= Вход
|= Изход
|: (1 + 2)
|: 3
|: ((2 + 9) * 3)
|: 33
|: (((8 * 1) * (56 + 4)) + (19 * 2))
|: 518
|
