Примеры решений прототипа №1

ПРИМЕРЫ РЕШЕНИЯ

№ 633 Джобс 02.11.2020 (Уровень: Базовый)

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

1. прибавь 1

2. умножь на 2

3. возведи в квадрат

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

def f(x, y):
    if x >= y: return x == y
    return f(x + 1, y) + f(x * 2, y) + f(x ** 2, y)
print(f(5, 154))

№ 1036 100 базовых задач Е. Джобс (Уровень: Базовый) Исполнитель преобразует число на экране.   У исполнителя есть две команды, которым присвоены номера:   1. Прибавить 1   2. Умножить на 2   Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.   Сколько существует программ, для которых при исходном числе 1 результатом является число 30, при этом траектория вычислений не проходит через 10?

def f(x, y):
    if x == 10: return 0
    if x >= y: return x == y
    return f(x + 1, y) + f(x * 2, y)
print(f(1, 30))

 

№ 11841 (Уровень: Базовый)

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

А. Вычесть 2
В. Вычесть 3
С. Найти целую часть от деления на 5

Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 41 результатом является число 5, при этом траектория вычислений не содержит числа 20 и содержит 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы СВА при исходном числе 51 траектория будет состоять из чисел 10, 7, 5

def f(x, y):
    if x == 20: return 0
    if x < y: return 0
    if x == y: return 1
    return f(x - 2, y) + f(x - 3, y) + f(x // 5, y)

print(f(41, 10) * f(10, 5))