| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1318 人关注过本帖
标题:凌晨用自己理解的回溯法写的一道关于四皇后的问题
只看楼主 加入收藏
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
结帖率:86%
收藏
已结贴  问题点数:20 回复次数:10 
凌晨用自己理解的回溯法写的一道关于四皇后的问题
程序运行正确,但没有输出结果,是不是数据溢出了的问题,望各位大神指点一下^_^
程序代码:
#include<stdio.h>
int count=0;
int H[4][4];
int pai(int i,int j)
{
    int s,t;
    for(s=i,t=0;t<0;t++) //判断行 
    if(H[s][t]==1&&t!=j)
    return 0;
    
    for(s=0,t=j;j<0;j++) //判断列 
    if(H[s][t]==1&&s!=i)
    return 0;
    
    for(s=i-1,t=j-1;s>=0,t>=0;s--,t--) //判断左上方 
    if(H[s][t]==1)
    return 0;
    
    for(s=i-1,t=j+1;s>=0,j<4;s--,t++) //判断右上方 
    if(H[s][t]==1)
    return 0;
    
    for(s=i+1,t=j-1;s<4,t>=0;s++,t--) //判断左下方 
    if(H[s][t]==1)
    return 0;
    
    for(s=i+1,t=j+1;s<4,t<4;s++,t++) //判断右下方 
    if(H[s][t]==1)
    return 0;
    
    return 1;  
}
void huang(int j)
{
    if(j==4)
        count++;
    for(int i=0;i<4;i++){
        if(pai(i,j)){
            H[i][j]==1; //插入皇后 
            huang(j+1); //继续搜索下一个 
            H[i][j]==0; 
        }
    }
}
int main()
{
    int i,j;
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            H[i][j]=0; 
    huang(0); //还原 
    printf("Answer:",count);
    getchar();
}
搜索更多相关主题的帖子: color 
2016-03-15 02:50
grmmylbs
Rank: 14Rank: 14Rank: 14Rank: 14
等 级:贵宾
威 望:54
帖 子:1409
专家分:5845
注 册:2016-2-14
收藏
得分:7 
先把3个编译告警处理了再调试。
2016-03-15 09:01
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:7 
楼主能不能给讲讲:你在哪里回溯的?怎么实现回溯的?

能编个毛线衣吗?
2016-03-15 10:23
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
收藏
得分:0 
回复 2楼 grmmylbs
我用dev-c++写的,编译时没有警告。只有这个:
图片附件: 游客没有浏览图片的权限,请 登录注册

做一名健壮的技术青年,如果未来无法用代码去改变世界,还可以考虑去搬砖。
2016-03-16 09:33
grmmylbs
Rank: 14Rank: 14Rank: 14Rank: 14
等 级:贵宾
威 望:54
帖 子:1409
专家分:5845
注 册:2016-2-14
收藏
得分:0 
回复 4楼 Redeyes
标红的是有问题的,逻辑问题没看,只看了表面的问题

#include<stdio.h>
int count=0;
int H[4][4];
int pai(int i,int j)
 {
     int s,t;
     for(s=i,t=0;t<0;t++) //判断行 //这里应该是t<4吧?
    if(H[s][t]==1&&t!=j)
     return 0;
     
     for(s=0,t=j;j<0;j++) //判断列  //这里应该是s<4;s++吧?
    if(H[s][t]==1&&s!=i)
     return 0;
     
     for(s=i-1,t=j-1;s>=0,t>=0;s--,t--) //判断左上方 //这里应该是s>=0&&t>=0;吧?
    if(H[s][t]==1)
     return 0;
     
     for(s=i-1,t=j+1;s>=0,j<4;s--,t++) //判断右上方 //这里应该是s>=0&&t<4;吧?
    if(H[s][t]==1)
     return 0;
     
     for(s=i+1,t=j-1;s<4,t>=0;s++,t--) //判断左下方 //同样用&&
    if(H[s][t]==1)
     return 0;
     
     for(s=i+1,t=j+1;s<4,t<4;s++,t++) //判断右下方 //同样用&&
    if(H[s][t]==1)
     return 0;
     
     return 1;  
 }
void huang(int j)
 {
     if(j==4)
         count++;
     for(int i=0;i<4;i++){
         if(pai(i,j)){
             H[i][j]==1; //插入皇后
            huang(j+1); //继续搜索下一个
            H[i][j]==0;
         }
     }
 }
int main()
 {
     int i,j;
     for(i=0;i<4;i++)
         for(j=0;j<4;j++)
             H[i][j]=0;
     huang(0); //还原
    printf("Answer:",count);
     getchar();
}
2016-03-16 09:42
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
收藏
得分:0 
回复 3楼 wmf2014
我也是初学回溯,有许多不懂的地方。 核心算法是这个
图片附件: 游客没有浏览图片的权限,请 登录注册
  满足条件就插入皇后,不满足就还原,继续寻找下一个...这样就实现了回溯

做一名健壮的技术青年,如果未来无法用代码去改变世界,还可以考虑去搬砖。
2016-03-16 09:47
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
收藏
得分:0 
回复 5楼 grmmylbs
好的,谢谢你了!我改后再试试

做一名健壮的技术青年,如果未来无法用代码去改变世界,还可以考虑去搬砖。
2016-03-16 09:48
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回溯算法不是这样吧。
我理解的回溯是:当前无法安放皇后时,移动我上一个已经安放好的皇后,再次安放当前皇后,还无法安放时再次移动我上一个安放好的皇后,直到回溯到第一个已经安放好的皇后,直到第一个皇后都无法安放时说明你已经得到所有的安放方法。

能编个毛线衣吗?
2016-03-16 10:37
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
收藏
得分:0 
回复 8楼 wmf2014
这样理解也可以。不过我觉得回溯就是个循环,不过比较高级了点,带判断的功能。比如走迷宫,四面八方都是出路,这条路不通,就换下一个。其实这个皇后问题我搞了好几天,算法思想框架都能理解,但就是换个类似的题,或者我自己去编写的话,就有许多错误,可能是我练的太少了吧。版主您有什么好的建议吗?

做一名健壮的技术青年,如果未来无法用代码去改变世界,还可以考虑去搬砖。
2016-03-22 02:16
luckhide
Rank: 5Rank: 5
来 自:青岛
等 级:职业侠客
帖 子:51
专家分:338
注 册:2016-3-19
收藏
得分:7 
回溯就是现在领导干部放在嘴边的所谓“倒查机制”,下边出问题了找上边,上边出问题找上上边,把循环理解为回溯显然是不对的。
2016-03-22 08:44
快速回复:凌晨用自己理解的回溯法写的一道关于四皇后的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015668 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved