Главная » Исполнитель Июнь15 преобразует число на экране...
21:12

Исполнитель Июнь15 преобразует число на экране...


Задание:

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

Решение через формулу:

* f(n) = f(n-1) + f(n/2) + f(n/3)

f(n/2) - применяется только к четным числам.
f(n/3) - применяется только к числам, кратным трём.

Считаем:
f(2) = 1 - изначально имеется одна программа.
f(3) = f(n-1) + f(n/3) = f(2) + f(1) = 1 + 0 = 1
f(4) = f(4-1) + f(4/2) = f(3) + f(2) = 1 + 1 = 2
f(5) = f(5-1) = f(4) = 2
f(6) = f(6-1) + f(6/2) + f(6/3) = f(5) + f(3) + f(2) = 2 + 1 + 1 = 4
f(7) = f(7-1) = f(6) = 4

По условию траектория вычислений содержит число 7:
f(8) = f(n-1) + f(n/2) = f(7) + f(4), f(4) нам не подходит, остается только f(7) = 4
f(9) = 4 - аналогично.
f(10) = 4
f(11) = 4
f(12) = 4
f(13) = 4
f(14) = f(14-1) + f(14/2) = f(13) + f(7) = 4 + 4 = 8
f(15) = f(15-1) + f(15/3) = f(14) + f(5), f(5) нам не подходит, f(14) = 8
f(16) = f(16-1) + f(16/2) = f(15) + f(8), f(8) подходит по траектории = 8 + 4 = 12
f(17) = f(17-1) = f(16) = 12
f(18) = f(18-1) + f(18/2) + f(18/3) = f(17) + f(9) + f(6)= 12 + 4 = 16
f(19) = f(19-1) = f(18) = 16
f(20) = f(20-1) + f(20/2) = f(19) + f(10) = 16 + 4 = 20
f(21) = f(21-1) + f(21/3) = f(20) + f(7) = 20 + 4 = 24
f(22) = f(22-1) + f(22/2) = f(21) + f(11) = 24 + 4 = 28
f(23) = f(23-1) = f(22) = 28
f(24) = f(24-1) + f(24/2) + f(24/3) = f(23) + f(12) + f(8) = 28 + 4 + 4 = 36
f(25) = f(25-1) = f(24) = 36
f(26) = f(26-1) + f(26/2) = f(25) + f(13) = 36 + 4 = 40
f(27) = f(27-1) + f(27/3) = f(26) + f(9) = 40 + 4 = 44
f(28) = f(28-1) + f(28/2) = f(27) + f(14) = 44 + 8 = 52

Ответ: 52

Если непонятно, по какой причине f(15) не подходит, или в f(18) мы не сложили f(6), они нам не подходят, так как по условию вычисления должны проходить через число 7:
по команде прибавь 1 нам подходят абсолютно все числа.
по команде умножь на 2 нам не подошли четные числа 8, 10, 12, так как вычисление этих чисел не проходит через число 7.
по команде умножь на 3 нам не подошли 9, 12, 15, 18 по аналогичной причине.


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