一开始将4个数存在数组中，每次从中取出两个数进行 + - * / 运算，并用运算后的结果替换原来的两个数，当数组中只有一个元素时判断这个数是不是24，如果是则输出结果。每次递归搜索后，注意将数组中取出的两个数恢复原位。
代码中， 每次取出res[i]和res[j]后将两数运算结果存入res[i]中，将res[j] = res[n-1]这样递归搜索时只要将数组大小的参数减一即可（dfs(n-1)）。为避免除法带来的精度损失，设置一个很小的浮点用作判断结果是不是接近24
1 //twenty four game
2 #include <iostream>
3 #include <string>
4 #include <math.h>
5 #include <string.h>
6 #include <stdlib.h>
7 #include <stdio.h>
8
9 using namespace std;
10
11 const int N = 4;
12 const double SCORE = 24;
13 double precise = 1E-6;
14 double number[N];
15 string result[N], res;
16
17 bool dfs(int n) {
18 if (n == 1) {
19 if (fabs(number[0] - SCORE) <= precise) {
20 //cout << "debug: " << number[0] << endl;
21 cout << result[0] << endl;
22 return true;
23 } else {
24 return false;
25 }
26 }
27 for (int i = 0; i < n; ++i) {
28 for (int j = i+1; j < n; ++j) {
29 double a = number[i];
30 double b = number[j];
31 string expa = result[i];
32 string expb = result[j];
33
34 number[j] = number[n-1];
35 result[j] = result[n-1];
36
37 number[i] = a + b;
38 result[i] = "(" + expa + "+" + expb + ")";
39 if (dfs(n-1) == true) {
40 return true;
41 }
42
43 number[i] = a * b;
44 result[i] = "(" + expa + "*" + expb + ")";
45 if (dfs(n-1) == true) {
46 return true;
47 }
48
49 number[i] = a - b;
50 result[i] = "(" + expa + "-" + expb + ")";
51 if (dfs(n-1) == true) {
52 return true;
53 }
54
55 number[i] = b - a;
56 result[i] = "(" + expb + "-" + expa + ")";
57 if (dfs(n-1) == true) {
58 return true;
59 }
60
61 if (b != 0) {
62 number[i] = a / b;
63 result[i] = "(" + expa + "/" + expb + ")";
64 if (dfs(n-1) == true) {
65 return true;
66 }
67 }
68
69 if (a != 0) {
70 number[i] = b / a;
71 result[i] = "(" + expb + "/" + expa + ")";
72 if (dfs(n-1) == true) {
73 return true;
74 }
75 }
76
77 number[i] = a;
78 number[j] = b;
79 result[i] = expa;
80 result[j] = expb;
81 }
82 }
83 return false;
84 }
85
86 int main(void)
87 {
88 char buf[5];
89 int m, i;
90
91 cout << "Input m:";
92 cin >> m;
93 while (m--) {
94 for (i = 0; i < N; ++i) {
95 scanf("%s", buf);
96 number[i] = (double)atoi(buf);
97 result[i] = buf;
98 }
99 /*
100 for (i = 0; i < N; ++i) {
101 printf("result i: ");
102 cout << result[i] << endl;
103 }
104 */
105 if (dfs(N) == true) {
106 cout << "Success" << endl;
107 } else {
108 cout << "Failed" << endl;
109 }
110 }
111 return 0;
112 }
posted on 2012-09-12 16:13
lixiucheng 阅读(1331)
评论(0) 编辑 收藏 引用