Задача 5787. Источник: Поляков. Задание КИМ 23
(М. Байрамгулов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавь 1
- Умножь на 3
- Прибавь предыдущее
Выполняя первую из них, исполнитель увеличивает число на экране на 1, выполняя вторую – умножает на 3, выполняя третью – прибавляет предыдущее значение (полученное после предпоследней выполненной операции). Программой для исполнителя называется последовательность команд. Сколько существует программ, которые преобразуют число 2 в число 27?
Решение
Напишем рекурсивную функцию, которая по текущему числу n и результату предпоследней команды last вернет количество программ.
Python
def r(n, last=0):
if n > 27:
return 0
if n == 27:
return 1
k = r(n + 1, n) + r(n * 3, n)
if last != 0:
k += r(n + last, n)
return k;
print(r(2))
PascalABC
begin
if n > 27 then
Result := 0
else if n = 27 then
Result := 1
else
begin
Result := r(n + 1, n) + r(n * 3, n);
if last <> 0 then
Result := Result + r(n + last, n);
end;
end;
begin
Writeln(r(2));
end.
C++
#include <iostream>
using namespace std;
int r(int n, int last = 0)
{
if (n > 27)
return 0;
if (n == 27)
return 1;
int k = r(n + 1, n) + r(n * 3, n);
if (last != 0)
k += r(n + last, n);
return k;
}
int main()
{
cout << r(2) << endl;
}
Ответ
135