Динамическое программирование: подсчёт программ (задание 23 ЕГЭ) — тренажёр

Пример 1. Исполнитель умеет только одну команду: «прибавь 1». Сколько команд в единственной программе, переводящей число 5 в число 12?

Подсказка. Разница финиша и старта и есть число команд.

Как решать. Каждая команда добавляет единицу, поэтому единственная программа делает 12 - 5 команд.

Ответ: 7

Пример 2. Программа переводит число 1 в число 11 и содержит ровно одну команду «прибавь 2», остальные команды — «прибавь 1». Сколько в этой программе команд «прибавь 1»?

Подсказка. Вычти из общей прибавки две единицы, которые приносит команда «прибавь 2».

Как решать. Общая прибавка равна 11 - 1; две единицы из них даёт команда «прибавь 2», остальные 11 - 1 - 2 добирают команды «прибавь 1».

Ответ: 8

Пример 3. Исполнитель выполнил программу из 7 команд, из которых 2 команд — «прибавь 2», а остальные — «прибавь 1». На сколько увеличится число после этой программы?

Подсказка. Замени каждую «прибавь 2» на «прибавь 1» плюс одна лишняя единица.

Как решать. Каждая «прибавь 2» даёт две единицы, каждая «прибавь 1» — одну: 2 · 2 + 7 - 2 = 7 + 2.

Ответ: 9

Пример 4. Черновик таблицы R ведётся от старта 3 до финиша 7 включительно. Сколько клеток придётся заполнить, если база тоже считается клеткой?

Подсказка. Между включёнными концами разница плюс единица.

Как решать. Клетки соответствуют числам от 3 до 7: разница концов плюс одна клетка, итого 7 - 3 + 1.

Ответ: 5

Пример 5. Исполнитель умеет только одну команду: «прибавь 1». Сколько команд в единственной программе, переводящей число 2 в число 15?

Подсказка. Разница финиша и старта и есть число команд.

Как решать. Каждая команда добавляет единицу, поэтому единственная программа делает 15 - 2 команд.

Ответ: 13

Пример 6. Программа переводит число 4 в число 12 и содержит ровно одну команду «прибавь 2», остальные команды — «прибавь 1». Сколько в этой программе команд «прибавь 1»?

Подсказка. Вычти из общей прибавки две единицы, которые приносит команда «прибавь 2».

Как решать. Общая прибавка равна 12 - 4; две единицы из них даёт команда «прибавь 2», остальные 12 - 4 - 2 добирают команды «прибавь 1».

Ответ: 6

Пример 7. Исполнитель выполнил программу из 5 команд, из которых 1 команд — «прибавь 2», а остальные — «прибавь 1». На сколько увеличится число после этой программы?

Подсказка. Замени каждую «прибавь 2» на «прибавь 1» плюс одна лишняя единица.

Как решать. Каждая «прибавь 2» даёт две единицы, каждая «прибавь 1» — одну: 1 · 2 + 5 - 1 = 5 + 1.

Ответ: 6

Пример 8. Черновик таблицы R ведётся от старта 2 до финиша 6 включительно. Сколько клеток придётся заполнить, если база тоже считается клеткой?

Подсказка. Между включёнными концами разница плюс единица.

Как решать. Клетки соответствуют числам от 2 до 6: разница концов плюс одна клетка, итого 6 - 2 + 1.

Ответ: 5

Пример 9. Исполнитель умеет только одну команду: «прибавь 1». Сколько команд в единственной программе, переводящей число 4 в число 14?

Подсказка. Разница финиша и старта и есть число команд.

Как решать. Каждая команда добавляет единицу, поэтому единственная программа делает 14 - 4 команд.

Ответ: 10

Пример 10. Программа переводит число 3 в число 9 и содержит ровно одну команду «прибавь 2», остальные команды — «прибавь 1». Сколько в этой программе команд «прибавь 1»?

Подсказка. Вычти из общей прибавки две единицы, которые приносит команда «прибавь 2».

Как решать. Общая прибавка равна 9 - 3; две единицы из них даёт команда «прибавь 2», остальные 9 - 3 - 2 добирают команды «прибавь 1».

Ответ: 4

Пример 11. Черновик таблицы R ведётся от старта 2 до финиша 10 включительно. Сколько клеток придётся заполнить, если база тоже считается клеткой?

Подсказка. Между включёнными концами разница плюс единица.

Как решать. Клетки соответствуют числам от 2 до 10: разница концов плюс одна клетка, итого 10 - 2 + 1.

Ответ: 9

Пример 12. Исполнитель умеет только одну команду: «прибавь 1». Сколько команд в единственной программе, переводящей число 6 в число 11?

Подсказка. Разница финиша и старта и есть число команд.

Как решать. Каждая команда добавляет единицу, поэтому единственная программа делает 11 - 6 команд.

Ответ: 5

Пример 13. Программа переводит число 5 в число 12 и содержит ровно одну команду «прибавь 2», остальные команды — «прибавь 1». Сколько в этой программе команд «прибавь 1»?

Подсказка. Вычти из общей прибавки две единицы, которые приносит команда «прибавь 2».

