У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. прибавь 3
3. умножь на 3
Сколько есть программ, которые число 1 преобразуют в число 15?

Обозначим через \(f(n)\) количество программ, которые получают число \(n\) из числа \(1\).

К числу \(n\) можно прийти тремя способами: из \(n-1\) командой «прибавь 1», из \(n-3\) командой «прибавь 3», а если \(n\) делится на \(3\), то из \(\frac{n}{3}\) командой «умножь на 3».

Считаем последовательно:

\(f(1)=1\), \(f(2)=1\), \(f(3)=2\), \(f(4)=3\), \(f(5)=4\), \(f(6)=7\), \(f(7)=10\), \(f(8)=14\), \(f(9)=23\), \(f(10)=33\), \(f(11)=47\), \(f(12)=83\), \(f(13)=116\), \(f(14)=163\), \(f(15)=251\).

Ответ: существует \(251\) программа.

0 0 Пожаловаться