Задание 23 ЕГЭ по информатике. Рекурсивный обход дерева

Содержание

Теория

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

Динамическое программирование — это способ решения сложных задач путём сведения их к более простым задачам того же типа (разбиение на подзадачи и повторное использование уже посчитанных результатов).

Базовый пример задания (исполнитель с командами «+1» и «×2»)

Условие. Исполнитель преобразует число на экране. Даны команды:
1) «Прибавить 1» 2) «Умножить на 2».
Программа — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 5? Построим дерево вариантов, затем проанализируем его.

Анализ дерева

Число возможных программ — 4 (узлы-«финиши» выделены зелёным на слайде).
Число 5 можно получить из чисел 1,2,3,4 — это подсказывает естественную рекурсивную зависимость.

Рекурсивная функция для количества программ

Вопросы к постановке: Сколько параметров у функции? Какие базовые случаи? Какова рекуррентная формула? Ответы с презентации: два параметра (начало и конец), два базовых случая, а рекурсия — сумма путей через «+1» и «×2».

Параметры: start (исходное число), finish (целевое число).
База 1: если start == finish ⇒ существует ровно 1 программа (пустая последовательность).
База 2: если start > finish ⇒ программ нет (0).
Рекуррентное соотношение: F(start,finish) = F(start+1,finish) + F(start*2,finish).

Код

def  c_prg ( start,finish ):  # 2 параметра: начало подсчета и конечный результат
     if start>finish:         # базовый случай, начало подсчета больше окончания
         return 0
     elif  start==finish:     # базовый случай, начало подсчета=окончанию
         return 1
     else:
         return  c_prg (start+1,finish)+ c_prg (start*2,finish)  # рекурсивный случай

Практическая пометка: для больших диапазонов добавляйте мемоизацию (@lru_cache) — это ровно «динамическое программирование» через кэш.

Усложнение: обязательный проход через заданное число

Условие : те же команды, но нужно посчитать число программ, которые преобразуют 1 в 6 и обязательно проходят через число 3. На слайде показано дерево и анализ.

Анализ дерева

Число вариантов — 4.
Идея разбиения: число программ «от 1 до 3» умножить на число программ «от 3 до целевого». На слайде приведена формула N1→6 = N1→3 · N3→6 и запись F(1,3)*F(3,6).

Задание 2 (исполнитель «НечетМ»)

Условие: команды: 1) «прибавь 1», 2) «сделай нечётное»: x → 2x+1. Сколько программ переводят 1 → 27, если траектория не содержит число 26? «Траектория» — последовательность всех промежуточных значений.

Идея: модифицировать функцию — добавить третий параметр ignore (список «запрещённых» значений) и сразу возвращать 0, если start попал в этот список.

def  c_prg ( start,finish,ignore ):
     # 2 параметра: начало и конец; 3-й параметр — массив игнорируемых значений
     if start>finish or start in ignore:   # базовый случай: вышли за цель или попали в запрещённые
         return 0
     elif  start==finish:                   # базовый случай: дошли ровно до цели
         return 1
     else:
         return  c_prg (start+1,finish,ignore)+ c_prg (start*2+1,finish,ignore)  # рекурсия

print ( c_prg (1,27,[26]) )  # решение с избеганием 26

Этот приём легко обобщается: можно передавать множество запретов, финальные «нельзя», ограничения по длине и т.д. (все такие добавки — в духе динамического программирования).

Задание 3 (предпоследняя команда фиксирована)

Условие: исполнитель «Удвоитель» (команды «+1», «×2»). Сколько программ переводят 4 → 24, причём предпоследняя команда — обязательно «+1»? :contentReference[oaicite:17]{index=17}

Анализ: если предпоследняя команда «+1», то финишная конфигурация — либо 22 → +1 → 23 → +1 → 24 (то есть нужен счёт путей до 22), либо 11 → +1 → 12 → ×2 → 24 (нужны пути до 11). Следовательно, ответ равен F(4,22) + F(4,11).

def  c_prg ( start,finish ):
     if start>finish:
         return 0
     elif  start==finish:
         return 1
     else:
         return  c_prg (start+1,finish)+ c_prg (start*2,finish)

print ( c_prg (4,22)+ c_prg (4,11) )

Задание 4 (самая короткая программа при фиксированном числе «+1»)

Условие: «Калькулятор»: 1) «+1», 2) «×2», 3) «×3». Найти длину самой короткой программы, преобразующей 1 → 9217 и содержащей ровно 30 команд «+1». Под длиной понимается общее число команд.

Идея: добавить в функцию два счётчика — числа «+1» и общего количества команд; вернуть общее количество, минимизируя по ветвям; применить принцип динамического программирования (оптимальность подрешений) и кэшировать ответы. :contentReference[oaicite:20]{index=20}

res={}
def  f ( a,b,cntplus,cntnode ):
    if a>b:
        return 10**8
    elif   cntplus >30:
        return 10**8
    elif  a==b and  cntplus ==30:
        return  cntnode
    elif  a==b and  cntplus !=30:
        return 10**8
    elif   res.get (( a,b ),-1)!=-1:
        return res[( a,b )]
    else:
        s = min(
            f(a+1,b,cntplus+1,cntnode+1),
            f(a*2,b,cntplus,cntnode+1),
            f(a*3,b,cntplus,cntnode+1)
        )
        res[( a,b )]=s
        return s

print(f(1,9217,0,0))

Практическая пометка: вместо словаря res можно использовать @lru_cache, если все параметры — хэшируемые; здесь параметры подходят (целые).

Задания для закрепления

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

Базовый пример задания (исполнитель с командами «+1» и «×2»)

Анализ дерева

Рекурсивная функция для количества программ

Код

Усложнение: обязательный проход через заданное число

Анализ дерева

Задание 2 (исполнитель «НечетМ»)

Задание 3 (предпоследняя команда фиксирована)

Задание 4 (самая короткая программа при фиксированном числе «+1»)

Задания для закрепления

Простые

Средние

Сложные