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