Question

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

Answer 1

составляем таблицу(см. вложение)

Ответ: 10

Answer 2

Для решения этой задачи мы можем использовать рекурсивный подход. Давайте рассмотрим каждую команду отдельно.

Пусть f(n) - это количество программ, которые при исходном числе 1 приводят к числу n, и при этом траектория вычислений содержит число 25 и не содержит число 10.

Тогда:

1. Если n = 25, то это означает, что мы уже достигли числа 25. Так как нам нужно, чтобы траектория вычислений содержала число 25, то это может быть только одна команда: увеличение на 1 (f(24)). Следовательно, f(25) = f(24).

2. Если n = 10, то это означает, что мы достигли числа 10, что недопустимо. Поэтому f(10) = 0.

3. Если n < 10, то мы можем рассмотреть только команду увеличения на 1, так как умножение на 2 даст число больше 10. Таким образом, f(n) = f(n-1).

4. Если n > 25 и не является степенью числа 2, то также недопустимо, потому что умножение на 2 даст число, которое не может быть достигнуто при стартовом числе 1. Таким образом, f(n) = 0.

Теперь давайте построим таблицу для значений f(n):

scssCopy code
n   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| ... | 24 | 25 | 26 | 27 | 28 | ...
f(n)| 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 0 | ... | 0  | f(25)| 0  | 0  | 1  | ...

Мы можем вычислить значения f(n) рекурсивно, начиная с f(1) и идя вперед, пока не достигнем f(28).

scssCopy code
f(1) = f(1-1) = f(0) = 0
f(2) = f(2-1) = f(1) = 0
f(3) = f(3-1) = f(2) = 1
f(4) = f(4-1) = f(3) = 1
f(5) = f(5-1) = f(4) = 2
f(6) = f(6-1) = f(5) = 2
f(7) = f(7-1) = f(6) = 3
f(8) = f(8-1) = f(7) = 3
f(9) = f(9-1) = f(8) = 4
f(10) = 0 (недопустимо)
...
f(25) = f(24) = 4
f(26) = 0 (недопустимо)
f(27) = 0 (недопустимо)
f(28) = f(27) + f(24) = 0 + 4 = 4

Таким образом, существует 4 различных программы, которые приведут к числу 28, при условии, что траектория вычислений содержит число 25 и не содержит число 10.