| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1438 人关注过本帖
标题:八皇后问题
只看楼主 加入收藏
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
我最近的一感触,现在人写代码喜欢人工加密, 所以大家基础要打好 , 哈哈

我就是真命天子,顺我者生,逆我者死!
2010-09-22 18:11
Windy0Winll
Rank: 2
来 自:走了
等 级:等待验证会员
帖 子:71
专家分:90
注 册:2010-8-26
收藏
得分:0 
回复 10楼 BlueGuy
重载等C++概念我还不懂,不过2楼的很多方面我并不赞同。

----现在人写代码喜欢人工加密----
2楼的那段代码没注释,读起来确实是很痛苦的,即使有注释也并不好读懂。如果是我的话,我不知道要怎样给它加注释,感觉加了也是白加,还有可能让别人读代码产生误解。
下面我粗略的来解释下那段代码,很多地方我肯定不能表达得很清楚的,请大家见谅。
2楼的思想核心部分就2个地方:int ok(int k)函数和f函数中的那个while循环。那个ok函数很简单,它的功能只是判断加入第k个数以后是不是符合要求(本题目的要求是:是不是还能满足每行每列还有斜行只有一个皇后。)(如果要用来处理全排列的话只要判断k和前面的数是不是重复了)。下面重点解释一下那个while循环。

// 源代码中的chess[s][x[s]]=1 ,其中的s是表示的棋盘的行,x[s]表示的列
//chess[s][x[s]]=1这一句的意思就是在棋盘的第s行,第x[s]列方一颗棋子(皇后)
// 源代码用循环语句和if语句来找到每一行对应的能满足要求的列,当找到8个符合要求的项目的时候就打印出来
//然后又再重新找下一组能满足要求的数据。

while (k > 0)
    {
      if (k > N)//k如果大于N,那么就执行需要的功能了。这里的k表示当前有k个项目符合要求了。此题目中是只要有8个皇后符合要求,所以当k为9的时候,也就是说已经有8个皇后符合要求了。
    {    v++;
      for (j = 1; j <=N; j++) printf("%d ", x[j]);
      printf("\n");
          for(s=1;s<=N;s++)
          chess[s][x[s]]=1;
          print();
      clrchess();
      printf("\n");
      x[--k]++;//这句以前,k等于N+1;执行以后,k又退回到N,并且让x[N]对应的值加1。本来x[N]是符合要求的,加了1以后,一般情况都是不符合要求的
    }                //下面几个else语句是最重要的地方,要解释清楚太麻烦了,要自己去体会
      else if (x[k] > N) x[--k]++;//如果x[k]超出了范围,则让x[k-1]这个项目的值加1;
      else if (ok(k)) x[++k] = 1;
      else x[k]++;
    }
最后三句不好解释,要自己去理解。
碰到这样的代码,应该一步一步的去想它的执行过程。我当初是从k的初值1开始推起的。当k为1的时候,while循环里面是执行的if的那个分支;然后k变成了2,又是执行的那个分支;这样下去,一直执行if (k > N)这一分支,那时候我想思路应该就清楚了;再接着k又退回到8,然后是7。。。等理解了这整段代码以后,就会发现这里面的技巧非常的巧妙,

[ 本帖最后由 Windy0Winll 于 2010-9-22 19:43 编辑 ]

悄悄地来。。。 然后悄悄地走。。。。。。
2010-09-22 19:21
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
#define SIZE 16
for (j = 0; j < SIZE ; j++) {
{
    if (data[i * ((SIZE >> 1 + 7) >> 3) + (j >> 3)]
        ...
}

谢谢你的耐心解释, 至于这代码有多巧妙,我没那个闲情去体会,ok()、f()这两个函数名就直接让我吐的不行,

"现在人写代码喜欢人工加密", 这话不是针对2楼的, 2楼的代码我至今没认真看过 1 行,他好意思帖,我还不好意思看呢。我管他加密不加密的。

我就是真命天子,顺我者生,逆我者死!
2010-09-23 13:09
vc2gcc
Rank: 1
等 级:新手上路
帖 子:3
专家分:6
注 册:2011-5-28
收藏
得分:0 
我对八皇后问题写了一个专题文章,在

http://clearsky.生成-测试法解决八皇后问题_并与回溯法对比

如果浏览器不支持中文URL,请访问

http://clearsky.

其中大概谈到了八皇后的原理,全排列的生成法,对算法的若干优化。并贴出了效率最高的回溯法。

[ 本帖最后由 vc2gcc 于 2011-5-28 15:43 编辑 ]
2011-05-28 15:41
快速回复:八皇后问题
数据加载中...
 
   



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

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