N个数计算24点
问题:
N个1到13之间的自然数,找出所有能通过加减乘除计算(每个数有且只能用一次)得到24的组合?
计算24点常用的算法有:① 任取两个数,计算后,将结果放回去,再从剩下的数中任取两个,如此反复直到只剩下一个数;② 先构建前缀/后缀表达式,再计算该表达式;③ 用集合保存中间结果,集合间两两进行合并计算得到新集合(或者对给定的一个集合,对其所有的子集合进行合并计算)。
本文采用第一种方法。定义六种操作符:ADD、SUB、MUL、DIV、RSUB、RDIV,分别对应加、减、乘、除、反减和反除(反减/除:先交换两个数,再减/除)。
显然,取两个数计算时,六种计算结果可能有重复,可以对这6个结果进行去重(实际上,只要分别对加减(ADD、SUB、RSUB)和乘除(MUL、DIV、RDIV)的3个计算结果进行去重判断就可以了,效率和对6个结果去重相差不大)。
另外一种剪枝方法:保存每个数上次计算时所用的操作符(初始值为空)。所取的两个数:
若某个数的上次操作符为减(SUB、RSUB),那么不进行加减(ADD、SUB、RSUB)计算。
若某个数的上次操作符为除(DIV、RDIV),那么不进行乘除(MUL、DIV、RDIV)计算。
比如:取的两个数为 a-b 和 c(c的上次操作符任意),如果进行加减计算的话,
a-b+c 和 c+a-b重复,
c-(a-b)和 c+b-a重复
a-b-c 和 c+b RSUB a重复
也就是说,上次操作符为减的,进行加减计算时,总可以转为某个上次操作符为加的表达式,因而可以不计算。同样,上次操作符为除的,不进行乘除计算。
当然,还可以考虑记录位置进行剪枝,这样避免a+b+c和a+c+b都进行计算。但要注意的是:在给定的组合无解时,越多的剪枝方法,极有可能提高搜索效率,但在给定的组合有解时,很可能反而降低搜索效率。
另外,对有解时输出的表达式的处理对程序的性能影响很大。如果每次计算都保存对应的表达式,会进行大量的字符串操作,严重影响性能。实际上,每次计算只要保存取出的两个数的位置和所进行计算的操作符就够了,最终需要输出表达式时,只要模拟一下递归函数调用过程,进行相应的字符串操作。
下面是程序(gcc 4.5,优化参数-O2)在T4200/2G单核下运行的结果,计算10个数,646646个组合只用了不到13分钟。
N个1到13之间的数的所有组合,计算24点
N
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
时间(ms)
|
78
|
610
|
4157
|
19593
|
160922
|
173766
|
764328
|
有解组合数
|
1362
|
6104
|
18554
|
50386
|
125969
|
293930
|
646646
|
总组合
|
1820
|
6188
|
18564
|
50388
|
125970
|
293930
|
646646
|
总表达式
|
1124776
|
15656645
|
105278906
|
492587616
|
3760744504
|
4535030813
|
19912345238
|
表达式A
|
457549
|
11864184
|
88679768
|
409129896
|
1173803224
|
4535030813
|
19912345238
|
表达式B
|
667227
|
3792461
|
16599138
|
83457720
|
2586941280
|
0
|
0
|
总函数调用
|
1482939
|
20950792
|
141892513
|
669790534
|
5258218577
|
6112529945
|
26948662625
|
函数调用A
|
603206
|
15849306
|
119160441
|
551913059
|
1576965280
|
6112529945
|
26948662625
|
函数调用B
|
879733
|
5101486
|
22732072
|
117877475
|
3681253297
|
0
|
0
|
其中:表达式A/B、函数调用A/B为:给定的n个数有/无解时,所处理的表达式总数和函数调用总次数。
N=8与N=9,两个所用时间只相差13秒,这是由于N为8时,有一个组合(8个1)无解,判断这个组合无解需110多秒,而计算剩下的125969个组合还不要50秒。
程序代码:
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
24.cpp
1
//24.cpp by flyinghearts#qq.com
2
#include<iostream>
3
#include<fstream>
4
#include<sstream>
5
#include<vector>
6
#include<ctime>
7
#include<cmath>
8
using std::cout;
9
using std::string;
10
using std::vector;
11
using std::ofstream;
12
using std::stringstream;
13![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class Calc
{
15
public:
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Calc()
{};
17
void print_result() const;
18
bool run(const int src[], size_t sz, double n = 24.0,
19
bool expr_calc = true, bool show = true);
20
void calc_range(int first, int last,size_t N = 4,
21
double M = 24, string filename = "24.out");
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
const string& get_expr() const
{ return expr;}
23![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
size_t get_count_expr() const
{ return count_expr;}
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
size_t get_count_func() const
{ return count_func;}
25
26
private:
27
Calc(const Calc&);
28
Calc& operator=(const Calc&);
29
bool init(const int src[], size_t sz, double n);
30
bool calc(size_t step);
31
inline bool calc2(size_t step, size_t pos2,double na, double nb, int op);
32
void calc_expr();
33
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void add_parentheses(string& str)
{
35
string tmp; tmp.reserve(str.size() + 2);
36
tmp += '('; tmp += str; tmp += ')';
37
str.swap(tmp);
38
}
39
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
char get_op_char(int op)
{ return char(op >> RSHIFT); }
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int get_opv(int op)
{ return op & OPV_MASK; }
42
43
//0-2位表示操作符的优先级 加减: 1 乘除2 初始值4
44
//+3位,即RFLAG标志,表示对减除法,交换两个操作数后再计算
45
//4-7位表示操作符,8-15位表示该操作符的ascii值
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
enum
{
47
OP_NULL = 4, RFLAG = 8, RSHIFT = 8, OPV_MASK = 7,
48
FLAG_ADD = 0x10, FLAG_SUB = 0x20, FLAG_MUL = 0x40, FLAG_DIV = 0x80,
49
ADD = '+' << RSHIFT | FLAG_ADD | 1, SUB = '-' << RSHIFT | FLAG_SUB | 1,
50
MUL = '*' << RSHIFT | FLAG_MUL | 2, DIV = '/' << RSHIFT | FLAG_DIV | 2,
51
RSUB = SUB | RFLAG, RDIV = DIV | RFLAG,
52
};
53![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
54![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
struct Info_step
{ //记录每一步取两个数所进行的计算
55
size_t first; //第一个操作数位置
56
size_t second; //第二个操作数位置
57
int op; //操作符
58
};
59
60
size_t size;
61
string expr; //得到的表达式
62
double result; //要得到的结果值
63
size_t count_expr; //处理的表达式总数
64
size_t count_func; //函数被调用次数
65
vector<int> old_number; //要计算的数
66
vector<double> number; //中间计算结果
67
vector<int> ops; //上一次计算所用的操作符,初始值要设为OP_NULL
68
vector<Info_step> info_step;
69
};
70![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
71
bool Calc::init(const int src[], size_t sz, double n)
72![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
73
if (sz == 0 || src == NULL) return false;
74
size = sz;
75
expr.clear();
76
result = n;
77
count_expr = 0;
78
count_func = 0;
79
old_number.assign(src, src + sz);
80
number.assign(src, src+sz);
81
ops.assign(sz, OP_NULL);
82
info_step.clear();
83
info_step.resize(sz);
84
return true;
85
}
86![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
87
bool Calc::run(const int src[], size_t sz, double n, bool expr_calc, bool show)
88![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
89
if (! init(src, sz, n)) return false;
90
bool ret = calc(sz);
91
if (ret && expr_calc) calc_expr();
92
if (show) print_result();
93
return ret;
94
}
95![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
96![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
97
void Calc::calc_expr()
98![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
99
const size_t sz = size;
100
static vector<string> str;
101
static vector<int> op_prev;
102
static stringstream ss;
103
str.resize(sz);
104
op_prev.assign(sz,OP_NULL); //初始值
105![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (size_t i = 0; i < sz; ++i)
{
106
ss << old_number[i];
107
getline(ss, str[i]);
108
ss.clear();
109
}
110![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (size_t k = sz; k-- > 1; )
{
111
size_t i = info_step[k].first;
112
size_t j = info_step[k].second;
113
int op = info_step[k].op;
114
int opv= get_opv(op);
115
int op1v, op2v;
116![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (op & RFLAG)
{
117
str[i].swap(str[j]);
118
op1v = get_opv(op_prev[j]);
119
op2v = get_opv(op_prev[i]);
120![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
121
op1v = get_opv(op_prev[i]);
122
op2v = get_opv(op_prev[j]);
123
}
124
125
if (opv > op1v) add_parentheses(str[i]);
126
if (opv > op2v || (opv == op2v && (op & (FLAG_SUB | FLAG_DIV))))
127
add_parentheses(str[j]);
128
op_prev[i] = op;
129
op_prev[j] = op_prev[k];
130
str[i].reserve(str[i].size() + str[j].size() + 1);
131
str[i] += get_op_char(op);
132
str[i] += str[j];
133
str[j].swap(str[k]);
134
}
135
expr.swap(str[0]);
136
}
137![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
138
bool Calc::calc(size_t step)
139![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
140
++count_func;
141![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (step <= 1)
{
142
++count_expr;
143
const double zero = 1e-9;
144
if (fabs(result - number[0]) < zero) return true;
145
return false;
146
}
147
--step;
148![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (size_t i = 0; i < step; i++)
{
149
info_step[step].first = i;
150![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(size_t j = i + 1; j <= step; j++)
{
151
info_step[step].second = j;
152
double na = number[i];
153
double nb = number[j];
154
int op1 = ops[i];
155
int op2 = ops[j];
156
number[j] = number[step];
157
ops[j] = ops[step];
158
int tt = op1 | op2;
159
bool ba = true, bb = true;
160
if (tt & FLAG_SUB) ba = false;
161
if (tt & FLAG_DIV) bb = false;
162
163![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (ba)
{
164
if (calc2(step, i, na, nb, ADD)) return true;
165
if (nb != 0 && calc2(step, i, na, nb, SUB)) return true;
166
if (na != nb && na != 0 && calc2(step, i, na, nb, RSUB)) return true;
167
}
168
169![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (bb)
{
170
double nmul = na * nb;
171
if (calc2(step, i, na, nb, MUL)) return true;
172![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (na != 0 && nb !=0)
{
173
double ndiv = na / nb;
174
if (nmul != ndiv && calc2(step,i,na, nb, DIV)) return true;
175
double nrdiv = nb / na;
176
if (nrdiv != ndiv && nrdiv != nmul && calc2(step,i,na, nb, RDIV))
177
return true;
178
}
179
}
180
number[i] = na;
181
number[j] = nb;
182
ops[i] = op1;
183
ops[j] = op2;
184
}
185
}
186
return false;
187
}
188![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
189
inline bool Calc::calc2(size_t step, size_t pos2,double na,double nb, int op)
190![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
191
info_step[step].op = op;
192
ops[pos2] = op;
193![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
switch (op)
{
194
case ADD: number[pos2] = na + nb; break;
195
case SUB: number[pos2] = na - nb; break;
196
case MUL: number[pos2] = na * nb; break;
197
case DIV: number[pos2] = na / nb; break;
198
case RSUB: number[pos2] = nb - na; break;
199
case RDIV: number[pos2] = nb / na; break;
200
default : break;
201
}
202
return calc(step);
203
}
204![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
205
void Calc::print_result() const
206![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
207
if (old_number.empty()) return;
208
cout << "number: ";
209
for (size_t i = 0; i < old_number.size(); ++i)
210
cout << old_number[i] << " ";
211
cout << "\n";
212
if (! expr.empty()) std::cout << "result: " << expr << "=" << result << "\n";
213
cout << "expr/func: " << count_expr << "/" << count_func << "\n\n";
214
}
215![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
216![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
217
void Calc::calc_range(int first, int last,size_t N, double M, string filename)
218![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
219
if (N ==0 || first >= last || filename.empty()) return;
220
clock_t ta = clock();
221
vector<int> vv(N, first);
222
int *end = &vv[N-1], *p = end, *arr = &vv[0];
223
ofstream ofs(filename.c_str());
224
size_t count = 0;
225
size_t count_b = 0;
226
typedef unsigned long long size_tt;
227
size_tt count_expr_a = 0;
228
size_tt count_expr_b = 0;
229
size_tt count_func_a = 0;
230
size_tt count_func_b = 0;
231![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(true)
{
232
++count_b;
233![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (run(arr,N,M,true,false))
{
234
ofs.width(4);
235
ofs<< ++count << " ";
236![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (size_t i = 0; i < N; ++i)
{
237
ofs.width(2);
238
ofs << arr[i]<< " ";
239
}
240
ofs<< " " << get_expr() << "\n";
241
count_expr_a += count_expr;
242
count_func_a += count_func;
243![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
} else
{
244
count_expr_b += count_expr;
245
count_func_b += count_func;
246
}
247
while (p >= arr && *p >= last) --p;
248
if (p < arr) break;
249
int tmp = ++*p;
250
while (p < end) *++p = tmp;
251
}
252
ofs.close();
253
const char sep[] = "/";
254
cout << "N: " << N << " M: " << M
255
<< " range: " << first << "-" << last << "\n"
256
<< "expr: " << count_expr_a + count_expr_b << sep << count_expr_a
257
<< sep << count_expr_b << "\n"
258
<< "func: " << count_func_a + count_func_b << sep << count_func_a
259
<< sep << count_func_b << "\n"
260
<< "total: " << count << sep << count_b << "\n"
261
<< "time: " << clock() - ta << " ms\n\n" << std::flush;
262
}
263![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
264![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
265
int main()
266![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
267
Calc calc;
268![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int ra[4]=
{3,3,8,8};
269![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int rb[4]=
{5,7,7,11};
270![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int rc[4]=
{4,7,11,13};
271
calc.run(ra,4);
272
calc.run(rb,4);
273
calc.run(rc,4);
274
//calc.calc_range(1,13,4,24,"nul");
275
//calc.calc_range(1,50,4,24,"nul");
276
//calc.calc_range(1,100,4,24,"nul");
277
calc.calc_range(1,13, 4,24,"a24-04t.txt");
278
calc.calc_range(1,13, 5,24,"a24-05t.txt");
279
calc.calc_range(1,13, 6,24,"a24-06t.txt");
280
calc.calc_range(1,13, 7,24,"a24-07t.txt");
281
calc.calc_range(1,13, 8,24,"a24-08t.txt");
282
calc.calc_range(1,13, 9,24,"a24-09t.txt");
283
calc.calc_range(1,13,10,24,"a24-10t.txt");
284
}
285![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)