weixin_43113933 2020-07-05 23:21 采纳率: 58.3%
浏览 123
已采纳

一个关于8皇后回溯递归,全局变量失效的超大疑惑?

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
using namespace std;
bool d[16]= {0},b[9]= {0},c[16]= {0};
int sum=0,a[9];
int search(int);
int print();
int main()
{
    search(1);//从第1个皇后开始放置
}
int search(int i)
{
    int j;
    for (j=1; j<=8; j++)//每个皇后都有8位置(列)可以试放
        if ((!b[j])&&(!c[i+j])&&(!d[i-j+7]))//寻找放置皇后的位置
            //由于C++不能操作负数组,因此考虑加7
        {
            //放置皇后,建立相应标志值
            a[i]=j;//摆放皇后
            b[j]=1;//宣布占领第j列
            c[i+j]=1;//占领两个对角线
            d[i-j+7]=1;
            if (i==8)
            {

                print();//8个皇后都放置好,输出
            }
            else
                search(i+1);//继续递归放置下一个皇后
            b[j]=0;//递归返回即为回溯一步,当前皇后退出
            c[i+j]=0;
            d[i-j+7]=0;
        }
}
int print()
{
    int i;
    sum++;//方案数累加1
    cout<<"sum="<<sum<<endl;
    for (i=1; i<=8; i++)//输出一种方案
        cout<<setw(4)<<a[i];
    cout<<endl;
}
网上这个解决8皇后问题的,逻辑对的,现在问题是sum失效,并没有起到全局变量的效果,这点特别苦恼,没想明白。sum输出总是循环输出。前41种方案还在正常的累加统计,后面的就开始输出2了,此后又从1开始,循环,无规则。全局变量按道理就是单纯累加统计,不管是不是递归才是。特别苦恼,难道还有深层次的原因吗

sum=40
4 7 1 8 5 2 6 3
sum=41
4 7 3 8 2 5 1 6
sum=2
4 7 5 2 6 1 3 8
sum=1
4 7 5 3 1 6 8 2
sum=2
4 8 1 3 6 2 7 5
sum=3
4 8 1 5 7 2 6 3
sum=4
4 8 5 3 1 7 2 6
sum=5
5 1 4 6 8 2 7 3

  • 写回答

1条回答 默认 最新

  • 胖狗子修行之路 2020-07-06 11:45
    关注

    改成这样可以解决,具体原因我也懵逼了,蹲一个大佬

    int a[9], sum = 0;
    

    预测一波数组越界

    破案
    修改:

    c[17]= {0}
    

    即可
    原因:
    i 和 j都有可能取到8的值,c[i+j]越界
    验证

                if (i==8)
                {
                    cout << i << " " << j << endl;
                    print();//8个皇后都放置好,输出
                }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题