雁過無痕

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