Задачи - УПП, Седмица 11, 22.12.2023


GitHub classroom: classroom.github.com/a/cZRnZj9y

important Във всички задачи трябва да използвате рекурсия!
warn Някои задачи се повтарят с тези от миналия път, ако преди не сте ги решили, сега ги решете

Алтернативни задачи

Считайте задачите от семинара като задачи преди тези. Тоест, за хората които се затрудняват повечко, решете семинарните и след това се върнете тук. Разбира се, ще помагам и със семинарните задачи.

Задача 1

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

Напомням, че нормално Фибоначи се дефинира като редица, която започва с числата 0 и 1, и всяко следващо е сумата на предходните две. Тоест, нулевото число е 0, първото 1, второто е 0 + 1 = 1 (понеже 1 се повтаря, зачитаме го за първото число), третото е 1 + 1 = 2, четвъртото е 1 + 2 = 3 и так. нат.

Примери:

Вход Изход
0 0
1 1
3 4
144 12
1597 17
46368 24

Задача 2

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

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

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

Примери:

Вход Изход
1 +
2 
+
++
3 
+
++
+++
5 
+
++
+++
++++
+++++

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

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

Примери:

Вход Изход
1 
#
2 
##
#
3 
###
##
#
5 
#####
####
###
##
#

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

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

Примери:

Вход Изход
1 
+
#
2 
+
++
##
#
3 
+
++
+++
###
##
#
5 
+
++
+++
++++
+++++
#####
####
###
##
#

Задача 3

Направете програма която разрешава проблема с възрастта на трите деца.

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

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

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

Примери:

Вход Изход
72 14 3 3 8
36 13 2 2 9
350 42 2 5 35

Задача 4

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

Примери:

Вход Изход
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

Направете програма която разрешава Такузо пъзели.

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

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

Примери:

Вход Изход 
-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
︽