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