Рекурсия и фишки

Question

Рекурсия и фишки

Рейтинг: 3Ответов: 1Опубликовано: 15.06.2011

Есть задача о фишках, необходимо ее решить рекурсией, вот условие:

Дана полоска из клеток, пронумерованных от 1 до N. Разрешено снимать или ставить фишку на первую клетку или на клетку, следующую за самой левой фишкой. Изначально строка пуста. Нужно занять все клетки. Формат входного файла

С клавиатуры вводится натуральное число N (1 ≤ N ≤ 10).

Формат выходного файла

Требуется вывести последовательность номеров клеток, с которыми совершается действие. Если фишка снимается, то номер клетки должен выводиться со знаком минус. Количество действий не должно превышать 10000. Если существует несколько возможных решений задачи, то разрешается вывести любое.

Примеры
Ввод 3
Вывод 1 2 -1 3 1

Я решаю так:

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;
}

Прошу помощи, что я делаю неправильно? Знаю, что переменная first лишняя, она говорит о том был ли запущен метод из main'а. Данный код решает задачу для n = 1,2,3. Для n = 4, он выдает
1 2 -1 3 -3 -2 -1 4 1 2 -1
вместо
1 2 -1 3 -3 -2 -1 4 1 2

c#

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

выдает 1 2 -1 3 -3 -2 -1 4 1 2 -1

вместо 1 2 -1 3 -3 -2 -1 4 1 2

А почему вы считаете, что 3 -3 правильно? Ведь вы ставите фишку, а потом сразу её убираете.. какой в этом смысл? Зачем тогда было её туда ставить?

Я написал для самотренировки рекурсию с одним параметром и у меня вышло следующее

1 2 -1 3 -2 4 2 1

UPD По просьбе трудящихся привожу свой код. Надеюсь, вы простите меня, что я написал на Java, так как мне было сподручнее. Исправить обратно на C будет совсем просто.

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();
    }
}

Объяснение простое. Сначала мы пытаемся захватить самую правую клетку. Для этого мы берём текущую, затем берём следующую, а потом снимаем текущую. Но снимаем только если мы не захватили последнюю (если мы захватили последнюю, то это значит, что клетка за ней тоже захвачена, а раз так, то у нас захвачено две последних клетки и снимать клетку не имеет смысла). Далее, начинаем всё по новой начиная с первой клетки до тех двух последних, которые были захвачены на предыдущей итерации. И так повторяем проходы слева направо отщипывая от линейки по две концевые до тех пор, пока всё не будет заполнено. Очевидно, сложность будет N / 2 проходов, каждый проход ~2n шагов.. n уменьшается каждый раз на два.. арифметическая прогрессия получается.. вам не составит труда оценить, что для N=10 будет точно меньше 10000. Да и эксперимент подтвердит ;)

Рекурсия и фишки

Ответы