Рассмотрим следующее задания типа КЕГЭ
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Первая из них увеличивает число на экране на 1, вторая увеличивает число в 2 раза, третья увеличивает число в 3 раза.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 10 результатом является число 374, и при этом в программах нет трех одинаковых команд, идущих подряд?
Как решать такой тип заданий?
Усложним вопрос - Найдите все траектории, которые переводят число S в число F (S=10, F=374)
Пусть t - некоторый набор команд, например t='123112'. Тогда через t(S) обозначим результат этой траектории:
t(S)='123112'(10)= ((10+1)*2*3+1+1)*2=136 - значение t(S)< F, значит эту траекторию можно "продолжать"
(если бы t(S) было бы больше F, про эту траекторию можно забыть)
Можно считать, что был организован обход графа по "некоторым путям".
Попробуем составить программу.
- Создадим словарь Track с начальными значениями {'1':11,'2':20,'3':30} (возможен вариант {'':10}
- Можем создать словарь Answer ={} для итоговых траекторий
- Далее попробуем "заменять" команды из Track на "более длинные" (если их значение меньше F)
- Признаком окончания будет "обнуление" Track