回溯法案例5/8

1.使用回溯法解决N皇后问题对于n皇后问题,有人认为当n为偶数时,其解具有对称性,即n皇后问题的解个数恰好为n/2皇后问题的解个数的2倍,这个结论正确吗?请编写回溯法程序对n46812的情况进行验证。要求写出算法实现思路采用数据结构具体算法测试实例和运行结果运行抓图。#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); }