6137 подписчиков

Рекурсия и задача с исполнителем из ЕГЭ по информатике

24 марта 202324 мар 2023

197

5 мин

Оглавление

Задача [Тип 23]
Решение:
Количество способов получить 10 из 3

Недавно разбирали с учеником 23 задачу из ЕГЭ по информатике. Хотел бы поделиться своими мыслями и некоторыми лайфхаками решения этой задачи с моими дорогими подписчиками. Очень надеюсь, что кому-нибудь эта заметка будет полезна или хотя бы интересна. Поэтому прошу не поскупиться на обратную связь, если эта тема интересна. Если же вам это не нравится, то можете поставить дизлайк — в вашей ленте будет меньше такой ерунды. А пока погнали начинать, сразу с практики :)

Задача [Тип 23]

Исполнитель А16 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1.  Прибавить 1;
2.  Прибавить 2;
3.  Умножить на 2;
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2. Программа для исполнителя А16 – это последовательность команд. Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10? Траектория вычислений программы  — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

Решение:

Попытка нарисовать полное дерево — плохой способ. Давайте начнем рисовать. Уверяю вас, что мы быстро устанем в попытках изобразить все возможные ветки нашего дерева, на которых будут получаться числа 12. (и на самом деле дерево будет перекошено в одну сторону, т.к. умножение на 2 быстро будет выходить за пределы 12). И всё равно это очень много трудозатрат. Смотрите сами...

Посмотреть картинку в исходном качестве

Как мы видим отсюда, тут невозможно полноценно построить все решения. Пока рисовал тот способ, то придумал более компактный. У нас всё равно ограниченное количество интересующих нас чисел. Так почему бы не выписать их все в строчку (или в круг, как вам нравится больше?), а затем расставить у всех весовые коэффициенты. Тогда весовой коэффициент последнего числа будет являться ответом на задачу. Сложно? Давайте я нарисую, сразу станет легке :)

Здесь важно отметить, что:
1. Черными цифрами внутри кружков обозначаются числа, в которых мы находимся и которые мы получаем с помощью трех инструкций, которые способен сделать исполнитель.
2. Красные числа рядом - весовые коэффициенты. Весовой коэффициент исходной вершины графа (в нашем случае это 3) является равным 1, потому что у нас только 1 способ оказаться в этой вершине, ибо она исходная. Весовой коэффициент каждой новой вершины можно посчитать, суммируя весовые коэффициенты тех вершин графа, из которых идут стрелки в нашу текущую вершину, для которой в текущий момент времени мы считаем весовой коэффициент. Проще: сколько стрелок входит, столько весовых коэффициентов складываем для определения веса текущей вершины/точки/числа. Вот такой вот графический способ.

Второй способ решения задачи — аналитический. У нас есть некоторая функция Nₖ - количество возможных способо добраться в число k. И мы рекурсивно просчитываем эту функцию для каждого нужного числа. Начинать проще с конца. Показываю:

Количество способов получить 10 из 3

Количество способов получить 12 из 10

Зная количество ветвей/путей, ведущих в 10 из 3 и количество путей, ведущих в 12 из 10, мы можем получить количество способов попасть из 3 в 12, обязательно проходя через 10, просто перемножив полученные значения: 2×30 = 60. Обратите внимание, что именно такой весовой коэффициент получился у числа «12» на втором рисунке, где мы сделали оптимизированный граф (графическое решение задачи).

Есть и третий способ решения — оптимизация через программирование

Мы уже видели в аналитических расчетах рекурсивное поведение функции N, которая определяет количество способов. Также можно заметить, что мы передвигаемся по целым числам, поэтому:
1. Количество способов получить четное число на текущем шаге → 3 (пример: N(8) = N(7) + N(6) + N(4).)
2. Количество способов получить нечетное число на текущем шаге → 2 (пример: N(9) = N(8) + N(7).)

Вот такой будет код решения

Стоит заметить, что это тоже не оптимизированное решение, потому что если попробовать взять относительно небольшие числа, например a = 3 и b = 40, то количество способов получить число 40 из 3 с помощью трех инструкций (+1, +2, *2) составляет 5 994 1014 ~ 6 миллионов возможных путей. И вот тут Python уже начинает заметно тормозить. Интересно, что выдала бы аналогичная программа на C/Assembler. Кто попробует переписать? :)

У нас действительно огромное количество рекурсивных вызовов, поэтому (возможно) оптимизировать можно было бы, если переписать решение через цикл или бить рекурсию на части, которые после запускать в разных потоков, чтобы добиться хоть какой-то псевдопараллельности выполнения.

Ссылка на код github

github.com

GitHub - HaloMath/Recursion-task-with-a-performer-from-the-Unified-State-Exam-: Recursion, a task with a performer from the Unified State Exam in computer science