РЕШЕНИЕ 23 НОМЕРА (1/3)

Шаблон решения

Для задач без дополнительных условий используется следующий прототип:

1
2
3
4
5

Логика проста: из каждого числа пробуем применить все команды и считаем суммарное количество успешных путей до цели.

Задача 1. Условие

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

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

B. Прибавить 2

C. Прибавить 3

Программа — это последовательность команд. Сколько существует программ, которые преобразуют число 5 в число 15?

Решение

1
2
3
4
5
6

Ответ: 274

Задача 2. Условие

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

A. Прибавить 2

B. Прибавить 5

C. Возвести в квадрат

Сколько существует программ, для которых при исходном числе 4 результатом является число 36, при этом последняя команда — не C?

Разбор

Нужно из 4 получить 36. Условие «последняя команда  не C» означает, что в момент получения 36 последний шаг должен быть A (+2) или B (+5). Это учитывается в коде: считаем общее количество путей до 36, но добавляем параметр, какая команда применялась последней (каждый раз, когда мы делаем ход, записываем в этот параметр соответствующий ход).

Решение

1
2
3
4
5
6

Важно понимать пару вещей,(x == y and last == "C") если у нас такая ситуация, то функция должна возвращать 0last != "C": - так мы проверяем, что последняя команда не равна третьейЕсли бы траектория начинала бы работу с 1 или 0, необходимо было дописывать доп проверки, ведь f(x ** 2, y, "C") не может выполняться при этих числах, так как рекурсия станет бесконечной

Ответ: 319