雁过无痕

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点

其中：表达式A/B、函数调用A/B为：给定的n个数有/无解时，所处理的表达式总数和函数调用总次数。

    N=8与N=9，两个所用时间只相差13秒，这是由于N为8时，有一个组合（8个1）无解，判断这个组合无解需110多秒，而计算剩下的125969个组合还不要50秒。


程序代码：

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>
  8using std::cout;
  9using std::string;
 10using std::vector;
 11using std::ofstream;
 12using std::stringstream;
 13
 14class Calc {
 15 public:
 16  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  const string& get_expr() const { return expr;}
 23  size_t get_count_expr() const { return count_expr;}
 24  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  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  char get_op_char(int op) { return char(op >> RSHIFT); }
 41  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  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
 54  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
 71bool Calc::init(const int src[], size_t sz, double n)
 72{
 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
 87bool Calc::run(const int src[], size_t sz, double n, bool expr_calc, bool show)
 88{
 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
 96
 97void Calc::calc_expr()
 98{
 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  for (size_t i = 0; i < sz; ++i) {
106    ss << old_number[i];
107    getline(ss, str[i]);
108    ss.clear();
109  }
110  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    if (op & RFLAG) { 
117      str[i].swap(str[j]);
118      op1v = get_opv(op_prev[j]);
119      op2v = get_opv(op_prev[i]);
120    } 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
138bool Calc::calc(size_t step)
139{
140  ++count_func;
141  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  for (size_t i = 0; i < step; i++){
149    info_step[step].first = i;
150    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      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      if (bb) {
170        double nmul = na * nb;
171        if (calc2(step, i, na, nb, MUL)) return true;
172        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
189inline bool Calc::calc2(size_t step, size_t pos2,double na,double nb, int op)
190{
191  info_step[step].op = op;
192  ops[pos2] = op;
193  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
205void Calc::print_result() const
206{
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
216
217void Calc::calc_range(int first, int last,size_t N, double M, string filename)
218{
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  while(true){
232    ++count_b;
233    if (run(arr,N,M,true,false)) {
234      ofs.width(4);
235      ofs<<  ++count << "    ";
236      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    } 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
264
265int main()
266{
267  Calc calc;
268  int ra[4]={3,3,8,8};
269  int rb[4]={5,7,7,11};
270  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