雁過無痕

N個(gè)數(shù)計(jì)算24點(diǎn)

問題：

    N個(gè)1到13之間的自然數(shù)，找出所有能通過加減乘除計(jì)算（每個(gè)數(shù)有且只能用一次）得到24的組合？

計(jì)算24點(diǎn)常用的算法有：① 任取兩個(gè)數(shù)，計(jì)算后，將結(jié)果放回去，再從剩下的數(shù)中任取兩個(gè)，如此反復(fù)直到只剩下一個(gè)數(shù)；② 先構(gòu)建前綴/后綴表達(dá)式，再計(jì)算該表達(dá)式；③ 用集合保存中間結(jié)果，集合間兩兩進(jìn)行合并計(jì)算得到新集合（或者對給定的一個(gè)集合，對其所有的子集合進(jìn)行合并計(jì)算）。

本文采用第一種方法。定義六種操作符：ADD、SUB、MUL、DIV、RSUB、RDIV，分別對應(yīng)加、減、乘、除、反減和反除（反減/除：先交換兩個(gè)數(shù)，再減/除）。

顯然，取兩個(gè)數(shù)計(jì)算時(shí)，六種計(jì)算結(jié)果可能有重復(fù)，可以對這6個(gè)結(jié)果進(jìn)行去重（實(shí)際上，只要分別對加減（ADD、SUB、RSUB）和乘除（MUL、DIV、RDIV）的3個(gè)計(jì)算結(jié)果進(jìn)行去重判斷就可以了，效率和對6個(gè)結(jié)果去重相差不大）。

另外一種剪枝方法：保存每個(gè)數(shù)上次計(jì)算時(shí)所用的操作符（初始值為空）。所取的兩個(gè)數(shù)：

若某個(gè)數(shù)的上次操作符為減(SUB、RSUB)，那么不進(jìn)行加減（ADD、SUB、RSUB）計(jì)算。

若某個(gè)數(shù)的上次操作符為除(DIV、RDIV)，那么不進(jìn)行乘除（MUL、DIV、RDIV）計(jì)算。

比如：取的兩個(gè)數(shù)為 a-b 和 c(c的上次操作符任意)，如果進(jìn)行加減計(jì)算的話，

a-b+c  和 c+a-b重復(fù)，

c-(a-b)和 c+b-a重復(fù)

a-b-c  和 c+b RSUB a重復(fù)

也就是說，上次操作符為減的，進(jìn)行加減計(jì)算時(shí)，總可以轉(zhuǎn)為某個(gè)上次操作符為加的表達(dá)式，因而可以不計(jì)算。同樣，上次操作符為除的，不進(jìn)行乘除計(jì)算。

當(dāng)然，還可以考慮記錄位置進(jìn)行剪枝，這樣避免a+b+c和a+c+b都進(jìn)行計(jì)算。但要注意的是：在給定的組合無解時(shí)，越多的剪枝方法，極有可能提高搜索效率，但在給定的組合有解時(shí)，很可能反而降低搜索效率。

另外，對有解時(shí)輸出的表達(dá)式的處理對程序的性能影響很大。如果每次計(jì)算都保存對應(yīng)的表達(dá)式，會進(jìn)行大量的字符串操作，嚴(yán)重影響性能。實(shí)際上，每次計(jì)算只要保存取出的兩個(gè)數(shù)的位置和所進(jìn)行計(jì)算的操作符就夠了，最終需要輸出表達(dá)式時(shí)，只要模擬一下遞歸函數(shù)調(diào)用過程，進(jìn)行相應(yīng)的字符串操作。

下面是程序（gcc 4.5，優(yōu)化參數(shù)-O2）在T4200/2G單核下運(yùn)行的結(jié)果，計(jì)算10個(gè)數(shù)，646646個(gè)組合只用了不到13分鐘。

 N個(gè)1到13之間的數(shù)的所有組合，計(jì)算24點(diǎn)

其中：表達(dá)式A/B、函數(shù)調(diào)用A/B為：給定的n個(gè)數(shù)有/無解時(shí)，所處理的表達(dá)式總數(shù)和函數(shù)調(diào)用總次數(shù)。

    N=8與N=9，兩個(gè)所用時(shí)間只相差13秒，這是由于N為8時(shí)，有一個(gè)組合（8個(gè)1）無解，判斷這個(gè)組合無解需110多秒，而計(jì)算剩下的125969個(gè)組合還不要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位表示操作符的優(yōu)先級 加減: 1 乘除2  初始值4
 44  //+3位，即RFLAG標(biāo)志，表示對減除法，交換兩個(gè)操作數(shù)后再計(jì)算
 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 {              //記錄每一步取兩個(gè)數(shù)所進(jìn)行的計(jì)算
 55    size_t first;                 //第一個(gè)操作數(shù)位置 
 56    size_t second;                //第二個(gè)操作數(shù)位置
 57    int op;                       //操作符
 58  };
 59  
 60  size_t size;                    
 61  string expr;                    //得到的表達(dá)式 
 62  double result;                  //要得到的結(jié)果值
 63  size_t count_expr;              //處理的表達(dá)式總數(shù)     
 64  size_t count_func;              //函數(shù)被調(diào)用次數(shù)
 65  vector<int> old_number;         //要計(jì)算的數(shù)
 66  vector<double> number;          //中間計(jì)算結(jié)果           
 67  vector<int> ops;               //上一次計(jì)算所用的操作符,初始值要設(shè)為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