算法竞赛入门经典第7章
1 生成遍历法:先产生所有的可能,然后根据限制条件过滤结果
#define RUN #ifdef RUN #include<stdio.h> //C[x]=y 表示x行的皇后处于y列 int C[50], tot = 0, n = 8, nc = 0; void search(int cur) { int i, j; nc++; //检查每个可能,看是否会冲突 if(cur == n) { for(i = 0; i < n; i++) for(j = i+1; j < n; j++) if(C[i] == C[j] || i-C[i] == j-C[j] || i+C[i] == j+C[j]) return; //找到一个没冲突的可能 tot++; } //遍历生成所有的可能 else for(i = 0; i < n; i++) { C[cur] = i; search(cur+1); } } int main() { search(0); printf("%d\n", tot); printf("%d\n", nc); return 0; } #endif
2 回溯法
//#define RUN #ifdef RUN #include<stdio.h> //C[x]=y 表示x行的皇后处于y列 int C[50], tot = 0, n = 8, nc = 0; void search(int cur) { int i, j; nc++; //递归边界,只要走到这里,所有的皇后必然不冲突 if(cur == n) { tot++; } else { //对于当前第cur行,逐个测试i从0到n-1,看适合放在哪一列 for(i = 0; i < n; i++) { int ok = 1; //假设放在第i列 C[cur] = i; //测试在前面的行的皇后是否会和当前位置冲突 for(j = 0; j < cur; j++){ //列冲突,主对角线冲突,副对角线冲突 if(C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j]) { ok = 0; break; } } //进行下一行的搜索 if(ok) search(cur+1); } } } int main() { search(0); printf("%d\n", tot); printf("%d\n", nc); return 0; } #endif
3 有全局变量的回溯法(最常用)
//#define RUN #ifdef RUN #include<stdio.h> #include <string.h> //C[x]=y 表示x行的皇后处于y列 int C[50], vis[3][50], tot = 0, n = 8, nc = 0; void search(int cur) { int i, j; nc++; if(cur == n) { tot++; } else{ //测试每一列 for(i = 0; i < n; i++) { //检测列冲突,副对角线,正对角线冲突 if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]) { C[cur] = i; vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1; search(cur+1); vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0; } } } } int main() { memset(vis, 0, sizeof(vis)); search(0); printf("%d\n", tot); printf("%d\n", nc); return 0; } #endif
注意:如果在回溯法中使用了辅助的全局变量,则一定要及时把它们恢复原状。例如,若函数有多个出口,则需在每个出口处恢复被修改的值。
相关推荐
0 资源分 八皇后 的三种解法 (java编写)
八皇后问题详细的解法-23页 PPT PDF版.pdf
8皇后问题的两种解法,C语言描述,有详细的注释和声明,通俗易懂
八皇后问题的两种解法,包含c方式和c++方式
比较经典的8皇后问题 与大家共享比较经典的8皇后问题 与大家共享比较经典的8皇后问题 与大家共享
这个是八皇后问题的一种解法,希望可以给大家参考,有需要的话可以看一下哦!
八皇后问题的java解法.rar
算法设计中的皇后摆放问题,用C写的八皇后和N皇后的解法。
解决n皇后的代码 #include #include #include #define _PRINT_ 0//没有输出具体的解,只是计算了总数。 #define MAXQ 100 long N, t; long qx[MAXQ], qy[MAXQ]; long quse; /* */ bool chk(int x, int y) //...
八皇后问题详细的解法.ppt
n皇后问题正确解法.txt
收集的用scheme语言编写的八皇后的解法,对学习scheme语言想理解递归的同志们是一个好例子,sicp中也有此练习题。
八皇后问题,回溯算法,92种解法均有,且结果真观易懂
八皇后问题详细的解法PPT学习教案.pptx
八皇后问题c++解法
八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题...
八皇后问题 c源代码 回溯法 通过更改N的值可以演变成为N皇后 不过当N大于一定的数值时 电脑会花费比较长的时间哦
八皇后解法.
8皇后的两种解法,一种是递归,一种是迭代,并且求出了所有的解,并存放在word中。
八皇后问题解法.zip