ЕГЭ-13. Динамическое программирование

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

1. Прибавить 2

2. Прибавить предыдущее

3. Прибавить следующее

Первая команда увеличивает число на 2, вторая – на предыдущее (например, число 5 будет преобразовано по правилу 5 + 4), третья – на следующее (аналогично, 5 по правилу 5 + 6 = 11). Сколько существует таких программ, которые исходное число 7 преобразуют в число 63, и при этом траектория вычислений не содержит число 43?

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

1. Умножить на 2

2. Умножить на 3

Первая команда увеличивает число на экране в 2 раза, вторая – увеличивает значение в 3 раза. Сколько существует программ, для которых при исходном числе 8 результатом является число 3456, и при этом траектория вычислений содержит число 96.

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

1. Прибавить 3

2.Умножить на 2

Первая команда увеличивает число на экране на 3, вторая – увеличивает значение в два раза. Сколько существует программ, для которых при исходном числе 12 результатом является число 96?

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

1. Прибавить 2

2. Сделать простое

Первая команда увеличивает число на экране на 2, вторая – получает ближайшее бóльшее простое число. Сколько существует программ, для которых при исходном числе 2 результатом является число 45 и при этом траектория вычислений содержит число 14 и не содержит числа 33?

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

1. Прибавить 3

2. Умножить на 2

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

(Е. Джобс) Исполнитель Остаточек преобразует числа и имеет следующие команды:

1. Прибавить 1

2. Умножить на 2

3. Прибавить остаток от деления на 4

Первая команда увеличивает число на единицу, вторая – увеличивает вдвое, третья команда добавляет к числу значение остатка от деления этого числа на 4. Определите, сколько существует чисел, из которых Остаточек может получить число 80 с помощью программы длиной не более 5 команд.

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

1. Прибавить 2

2. Прибавить 4

3. Прибавить 5

Определите число, для получения которого из числа 31 существует 1001 программа.

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

1. Прибавить 2

2. Прибавить 5

Определите число, для получения которого из числа 5 существует 34 программы.

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

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

Определите число, для получения которого из числа 1 существует 175 программ.

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

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

Сколько разных чисел на отрезке [1000, 1024] может быть получено из числа 1 с помощью программ, состоящих из 8 команд?

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

1. Прибавить 1

2. Прибавить 2

3. Умножить на 2

Сколько разных чисел на отрезке [34, 59] может быть получено из числа 1 с помощью программ, состоящих из 6 команд?

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

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

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

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

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

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

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

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

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

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

1. Прибавить 1

2. Прибавить 2

3. Умножить на 2

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

(С.С. Поляков) У исполнителя Калькулятор есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 5

3. Умножить на 3

Найдите длину самой короткой программы, в результате выполнения которой при исходном числе 1 результатом является число 227.

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

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Сколько существует программ, которые преобразуют исходное число 5 в число 26, и при этом траектория вычислений содержит число 11 и не содержит чисел 13 и 15?

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

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

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

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

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Сколько существует программ, которые преобразуют исходное число 3 в число 22, и при этом траектория вычислений содержит число 10 и не содержит чисел 8 и 15?

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

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Сколько существует программ, которые преобразуют исходное число 2 в число 21, и при этом траектория вычислений содержит число 5 и не содержит чисел 8 и 11?