Задание 23. Динамическое программирование (количество программ)

У исполнителя имеются две команды, которые обозначены латинскими буквами:

A. Вычесть 2
B. Найти целую часть от деления на 2

Первая команда уменьшает число на 2, вторая – находит целую часть от деления числа на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 38 результатом является число 2, при этом траектория вычислений содержит число 16?

Ответ:  36

def f(x,y):
    if x == y:
        return 1
    if x < y:
        return 0
    
    return f(x-2,y)+f(x//2,y)

print(f(38,16)*f(16,2))

Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 2
результатом является число 20, при этом траектория вычислений не содержит числа 11?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA
при исходном числе 4 траектория будет состоять из чисел 16, 32, 33

Ответ 37

def f(x, y):
    if x == y:
        return 1
    if x > y or x == 11:
        return 0
    
    return f(x + 1, y) + f(x * 2, y) + f(x**2, y)

print(f(2, 20))

Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. прибавить 1
2. умножить на 2

Программа для исполнителя - это последовательность команд. Сколько существует программ для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?

Траектория вычислений программы - это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Ответ:  98

Решение

def f(x, y):
    if x == y:
        return 1
    if x > y or x == 17: 
        return 0
    
    return f(x + 1, y) + f(x * 2, y)

print(f(1, 10) * f(10, 35))

У исполнителя имеются три команды, которые обозначены латинскими буквами:

A. Вычесть 1
B. Вычесть 2
C. Найти целую часть от деления на 3

Первая команда уменьшает число на 1, вторая – уменьшает его на 2, третья – находит целую часть от деления числа на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 16 результатом является число 6, при этом траектория вычислений содержит число 11?

Ответ:  64

Решение

def f(x,y):
    if x == y:
        return 1
    if x < y:
        return 0
    
    return f(x-1,y)+f(x-2,y)+f(x//3,y)

print(f(16,11)*f(11,6))

Яндекс Учебник

Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены буквы латинского алфавита:

A. Прибавить 1
B. Прибавить 3
C. Умножить на 4

Программа для исполнителя — это последовательность команд.

Сколько программ преобразуют число 4 в число 35, и при этом их траектория вычислений содержит число 18 и не содержит число 23?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе 7 траектория состоит из чисел 8, 32, 35.

Ответ: 21580

Яндекс Учебник

Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:

A. Вычти 2
B. Найти целую часть от деления на 2

Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 42 результат — число 1 и при этом траектория вычислений содержит число 26 и не содержит число 12?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.

Ответ: 51

Яндекс Учебник

Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Вычти 3.
2. Найди целую часть от деления на 2.

Первая из них уменьшает число на экране на 3, вторая заменяет число на экране на целую часть от деления числа на 2.

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 80 результатом является число 3, и при этом траектория вычислений содержит число 23 и не содержит число 12?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 10 траектория состоит из чисел 7, 4, 2.

Ответ: 14

Яндекс Учебник

Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель преобразует число на экране.

У исполнителя есть три команды, которые обозначены латинскими буквами:

A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 8 результат — число 115, при этом траектория вычислений содержит число 32 и не содержит 33?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.

Ответ: 11

Крючков М. Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три пронумерованных команды:

1. Прибавить 3
2. Умножить на 2
3. Умножить на 5

Первая команда увеличивает число на экране на 3, вторая увеличивает число на экране в два раза, третья увеличивает число на экране в пять раз.

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 7 результат — число 961? При этом траектория вычислений должна содержать число 169, но не содержать 321.

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 5 траектория будет состоять из чисел 8, 40, 80.

Ответ: 154457

Яндекс Учебник 

Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель преобразует число на экране.

У исполнителя есть три команды, которые обозначены латинскими буквами:

A. Прибавить 2
B. Прибавить 3
C. Возвести в квадрат

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результат — число 42, при этом траектория вычислений содержит число 25 и не содержит 16?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 19, 21.

Ответ: 12348

Яндекс Учебник

Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 3
2. Умножь на 2
3. Возведи в квадрат

Первая из них увеличивает число на экране на 3, вторая увеличивает число на экране в два раза, третья возводит число в квадрат.

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 128 и траектория вычислений программы содержит число 12 ИЛИ не содержит числа 20.

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 3 траектория будет состоять из чисел 6, 12, 144.

Ответ: 368

Яндекс Учебник

Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Отними первую цифру квадрата числа
2. Отними сумму цифр числа

Первая из них отнимает от числа на экране первую цифру этого числа в квадрате, вторая отнимает от числа на экране сумму его цифр.

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 32 результатом является число 1?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 30 траектория будет состоять из чисел 21, 18, 15.

Ответ: 56

Рогов А.

Тема: Подсчёт количества маршрутов в графе(Подсчёт количества маршрутов в графе)

Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Вычти 1.
2. Найди целую часть от деления на 2.

Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2. Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 89 результатом является число 7, и при этом траектория вычислений содержит число 30?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.

Ответ: 682

1.    Перейти на сайт ФИПИ "Открытый банк заданией ЕГЭ"

        Открытый банк заданией ЕГЭ

2.     Раскрыть вкладку "ПОДБОР ЗАДАНИЙ" , в таблице выбрать вариант задания и ввести этот номер в окно "Номер задания"

3.     Решить задание и проверить решение на сайте

Задания открытого банка по информатике

24EE48	94AB77	C0C817	E51AA0
D5434F	E28170	121720	209B53
765FFF	F27CB9	1FC322	8F2A53
E9714A	C2A6B5	6DB421	D785AA
B976F3	EC38B4	313621	7173AE
9A65F5	4DC91D	28BCD8	AAEAA0
43B305	007C14	DE68DA	3F3DA7
0A180B	18811	6C2CD5	498BC0
C2EB01	CD3814	791F51	E1D1CF
E9000D		B3D150	0B1894
62B10B			0CCF9C