Главная » Исполнитель Июнь15 .. Прибавить 1.. Умножить на 2
16:53

Исполнитель Июнь15 .. Прибавить 1.. Умножить на 2


Задание:

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Прибавить 3
Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 20 и при этом траектория вычислений содержит число 10? 

Решение: 

Составим формулу от обратного:

F(n) = F(n-1) + F(n/2) + F(n-3);

F(n/2) - только для четных n.

F(4) = 1, изначально одна программа есть.
F(5) = F(4) + F(2) = 1 + 0 = 1
F(6) = F(5) + F(3) + F(3) = 1 + 0 + 0 = 1
F(7) = F(6) + F(4) = 1 + 1 = 2
F(8) = F(7) + F(4) + F(5) = 2 + 1 + 1 = 4
F(9) = F(8) + F(6) = 4 + 1 = 5
F(10) = F(9) + F(5) + F(7) = 5 + 1 + 2 = 8

Далее работаем с формулой и числами, вычисления которых содержат 10.

F(11) = F(10) + F(8) = 8, F(8) не подходит по траектории.
F(12) = F(11) + F(6) + F(9) = 8, F(6) и F(9) не подходят нам.
F(13) = F(12) + F(10) = 8 + 8 = 16
F(14) = F(13) + F(7) + F(11) = 16 + 8 = 24, F(7) не подходит.
F(15) = F(14) + F(12) = 24 + 8 = 32
F(16) = F(15) + F(8) + F(13) = 32 + 16 = 48, F(8) не подходит.
F(17) = F(16) + F(14) = 48 + 24 = 72
F(18) = F(17) + F(9) + F(15) = 72 + 32 = 104, F(9) не подходит.
F(19) = F(18) + F(16) = 104 + 48 = 152
F(20) = F(19) + F(10) + F(17) = 152 + 8 + 72 = 232

Ответ: 232


Похожие материалы:
Нашли ошибку на сайте? Напишите в комментариях!
Категория: Информатика и ИКТ | Просмотров: 1233 | Добавил: Ученик | Рейтинг: 4.0/2