There is a problem about chips, it is necessary to solve it by recursion, here is the condition:

A strip of cells numbered from 1 to N is given. It is allowed to remove or place a chip on the first cell or on the cell next to the leftmost chip. Initially, the string is empty. Need to take all the cells. Input file format

A natural number N is entered from the keyboard (1 ≤ N ≤ 10).

Output file format

It is required to display a sequence of numbers of cells with which the action is performed. If the chip is removed, the cell number should be displayed with a minus sign. The number of actions should not exceed 10,000. If there are several possible solutions to the problem, then it is allowed to output any.

Examples
Input 3
Conclusion 1 2 -1 3 1

I decide like this:

void F(int n, int i, const bool first = false) { if (n > 0) { F (n - 1, i - 1); cout << i << " "; if (!first) F(n - 1, 1 - n); else F(n - 2, n - 2); } } int main() { cin >> n; F(n, n, true); return 0; }

Please help, what am I doing wrong? I know that the first variable is superfluous, it says whether the method from the main has been launched. This code solves the problem for n = 1,2,3. For n = 4, it yields
1 2 -1 3 -3 -2 -1 4 1 2 -1
instead
1 2 -1 3 -3 -2 -1 4 1 2



    1 answer 1

    gives out 1 2 -1 3 -3 -2 -1 4 1 2 -1

    instead of 1 2 -1 3 -3 -2 -1 4 1 2

    And why do you think that 3 -3 is correct? After all, you put the chip, and then immediately remove it .. what's the point? Why then was it put there?

    I wrote a recursion with one parameter for self-training and I got the following

    1 2 -1 3 -2 4 2 1

    UPD At the request of workers give my code. I hope you forgive me for writing in Java, since it was more convenient for me. Fix it back to C will be quite easy.

     package cg; import java.io.BufferedReader; import java.io.InputStreamReader; /** * @author Sergey Mashkov */ public class Main { private void processCell(int cell, int N) { if (cell <= N) { printCell(cell); if (cell < N) { if (cell > 1) { printNegateCell(cell - 1); } processCell(cell + 1, N); } } } private void processCells(int N) { if (N > 0) { processCell(1, N); processCells(N - 2); } } private void printNegateCell(int cell) { System.out.print('-'); printCell(cell); } private void printCell(int cell) { System.out.print(cell); System.out.print(' '); } public static void main(String[] args) throws Exception { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(reader.readLine().trim()); new Main().processCells(N); System.out.println(); } }

    The explanation is simple. First we try to capture the rightmost cell. To do this, we take the current one, then take the next one, and then remove the current one. But we only remove if we haven’t captured the last one (if we captured the last one, it means that the cell behind it is also captured, and if so, then the last two cells are captured from us and it does not make sense to shoot the cell). Next, we start everything on a new one, starting from the first cell to the last two, which were captured at the previous iteration. And so we repeat the passages from left to right, pinching two end pins from the ruler until everything is filled. Obviously, the complexity will be N / 2 passes, each pass ~ 2n steps .. n decreases each time by two .. arithmetic progression turns out .. you will not be difficult to estimate that for N = 10 it will be exactly less than 10,000. Yes, and the experiment will confirm; )

    • I apologize, my joint, if not difficult, could you throw off your code? - strbb
    • Unfortunately, this is a partial solution, but thanks anyway, I'll try to finish it. PS at N = 7 in your decision the answer ends with 5 4 3 2 1, so it is impossible - strbb
    • I must have misunderstood the conditions of the problem. In this case, do I understand correctly that for N = 4 the solution is "1 2 -1 3 -2 4 1 2", and for N = 7 - "1 2 -1 3 -2 4 -3 5 -4 6 - 5 7 1 2 -1 3 -2 4 -3 5 1 2 -1 3 1 "? - cy6erGn0m
    • I corrected the answer to fit the solution above. - cy6erGn0m