Задача 7489 У исполнителя Удвоитель две команды,...

YanMarkov

07.03.2016

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

1. прибавь 1,
2. умножь на 2.

Первая из них увеличивает число на экране на 1, вторая удваивает его.

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

Пусть n - конечное число, К(n) - количество программ, которые число 3 преобразуют в число n.
Cоставим рекуррентную формулу для определения числа программ получения числа:
При n = 3 имеем K(3) = 1.
Если n не кратно 2: К(n) = K(n-1)
Если n делится на 2: K(n) = K(n-1) + K(n/2)

Начинаем с конца.
N = 8. Делится на два, значит K(8) = K(7) + K(4)
N = 7. Не делится на два, значит K(7) = K(6)
N = 6. Делится на два, значит K(6) = K(5) + K(3)
N = 5. Не делится на два, значит K(5) = K(4)
N = 4. Делится на два, значит K(4) = K(3) + K(2) (K(2) не существует, берем как ноль)

Знаем, что K(3) = 1, подставляем в другие формулы:
К(4) = K(3) + K(2) = 1 + 0 = 1
К(5) = К(4) = 1
K(6) = K(5) + K(3) = 1 + 1 = 2
K(7) = K(6) = 2
К(8) = K(7) + K(4) = 2 + 1 = 3 - ответ.

Ответ: 3