Рекуррентные последовательности

15 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Рекурсия#63700
Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n < 11,
F(n) = n + F(n­ –1), если n ≥ 11

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 2023
2007		 32248
Рекуррентные последовательности
✓ 65✗ 87700средняяВойти и решать
Рекурсия итеративно - 3#47159
Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n < 11,
F(n) = n + F(n­ –1), если n ≥ 11

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 2023
2007		 32248
Рекуррентные последовательности
✓ 61✗ 59500лёгкаяВойти и решать
Рекурсия итеративно - 2#47158
Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 7, если n < 7,
F(n) = n + 1 + F(n­ –2), если n ≥ 7.

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 3000
2000		 1251000
Рекуррентные последовательности
✓ 116✗ 195600лёгкаяВойти и решать
Рекурсия итеративно - 1#47155
Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 3, если n < 3,
F(n) = 2n + 5 + F(n­ – 2), если n ≥ 3.

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 3000
2000		 2503500
Рекуррентные последовательности
✓ 139✗ 88500лёгкаяВойти и решать
Счетовод - 6#47145
У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. прибавь B
3. умножь на С
Первая из них увеличивает на A число на экране, вторая увеличивает число на экране на B, третья умножает число на экране на С. Программа для Счетовода – это последовательность команд. Сколько существует таких программ, которые исходное число S преобразуют в число F и при этом траектория вычислений программы содержит число num1 и число num2?

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, A не равно B.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num1, num2 (1<= A,B,C <= 10, 1 <= S <= 100, 1 <= F <= 103, S <= num1 < num2 <= F). Каждое число вводится с новой строки.

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 
Примеры
№ Входные данные Выходные данные
1 1
2
2
3
13
9
11		 68
Рекуррентные последовательности
✓ 37✗ 12700средняяВойти и решать
Счетовод - 5#47128
У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь 1
2. сделай четное
3. сделай нечетное
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. 
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход два числа: S, F (1 <= S <= 100, 1 <= F <= 103)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 
Примеры
№ Входные данные Выходные данные
1 2
16		 40
Рекуррентные последовательности
✓ 51✗ 80600лёгкаяВойти и решать
Счетовод - 4#46792
У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. возведи в квадрат
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 103)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 
Примеры
№ Входные данные Выходные данные
1 1
2
2
38		 266
Рекуррентные последовательности
✓ 47✗ 51500лёгкаяВойти и решать
Счетовод - 3#46791
У исполнителя Счетовод три команды, которым присвоены номера:
1. прибавь A
2. прибавь B
3. умножь на С
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 10, 1 <= F <= 100, A и B - различные числа)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 
Примеры
№ Входные данные Выходные данные
1 1
2
3
1
12		 225
Рекуррентные последовательности
✓ 118✗ 127500лёгкаяВойти и решать
Счетовод - 2#46790
У исполнителя Счетовод три команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. умножь на С
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход пять чисел: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 100, 1 <= F <= 103, B и C - различные числа)

Выходные данные
Выведите ответ на задачу.  Гарантируется, что ответ не превышает 263.
Примеры
№ Входные данные Выходные данные
1 1
2
3
1
18		 96
Рекуррентные последовательности
✓ 81✗ 90500лёгкаяВойти и решать
Счетовод - 1#46789
У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 103)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 
Примеры
№ Входные данные Выходные данные
1 1
2
1
10		 14
Рекуррентные последовательности
✓ 61✗ 105500лёгкаяВойти и решать
Мячик на лесенке#38639

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.


Входные данные

Вводится одно число 0 < N < 31.


Выходные данные

Выведите одно число — количество маршрутов.
 

Примеры
№ Входные данные Выходные данные
1 4 7
Динамическое программирование: один параметрРекуррентные последовательности
✓ 211✗ 205400лёгкаяВойти и решать
Небоскреб#31785
В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобьется, то если уронить шарик с этажа номер p+1, то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается.
 
Вы хотите определить минимальный номер этажа, при падении с которого шарик разбивается. Для проведения экспериментов у вас есть два шарика. Вы можете разбить их все, но в результате вы должны абсолютно точно определить этот номер.
 
Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу.
 
Входные данные
Программа получает на вход количество этажей в небоскребе n.
 
Выходные данные
Требуется вывести наименьшее число бросков, при котором можно всегда решить задачу.
 
Примечание
Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа.
 
Подсказки
1. Как следует действовать, если шарик был бы только один?
2. Пусть шариков два и мы бросили один шарик с этажа номер k. Как мы будем действовать в зависимости от того, разобьется ли шарик или нет?
3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a.
 
Примеры
№ Входные данные Выходные данные
1 4 2
2 7 3
Динамическое программирование: один параметрРекуррентные последовательности
✓ 61✗ 110700средняяВойти и решать
Опасные отходы#27085
При переработке радиоактивных материалов образуются отходы двух типов: А (неопасные) и B (особо опасные). Отходы каждого типа упаковываются в контейнеры, а затем контейнеры складываются в стопки. Стопка считается взрывоопасной, если в ней есть три или больше контейнеров с особо опасными отходами (типа B) расположены рядом. Для заданного количества контейнеров N определите, сколько есть способов составить безопасную стопку.
 
Входные данные
Входная строка содержит натуральное число – количество контейнеров N в стопке (1 <= N <= 35).
 
Выходные данные
Программа должна вывести одно число – количество способов составить безопасную стопку из N контейнеров.

 
Примеры
№ Входные данные Выходные данные
1 3 7
Динамическое программирование: один параметрРекуррентные последовательности
✓ 88✗ 156700средняяВойти и решать
Числа Фибоначчи#25962
Числа Фибоначчи определяются рекуррентной формулой:

\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \text{ при}\ n \ge 2\)

Входные данные
В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).
 
Выходные данные
Вывести одно n-е число Фибоначчи - Fn.
 
Примеры
№ Входные данные Выходные данные
1 1 1
2 7 21
Динамическое программированиеРекуррентные последовательности
✓ 104✗ 217400лёгкаяВойти и решать
MTN DEW#21780
Чтобы подготовиться к предстоящей битве Bonkisilver должен прокачать свой скил, а, как известно, лучшим способом это сделать, является употребление mtn dew при прослушивании дабстепа в 4:20 по МСК. Полученный скилл вычисляется по формуле:

f(n) = f(n - 1) + f(n - 2) + f(n / 2),
где n - количество литров mtn dew, выражаемое целым числом. Операция n/2 означает целочисленное деление числа n на 2.

Также, известно, что

f(1) = 1 microCoinZ 
f(x) = 0 microCoinZ, при x < 1.

Помогите Bonkisilver сосчитать полученное количество microCoinZ.
 
Входные данные
На вход подается число n (0 <= n <= 70).
 
Выходные данные
Выведите одно число - полученный скилл. 
 
Примеры
№ Входные данные Выходные данные
1 1 1

PS: Mountain Dew, также MTN DEW — безалкогольный сильногазированный прохладительный напиток, торговая марка американской компании PepsiCo. 
Динамическое программированиеДинамическое программирование: один параметрРекуррентные последовательности
✓ 296✗ 741500лёгкаяВойти и решать
Поделиться
Класснуть