Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
-
Удвоить
-
Удвоить и прибавить
Первая команда умножает число на экране на 2, вторая — умножает его на 2, а затем прибавляет 1.
Программа для исполнителя — это последовательность команд. Например, программа 121 при исходном числе 3 последовательно получит числа 6, 13 и 26. Результатом программы будет число 26.
Сколько различных результатов можно получить из исходного числа 1 после выполнения программы, содержащей ровно 9 команд?
Решение:
Решение на Python:
a = []
def F(x, k):
if k > 9:
return
if k == 9:
a.append(x)
return
F(x * 2, k + 1)
F(x * 2 + 1, k + 1)
F(1, 0)
print(len(set(a)))Ответ: 512
Ответ:
512