回溯法案例5/8

1.使用回溯法解决N皇后问题

对于n皇后问题,有人认为当n为偶数时,其解具有对称性,即n皇后问题的解个数恰好为n/2皇后问题的解个数的2倍,这个结论正确吗?请编写回溯法程序对n=4，6，8，12的情况进行验证。

要求：写出算法实现思路，采用数据结构，具体算法，测试实例和运行结果，运行抓图。

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #define MAXN 20 int q[MAXN]; int count = 0; bool place(int i) { if (i == 1) return true; else { int j = 1; for (j; j < i; j++) if (q[j] == q[i] || (abs(i - j) == abs(q[i] - q[j]))) return false; } return true; } void dispasolution(int n) { printf("第%d个解为：",++count); for (int j = 1; j <= n; j++) printf("(%d,%d) ", j, q[j]); printf("\n"); } void quenes(int n) { int i = 1; q[i] = 0; while (i >= 1) { q[i]++; while(q[i]<=n&&!place(i)) { q[i]++; } if (q[i] <= n) { if (i == n) dispasolution(n); else { i++; q[i] = 0; } } else i--; } } int main() { int n = 0; scanf("%d", &n); quenes(n); }

2移动路径问题

一个机器人只能向下和向右移动，每次只能移动一步，设计一个算法求它从（0,0)移动到（m-1,n-1)有多少条路径。

要求：写出算法实现思路，采用数据结构，具体算法，测试实例和运行结果，运行抓图。

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #define MAXN 20 int q[MAXN]; int count = 0; void move(int i, int j,int m,int n) { if (i == m && j == n) { count++; } else { if (i < m) { move(i + 1, j, m, n); } if (j < n) { move(i, j + 1, m, n); } } } int main() { int m, n; scanf("%d %d", &m, &n); move(0, 0, m-1, n-1); printf("共有%d种路径", count); }