Python. Рекурсии.
Фишки
Дана полоска из клеток, пронумерованных от 1 до N слева направо. Разрешено снимать или ставить фишку на клетку с номером 1 или на клетку, следующую за самой левой из установленных фишек (правее неё), если она пуста. Изначально полоска пуста. Нужно разместить фишки во всех клетках.
Входные данные
Программа получает на вход количество клеток в полоске N(1≤N≤10).
Выходные данные
Программа должна вывести последовательность номеров клеток, с которыми совершается действие. Если фишка снимается, то номер клетки должен выводиться со знаком минус. Количество действий не должно превышать 104. Если существует несколько возможных решений задачи, то разрешается вывести любое.
Примеры:
Ввод:
3
Вывод:
1 2 -1 3 1
Программа(работает только с нечётными числами, на других зависает):
from sys import setrecursionlimit
setrecursionlimit(10**9)
def f(a,i):
if a == 1:
print(1,end = ' ')
elif i == a - 1:
print(i+1,end = ' ')
f(a-2,1)
else:
print(i+1,-i,end = ' ')
f(a,i+1)
a = int(input())
print(1,end = ' ')
f(a,1)
ответ: в одной строке 60 символов.
Var
n,i,j,resi,resj,flag:integer;
begin
flag:=0;
i:=1;
readln(n);
while power(i,3)<n do
begin
j:=1;
while power(j,3)+power(i,3)<=n do
begin
if power(j,3)+power(i,3)=n then
begin
flag:=1;
resi:=i;
resj:=j;
break;
end;
inc(j);
end;
if flag=1 then break;
inc(i);
end;
if flag=1 then writeln(resi,' ',resj,' ',resj,' ',resi) else writeln('impossible');
end.
Пример ввода:
1008 //2^3+10^3
Пример вывода:
2 10 10 2