Задание 23 ЕГЭ по информатике. Решение деревом

В теории графов , дерево – это неориентированный граф , в котором любые две вершины соединены ровно одним путем.

Корнем будет являться исходное число, а листами – число, в которое надо прийти.

Типовое задание:

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

1. Увеличить число

2. Увеличить число

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

Если строить полное дерево, оно получится очень большим. Рекомендуется применять методы динамического программирования: не считать вершины, которые уже были подсчитаны ранее.

Дополнительные ограничения мы применяем так:

1. Траектория вычислений содержит число n.
   Разбиваем дерево решений на два дерева. Сначала находим количество программ из a в n, потом из n в a. Полученные числа перемножаем.
2. Траектория вычислений не содержит числа k.
   В дереве не учитываем ветки, где ход идет в число k.

Рассмотрим примеры.

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

1. прибавь 1

2. умножь на 3

Сколько есть программ, которые число 1 преобразуют в число 20?

У данного исполнителя две команды. Вторая более “весомая” чем первая, т.е. делает более “сильный” ход – больше увеличивает число. Поэтому будем отталкиваться от первой команды.

Само решение будет идти в два хода: сначала мы спускаемся вниз, до конечного числа. Затем обратный ход – поднимаемся до исходного числа с подсчетом количества программ.

Поскольку получить 20 из 1 прибавлением 1 можно за 19 команд, строить такое большое дерево не рационально. Из числа 7 мы уже не сможем получить 20 с помощью второй команды, мы его перепрыгнем. Значит, из 7 есть только один способ уйти в 20 — это прибавлять 1.

В дереве нижним индексом приписано количество способов получить число 20. Из всех чисел из диапазона 7..20 есть ровно один такой способ.

Из 6 мы можем попасть с помощью второй команды в число 18, которое как раз находится в этом диапазоне. Для подсчета количества программ для числа 6 мы будем складывать количество программ в числах, в которые можно попасть из 6

Продолжим подниматься вверх. Теперь мы будем опираться на уже подсчитанные значения. Такие числа выделены синим

Таким образом, получилось 12 программ.

Другой пример

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

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 40 и при этом траектория вычислений содержит число 20 и не содержит число 8?

В данном задании присутствует сразу два ограничения.

Чтобы учесть, что траектория содержит число 20, мы разобьем решение на два этапа: сначала найдем количество программ из 2 в 20, затем из 20 в 40.

Второе ограничение – что нельзя в число 8 – проявит себя только в первой части решения.

При построении дерева по команде +1 мы упираемся в число 8, в которое попасть нельзя. При этом после него, т.е. из 9, мы можем все посчитать.

Все числа от 11 до 20 при умножении на 2 перепрыгивают 20, поэтому из каждого из них есть только один способ попасть в 20: это прибавлять 1.

Для числа 10 мы получаем 2 способа.

Продолжим обратный ход для чисел от 7 до 2

Для числа 7 мы получаем количество программ равное количеству программ для 14.

Второй раз нам 8 встречается при попытке умножить 4 на 2. Не забываем его проигнорировать.

В итоге, получилось 10 способов.

Теперь посчитаем способы из 20 в 40. На самом деле, их не очень много.

Итоговое количество способов это 10 * 2 = 20.

Таким образом, с помощью дерева мы получаем решение, в котором можно учесть все ограничения и относительно компактную запись. Я предпочитаю именно этот способ ручного решения, вместо табличного.