Как решать. Общая прибавка равна 12 - 5; две единицы из них даёт команда «прибавь 2», остальные 12 - 5 - 2 добирают команды «прибавь 1».

Ответ: 5

Пример 14. Исполнитель выполнил программу из 8 команд, из которых 3 команд — «прибавь 2», а остальные — «прибавь 1». На сколько увеличится число после этой программы?

Подсказка. Замени каждую «прибавь 2» на «прибавь 1» плюс одна лишняя единица.

Как решать. Каждая «прибавь 2» даёт две единицы, каждая «прибавь 1» — одну: 3 · 2 + 8 - 3 = 8 + 3.

Ответ: 11

Пример 15. Черновик таблицы R ведётся от старта 1 до финиша 10 включительно. Сколько клеток придётся заполнить, если база тоже считается клеткой?

Подсказка. Между включёнными концами разница плюс единица.

Как решать. Клетки соответствуют числам от 1 до 10: разница концов плюс одна клетка, итого 10 - 1 + 1.

Ответ: 10

Пример 16. Исполнитель умеет только одну команду: «прибавь 1». Сколько команд в единственной программе, переводящей число 5 в число 11?

Подсказка. Разница финиша и старта и есть число команд.

Как решать. Каждая команда добавляет единицу, поэтому единственная программа делает 11 - 5 команд.

Ответ: 6

Пример 17. Программа переводит число 5 в число 11 и содержит ровно одну команду «прибавь 2», остальные команды — «прибавь 1». Сколько в этой программе команд «прибавь 1»?

Подсказка. Вычти из общей прибавки две единицы, которые приносит команда «прибавь 2».

Как решать. Общая прибавка равна 11 - 5; две единицы из них даёт команда «прибавь 2», остальные 11 - 5 - 2 добирают команды «прибавь 1».

Ответ: 4

Пример 18. Исполнитель выполнил программу из 4 команд, из которых 3 команд — «прибавь 2», а остальные — «прибавь 1». На сколько увеличится число после этой программы?

Подсказка. Замени каждую «прибавь 2» на «прибавь 1» плюс одна лишняя единица.

Как решать. Каждая «прибавь 2» даёт две единицы, каждая «прибавь 1» — одну: 3 · 2 + 4 - 3 = 4 + 3.

Ответ: 7

Пример 19. Черновик таблицы R ведётся от старта 2 до финиша 9 включительно. Сколько клеток придётся заполнить, если база тоже считается клеткой?

Подсказка. Между включёнными концами разница плюс единица.

Как решать. Клетки соответствуют числам от 2 до 9: разница концов плюс одна клетка, итого 9 - 2 + 1.

Ответ: 8

Вопрос 1. Сколько различных программ переводят число 0 в число 5, если команды исполнителя — «прибавь 1» и «прибавь 2»?

Ответ: 8

Пояснение. Таблица от нуля: R(0) = 1, R(1) = 1, R(2) = 2, R(3) = 3, R(4) = 5, R(5) = 8. В клетке 5 — восемь программ.

Вопрос 2. Что верно про подсчёт программ через обязательную точку C?

Ответ: количество программ до C умножается на количество программ после C; каждая программа через C учитывается в произведении ровно один раз

Пояснение. Точка C делит каждую программу однозначно, поэтому количества отрезков перемножаются, и двойного счёта нет. Вычитание отвечает лишь на вопрос «мимо C», а чётность C роли не играет.

Вопрос 3. Сколько программ переводят число 0 в число 10, если траектория не должна проходить через число 4? Впиши число.

Ответ: 24

Пояснение. Ноль в клетке 4, дальше обычное заполнение: R(5) = 3, R(6) = 3, R(7) = 6, R(8) = 9, R(9) = 15, R(10) = 24. Проверка вычитанием: всего 89, через 4 проходит 5 · 13 = 65, обходят 89 - 65 = 24.

Вопрос 4. Если команды исполнителя уменьшают число, таблицу заполняют от большего к меньшему.

Ответ: Верно

Пояснение. Клетка собирает приходы из уже заполненных клеток: при вычитании предшественники стоят правее, поэтому заполнение идёт справа налево, от старта к финишу.

Вопрос 5. Расставь шаги решения с запрещённой точкой по порядку.

Ответ: вписать единицу в стартовую клетку → записать ноль в запрещённую точку K → заполнить клетки от старта к финишу, собирая приходы → взять число из клетки финиша — это ответ

Пояснение. Сначала база, затем запреты, потом заполнение слева направо — и только в конце ответ из финишной клетки. Пропуск шага ломает всю таблицу.

Вопрос 6. Сопоставь термин и его смысл.

Пояснение. Четыре опоры метода: база, переход, правило обязательной точки и способ счёта сверху вниз. На них держится любой вариант задания 23.

Вопрос 7. Дополни правило подсчёта программ.

Ответ: n - 1 → n - 2 → ноль

Пояснение. Команда «прибавь 1» приходит из n - 1, команда «прибавь 2» — из n - 2. Запрещённая точка получает ноль, и все пути через неё гаснут.