0

这是我的问题，对于一个练习，我需要通过在回溯中对其进行暴力破解来生成一个魔方。

我认为将矩阵分配为向量和更改坐标的函数可能很有用。正如您可以想象的那样，即使使用 3x3 幻方，它也给了我一个堆栈溢出问题。

调试它我发现它或多或少发生在生成的一半，更准确地说是函数chk_magic(int *m, int n)调用的位置change_coord(i, j, m, n);。

这是整个代码，我在其中签署了中断程序的行。

#include <stdio.h>
#include <stdlib.h>

int chk_magic(int*, int);
void generate_magic(int*, int, int);
int change_coord(int, int, int*, int);

int back_f;

int main()
{
    int i, j, n=3, *m;
    //printf("Inserisci la dimensione del quadrato: ");
    //scanf("%d", &n);

    m=malloc(n*n*sizeof(int*));
    for(i=0; i<(n*n); i++)
    {
        m[i]=1;
    }
    printf("Generazione in corso (se la dimensione e' maggiore di 4 potrebbero volerci minuti)...\n");
    generate_magic(m, n, n*n-1);
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            printf("%3d ", change_coord(i, j, m, n));
        }
        printf("\n");
    }

    return 0;
}

int chk_magic(int *m, int n)
{
    int i, j, magic_n, orizzontal_buffer, vertical_buffer, flag;
    flag=0;
    magic_n=n*(n*n + 1)/2;

    for(i=0; i<n; i++)
    {
        orizzontal_buffer=0;
        vertical_buffer=0;

        for(j=0; j<n; j++)
        {
            orizzontal_buffer+=change_coord(i, j, m, n); // <<-- HERE! HALP!
            vertical_buffer+=change_coord(j, i, m, n);
        }
        if(vertical_buffer!=magic_n || orizzontal_buffer!=magic_n)
        {
            flag=1;
            return flag;
        }
    }
    orizzontal_buffer=0;
    vertical_buffer=0;
    for(i=0, j=n-1; i<n; i++, j--)
    {
        orizzontal_buffer=change_coord(i, i, m, n);
        vertical_buffer=change_coord(i, j, m, n);
    }
    if(vertical_buffer!=magic_n || orizzontal_buffer!=magic_n)
        {
            flag=1;
        }

    return flag;
}

void generate_magic(int *m, int n, int pos)
{
    if(m[pos]<n*n)
    {
        m[pos]++;
        back_f=chk_magic(m, n);
        if(back_f==0)
        {
            return;
        }
        generate_magic(m, n, n*n-1);
        return;
    }
    if(m[pos]==n*n)
    {
        if(back_f==0)
        {
            return;
        }
        m[pos]=1;
        generate_magic(m, n, pos-1);
        return;
    }
    if(pos==-1)
    {
        return;
    }
    return;
}

int change_coord(int x, int y, int *m, int dim)
{
    return m[(x*dim)+y];
}

谷歌搜索我发现对于奇数有一种算法可以很容易地生成它，但是对于偶数问题仍然存在（此外，我的教授希望它具有暴力递归）。

任何可能的解决方案？

4

1 回答 1

1

这是家庭作业，所以我不打算修复您的代码......但是我会为您做一些分析以向您展示问题。仅供参考：您确实应该学习使用调试器并跟踪您的代码。

你的大问题是你的“递归”逻辑只是在两个块之间来回反弹，没有“最低步骤”，因此你用太多的函数调用填充缓冲区并获得堆栈溢出：

void generate_magic(int *m, int n, int pos)
{
    if(m[pos]<n*n)
    {
        m[pos]++;
        back_f=chk_magic(m, n);
        if(back_f==0)
        {
            return;
        }
        generate_magic(m, n, n*n-1);  <--- 'Recursive' step

所以当你调用这个函数时，你有m* == your memory block,n == 3和pos == 8(3*3-1)。

我将“递归”放在引号中，因为您没有执行递减步骤，此代码每次generate_magic()使用相同的参数一遍又一遍地调用（n始终为 3，pos始终为 8）

经过几次迭代后m[pos]，将从 1 增加到 9，现在如果检查失败，我们跳到下一个块：

if(m[pos]==n*n)
{
    if(back_f==0)
    {
        return;
    }
    m[pos]=1;
    generate_magic(m, n, pos-1);  <- 'Recursive' step

所以现在我们将代码集 m[pos] 从前一个值 (9) 输入到我们从 (1) 开始的值，然后我们执行“递归”步骤，generate_magic()使用值 ( n==3、pos=7和m[pos]==1)调用

好的，所以这次我们用不同的值重新开始，对吧？我们第一次有：

n == 3pos == 8
现在我们有
n == 3：和pos == 7

糟糕，但是当我们再次点击第一个“递归”调用时会发生什么？

generate_magic(m, n, n*n-1);

这会将我们的下一个条目重置为：

n == 3和pos == 8

这进展得很快。所有这些压栈的函数/参数迟早会杀死我们，因为我们进入了一个无限循环。

边注：

malloc(n*n*sizeof(int*));

你想要sizeof(int)，不是sizeof(int*)因为你是int矩阵中的字符串，而不是指向ints 的指针。

于 2013-05-07T13:25:15.617 回答