问题2：通过求解n-皇后问题，体会回溯法深度优先遍历状态空间树，并利用约束函数进行剪枝的算法思想。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> using namespace std; int cnt = 0; bool Place(int k, int i, int *x) { for(int j = 0; j < k; j++) if((x[j] == i) || (abs(x[j] - i) == abs(j - k))) return false; return true; } void NQueens(int k, int n, int *x) { for(int i = 0; i < n; i++) { if(Place(k, i, x)) { x[k] = i; if(k == n - 1) { for(i = 0; i < n; i++) cout << x[i] << " "; cout << endl; cnt ++; } else { NQueens(k + 1, n, x); } } } } void NQueens(int n, int *x) { NQueens(0, n, x); } int main() { int x[8]; cnt = 0; for(int i = 0; i < 8; i++) x[i] = -1; NQueens(8, x); printf("Answers num: %d\n", cnt); return 0; }
本次实验的思考题太烦，就写了一个。将求解24点的表达式拆分：
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #include <stack> #include <string> #include <cmath> using namespace std; double EPS = 1e-10; double num[4]; bool flag; int cnt; string re[4]; string ans; bool equel(double a, double b) { if(fabs(a - b) <= EPS) return true; return false; } void DFS(int n) { //if(flag) // return; if(n == 1 && equel(num[0], 24)) { cnt ++; cout << re[0] << endl; //ans = re[0]; ///flag = true; return; } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { double c1 = num[i], c2 = num[j]; string re1, re2; num[j] = num[n - 1]; num[i] = c1 + c2; re1 = re[i]; re2 = re[j]; re[j] = re[n - 1]; re[i] = \'(\' + re1 + \'+\' + re2 + \')\'; DFS(n - 1); num[i] = c1 - c2; re[i] = \'(\' + re1 + \'-\' + re2 + \')\'; DFS(n - 1); num[i] = c2 - c1; re[i] = \'(\' + re2 + \'-\' + re1 + \')\'; DFS(n - 1); num[i] = c1 * c2; re[i] = \'(\' + re1 + \'*\' + re2 + \')\'; DFS(n - 1); if(!equel(c2, 0)) //judge { num[i] = c1 / c2; re[i] = \'(\' + re1 + \'/\' + re2 + \')\'; DFS(n - 1); } if(!equel(c1, 0)) { num[i] = c2 / c1; re[i] = \'(\' + re2 + \'/\' + re1 + \')\'; DFS(n - 1); } num[i] = c1; num[j] = c2; re[i] = re1; re[j] = re2; } } } int main() { //consider the rational numbers, we define them as double flag = false; scanf("%lf %lf %lf %lf", &num[0], &num[1], &num[2], &num[3]); re[0] = num[0] + \'0\'; re[1] = num[1] + \'0\'; re[2] = num[2] + \'0\'; re[3] = num[3] + \'0\'; cnt = 0; DFS(4); if(cnt == 0) printf("Fail!\n"); else { string o[10]; stack <char> stk; int cnt1 = 0; int len = ans.length(); cout << ans << endl; for(int i = 0; i < len; i++) { if((ans[i] != \')\')) stk.push(ans[i]); else { char tmp[100]; int cnt2 = 0; char ch1, ch2; char tp; while(stk.top() != \'(\') { tmp[cnt2 ++] = stk.top(); stk.pop(); } stk.pop(); double num3; double num2 = 0; double num1 = 0; int le1 = 0; int le2 = 0; bool f = false; bool f1 = false; bool f2 = false; for(int i = cnt2 - 1; i >= 0; i--) { o[cnt1] += tmp[i]; if(!f && tmp[i] != \'+\' && tmp[i] != \'-\' && tmp[i] != \'*\' && tmp[i] != \'/\') { if(f1) le1 ++; if(tmp[i] == \'.\') { f1 = true; continue; } num1 = num1 * 10 + tmp[i] - \'0\'; } else if(tmp[i] == \'+\' || tmp[i] == \'-\' || tmp[i] == \'*\' || tmp[i] == \'/\') { tp = tmp[i]; f = true; } else if(f) { if(f2) le2 ++; if(tmp[i] == \'.\') { f2 = true; continue; } num2 = num2 * 10 + tmp[i] - \'0\'; } } num1 /= pow(10.0, le1); num2 /= pow(10.0, le2); // printf("num1 = %lf\n", num1); // printf("num2 = %lf\n", num2); if(tp == \'+\') { num3 = num1 + num2; char t4[10]; sprintf(t4, "%.6f", num3); int le = strlen(t4); for(int i = 0; i < le; i++) stk.push(t4[i]); } else if(tp == \'-\') { num3 = num1 - num2; char t4[10]; sprintf(t4, "%.6f", num3); int le = strlen(t4); for(int i = 0; i < le; i++) stk.push(t4[i]); } else if(tp == \'*\') { num3 = num1 * num2; char t4[10]; sprintf(t4, "%.6f", num3); int le = strlen(t4); for(int i = 0; i < le; i++) stk.push(t4[i]); } else if(tp == \'/\') { num3 = num1 / num2; char t4[10]; sprintf(t4, "%.6f", num3); int le = strlen(t4); for(int i = 0; i < le; i++) stk.push(t4[i]); } o[cnt1] += \'=\'; char t4[10]; sprintf(t4, "%.6f", num3); o[cnt1] += t4; cnt1 ++; } } for(int i = 0; i < cnt1; i++) cout << o[i] << endl;4 } }
回溯法实例：Sticks
Description