Развертывание переменной не так, как ожидалось при использовании рекурсии - PullRequest
Новая
       27

Развертывание переменной не так, как ожидалось при использовании рекурсии

0 голосов
/ 19 апреля 2020

Заранее спасибо за ваше время :). Когда я пытался реализовать NQueens, я как бы наблюдал случай, когда ... экземпляр переменных после рекурсии обычно разворачивается в стеке, как в моем случае со всеми переменными, кроме одного двумерного массива. Это не разворачивается ... вместо того, чтобы оставаться таким, каким он был на последнем рекурсивном вызове ... спасибо, что нашли время помочь, спасибо = D.

Место выпуска ... переменная " доска [100] [100] "не разворачивается, вместо этого, как уже было сказано, она остановилась на последнем случае рекурсивного вызова. Я ожидаю, что это будет как 1-я королева, 2-я королева, 3-я королева и 3-я королева, 2-я королева поместил, 1-ая королева помещена точно так же как переменная placed. Или я думаю, может быть, именно так оно и должно работать, однако я хочу знать логическое объяснение его поведения по поводу того, почему переменная "board" не раскрывается. 

void foo(bool board[100][100], int x, int y, int n, int m, int placed)
{
    if( placed == n )
    {
        display(board, n, m);

        return ;
    }

    int i, j;

    for(i=x; i<=n; i++)
    {
        for(j=y; j<=m; j++)
        {
            if( checkBoard(board, n, m, i, j) )
            {
                board[i][j] = true;

                display(board, n, m);
                cout<<placed;

                foo(board, 1, 1, n, m, placed+1);

                display(board, n, m);
                cout<<placed;
            }
        }
    }
}

My Выходные данные -> Как видите, переменная с именем "pped "разворачивается, как и ожидалось, но это не так, как в случае этого двумерного массива с именем" board [100] [100] ".

Весь код: - 

#include <bits/stdc++.h>

using namespace std;

int display(bool board[100][100], int n, int m)
{
    int i, j;

    cout<<"\n===============================================\n\n";

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if( board[i][j] )
            {
                cout<<"|Q|";
            }

            else
            {
                cout<<"|_|";
            }
        }

        cout<<'\n';
    }

    cout<<"\n===============================================\n";
}

bool checkBoard(bool board[100][100], int n, int m, int x, int y)
{
    int i, j;

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if( board[i][j] and ( (x==i or y==j) or (abs(x-i)==abs(y-j)) ) )
            {
                return false;
            }
        }
    }

    return true;
}

void foo(bool board[100][100], int x, int y, int n, int m, int placed)
{
    if( placed == n )
    {
        display(board, n, m);

        return ;
    }

    int i, j;

    for(i=x; i<=n; i++)
    {
        for(j=y; j<=m; j++)
        {
            if( checkBoard(board, n, m, i, j) )
            {
                board[i][j] = true;

                display(board, n, m);
                cout<<placed;

                foo(board, 1, 1, n, m, placed+1);

                display(board, n, m);
                cout<<placed;
            }
        }
    }
}

int main(void)
{
    int i, j,
        n = 4,
        m = 4;

    bool board[100][100];

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            board[i][j] = false;
        }
    }

    foo(board, 1, 1, n, m, 0);

    return 0;
}

1 Ответ

0 голосов
/ 19 апреля 2020

Для будущего меня или любого, кто застрянет с той же проблемой, это то, что массив - это не просто массив переменных, это больше похоже на указатель на переменную (блок памяти во дворце памяти). Так что рекурсия, переменные будут возвращены к своим предыдущим значениям после успешного вызова рекурсии в стеке, однако эти массивы или указатели не делают, поскольку массивы или указатели просто указывают. Таким образом, значения в блоке памяти будут одинаковыми, если только они не будут изменены явно / вручную, но их нельзя развернуть / откатить к предыдущим экземплярам при развертывании рекурсии.

Этот код, который я написал час go, помог мне понять это надеюсь, это поможет другим ... 

#include <bits/stdc++.h>

using namespace std;

void display(int a[5][5], int b[5])
{
    int i, j;

    cout<<"\n===============================================\n";

    for(i=0; i<5; i++)
    {
        for(j=0; j<5; j++)
        {
            cout<<a[i][j]<<' ';
        }

        cout<<'\n';
    }

    cout<<"\n-----------------------------------------------\n";

    for(i=0; i<5; i++)
    {

        cout<<b[i]<<' ';
    }

    cout<<"\n===============================================\n";
}

void foo(int i, int j, int a[5][5], int b[5], int var, int *temp)
{
    if( i == 5 )
    {
        return ;
    }

    a[i][j] = b[i] = 1;

    display(a, b);
    cout<<var<<' '<<*temp;

    foo(i+1, j+1, a, b, var++, &(++*temp));

    display(a, b);
    cout<<var<<' '<<*temp;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int i, j, a[5][5], b[5], *temp, alpha;

    temp = &(alpha = 0);

    for(i=0; i<5; i++)
    {
        for(j=0; j<5; j++)
        {
            a[i][j] = 0;
        }

        b[i] = 0;
    }

    foo(0, 0, a, b, 0, temp);

    return 0;
}

Кроме того, обратите внимание, что foo(i+1, j+1, a, b, var++, &(++*temp)); здесь *temp следует предварительно увеличивать, но не публиковать, поскольку *temp уже будет назначено и не может быть обновлено по неизвестной причине ... Все это основано на моей интуиции и нескольких экспериментах без надлежащего исследования и, вероятно, все они могут быть неверны фактическому объяснению, поэтому, пожалуйста, не стесняйтесь исправлять меня.

...