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

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

1. Вычти 2

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

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

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

1. Вычти 1

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

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

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

1. Прибавь 1

2. Припиши 1

3. Умножь на 5

Первая команда увеличивает число на экране на 1. Вторая приписывает в конец числа 1, если новое число делится на 3; в противном случае число не изменяется. Третья команда умножает число на 5. Сколько существует различных программ, которые преобразуют исходное число 1 в число 410?

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

1. Умножь на 5

2. Умножь на 3

3. Прибавь 45

Первая команда умножает число на экране на 5, вторая – умножает на 3, третья – увеличивает на 45. Сколько существует различных программ, которые преобразуют исходное число 1 в число 2970, и при этом траектория вычислений не более 4 команд «умножь на 5», не менее 2 команд «умножь на 3», и ровно 5 команд «прибавь 45»?

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

1. запиши сумму чисел в первое окно

2. запиши сумму чисел во второе окно

Выполняя первую из них, Сумматор складывает числа в окнах и заменяет этой суммой число в первом окне, а выполняя вторую, складывает числа и заменяет этой суммой число во втором окне. Сколько существует программ для Сумматора таких, что в результате его работы из пары чисел (1, 1) получится пара с суммой 88?

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

1. Прибавь 2

2. Умножь на 2

3. Умножь на 3

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

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

1. Прибавь 2

2. Умножь на 2

3. Умножь на 3

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

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

1. Прибавь 2

2. Умножь на 2

3. Умножь на 3

Первая команда увеличивает число на экране на 2, вторая умножает его на 2, третья – умножает на 3. Сколько существует различных программ, которые преобразуют исходное число 1 в число 402, и при этом траектория вычислений содержит не более 2 чётных чисел (не считая первое и последнее числа)?

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

1. Прибавь 3

2. Умножь на 2

3. Умножь на 7

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

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

1. Прибавь 1

2. Умножь на 2

3. Умножь на 5

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

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

1. Прибавь 1

2. Умножь на 2

3. Умножь на 3

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

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

1. Прибавь 1

2. Умножь на 3

3. Умножь на 4

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

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

1. Прибавь 2

2. Умножь на 3

3. Умножь на 5

Первая команда увеличивает число на экране на 2, вторая умножает его на 3, третья – умножает на 5. Сколько существует различных программ, которые преобразуют исходное число 2 в число 200 и содержат не более трёх команд умножения?

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

1. Прибавь 1

2. Умножь на 2

3. Умножь на 3

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

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

1. Прибавь 1

2. Припиши 2

Первая команда увеличивает число на экране на 1, вторая приписывает 2 в начало десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 3, то программа 212 последовательно преобразует его в 23, 24, 224. Сколько существует различных программ, которые преобразуют исходное число 3 в число 678?

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

1. Прибавь 1

2. Припиши 1

Первая команда увеличивает число на экране на 1, вторая приписывает 1 в начало десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 11, 12, 112. Сколько существует различных программ, которые преобразуют исходное число 1 в число 512?

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

1. Прибавь 1

2. Припиши 3

Первая команда увеличивает число на экране на 1, вторая приписывает 3 в конец десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 13, 14, 143. Сколько существует различных программ, которые преобразуют исходное число 3 в число 462?

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

1. Прибавь 2

2. Припиши 2

Первая команда увеличивает число на экране на 2, вторая приписывает 2 в конец десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 12, 14, 142. Сколько существует различных программ, которые преобразуют исходное число 2 в число 900?

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

1. Прибавь 1

2. Припиши 1

Первая команда увеличивает число на экране на 1, вторая приписывает 1 в конец десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 11, 12, 121. Сколько существует различных программ, которые преобразуют исходное число 1 в число 555?

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

1. Прибавь 2

2. Вычти 3

Первая команда увеличивает число на экране на 2, вторая уменьшает на 3. При выходе за пределы отрезка [–40; 40] исполнитель аварийно завершает свою работу. Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 1 преобразуют в число 30 и при этом траектория вычислений не содержит одинаковых чисел?