《編程之美》讀書筆記22：    1.16  24點游戲

給定4個數，能否只通過加減乘除計算得到24？由于只有4個數，弄個多重循環，就可以。如果要推廣到n個數，有兩種思路：

① 采用前綴/后綴表達式。相當于將n個數用n-1個括號括起來，其數目就是一個catlan數。最多可得到 f(n) = (1/n * (2*n - 2)! / (n-1)! / (n-1)!) * n! * 4^(n-1) = 4^(n-1) * (2*n-2)! / (n-1)! 種表達式，當n=4時，共可得到 7680種。

② 從n個數中任意抽取2個，進行計算最多有6種結果，將計算結果放回去，再從剩下的n-1個任取2個，進行計算，如此反復，直到只剩下1個數。按這種算法，共要處理表達式：g(n)=(n*(n-1)/2*6) * ((n-1)*(n-2)/2*6) * ((n-2)*(n-3)/2*6) * (2*1/2*6) = n!*(n-1)!*3^(n-1)當n=4時，最多要處理3888種。 (書上的代碼將這兩種思路混在一塊了。)

f(n) / g(n) = (4/3)^(n-1) * (2*n-2)! / n! / (n-1)! / (n-1)!

很明顯，當n比較大時（比如n大于8），會有 f(n) < g(n)。比如：f(10)/g(10)=0.178。

從f(n)與g(n)的比值，可以看出，這兩種解法都存在大量的不必要計算。當n比較大時，思路2的冗余計算已經嚴重影響了性能。要如何減少這些不必要計算呢？

可以記錄得到某個計算結果時所進行操作。比如: a、b、c和d這4個數取前2個，進行加法計算得到 a+b，則記錄‘+’。另外，假設加減號的優先級為0，乘除號的優先級為1。

a和b進行減/除計算時，實際上得到 a-b與b-a，a/b與b/a。

當取出2個數a和b，進行計算，這兩個數上次的操作符有下面這幾種情況：

① 都為空：

要計算6個結果，即 a+b, a-b, b-a, a*b, a/b, b/a。

② 只有一個為空：假設： a = a1 op1 a2

   ⑴　一種剪枝方法是： 若op1為減（除）號，則不進行加減（乘除）計算。

       因為： (a-b)-c可以轉為a-(b+c)，這兩個表達式只要計算一個就可以。

⑵　另一種剪枝方法：額外記錄每次計算最靠后的那個數的位置。比如位置順序：a、b、c、d，進行a+c計算時，記錄了c位置，再與數b計算時，由于b位置在c位置前，不允許計算 (a+c) + b 和 (a+c) – b這樣就避免了表達式 a+b+c和 a-b+c被重復計算。

③ 都不為空： 假設： a = a1 op1 a2， b= b1 op2 b2

   要計算的結果： a op3 b = （a1 op1 a2）op3 (b1 op2 b2)

   ⑴　如果 op1 和 op2的優先級相同，那么 op3 的優先級不能與它們相同，若相同，則原來的表達式可以轉為 ((a1 op4 a2) op5 b1) op6 b2，因而沒必要對原來的表達式進行計算。比如 (m1+m2)與(m3-m4)之間只進行乘除計算，而不進行加減計算。

⑵　如果 op1 和 op2的優先級不同，那么 op3 無論怎么取，其優先級都必會與其中一個相同，則原表達式可以轉化((c1 op4 c2) op5 c3) op6 c4這種形式，因而該表達式沒必要計算。如(m1+m2)與(m3*m4)，不進行任何計算。

總之：op1 與 op2優先級不同時，不進行計算。

         op1 與 op2優先級相同時，進行計算的操作符優先級不與它們相同。

要注意的是：剪枝不一定提高性能（在筆記1.3 一摞烙餅的排序 中已經說明了這個問題）。如果n個數計算可得到24，過多的避免冗余計算，有可能嚴重降低性能。計算n=6時，碰到一個組合，僅使用了③的剪枝方法，得到結果時處理了四百個表達式，但再采用了②的第一種剪枝方法，處理的表達式達到五十三萬多。（也許②的第二種剪枝方法不存在這么嚴重的問題。）與烙餅排序不同的是，烙餅排序總能找到一個結果，而n個數計算有可能無解。顯然在無解時，采用盡可能多的剪枝方法，必然會極大的提高性能。

另外，對于輸出表達式，書上的程序進行了大量的字符串操作，實際上可以只記錄，每一步取出的兩個數的位置（即記錄i、j值），在需要輸出時，再根據所記錄的位置，進行相應的字符串操作就可以了。

書上的解法二實現
 1#include <iostream>
 2#include <string>
 3#include <set>
 4#include <cmath>
 5using namespace std;
 6
 7bool calc(int src[], size_t N, double M = 24.0)
 8{
 9  if (N == 0 || src == NULL) return false;
10  set<double> result[1 << N];
11  for (size_t i = 0; i < N; ++i) result[1<<i].insert((double)src[i]); 
12  
13  for (size_t i =1; i < (1<<N); ++i) {
14    for (size_t j = 1; j <= (i >> 1); ++j) {
15       if ((i & j) != j) continue;
16       for (set<double>::iterator p = result[j].begin(); p != result[j].end(); ++p) {
17         double va = *p;
18         size_t k = i ^ j;
19         for (set<double>::iterator q = result[k].begin(); q != result[k].end(); ++q) {
20           double vb = *q;
21           result[i].insert(va + vb);
22           result[i].insert(va - vb);
23           result[i].insert(vb - va);
24           result[i].insert(va * vb);
25           if (vb != 0.0) result[i].insert(va / vb);
26           if (va != 0.0) result[i].insert(vb / va);
27         }
28       }
29    } 
30  }
31  
32  size_t j = (1 << N) - 1;
33  const double zero = 1e-9;
34  for (set<double>::iterator p = result[j].begin(); p != result[j].end(); ++p) {
35    if (fabs(*p - M) < zero) return true;
36  }
37  return false;
38}
39
40int main()
41{
42  //int src[]={13, 773, 28, 98, 731, 1357,97357246};
43  int src[]={13, 773, 28, 98, 731, 97357246};
44  cout << calc(src,sizeof(src)/sizeof(src[0]))<<endl;
45}
46

下面的代碼是個半成品：

#include<iostream>
#include<sstream>
#include<cmath>
using namespace std;

const double Result = 24;
const size_t Cards = 6;
double number[Cards]={11,21,31,41,51,61};
char op[Cards+1] = {0};
size_t pos[Cards];

static long long count1=0;
static long long count2=0;
static bool calc(size_t step);

inline bool calc2(size_t step, size_t i, double na, double nb, char op9)
{
  op[i] = op9;
  switch (op9) {
    case '+':   number[i] = na + nb; break;
    case '-':   number[i] = na - nb; break;
    case '*':   number[i] = na * nb; break;
    case '/':   number[i] = na / nb; break;
    default : break;
  }
  return calc(step-1);
}

inline bool iszero(double num)
{
  const double Zero = 1e-9; 
  if (num > Zero || num < -1.0 * Zero) return false; 
  return true;
}

size_t getop(const char op9)
{
  static size_t arr[256]= {0}; 
  arr['+']=1,arr['-']=1,arr['*']=4,arr['/']=4;
  return arr[(size_t)op9];
}


bool calc(size_t step)
{
  ++count1;
  if (step <= 1) {
    ++count2;   
    if (fabs(number[0] - Result)<1e-6) {
      return true; 
    }  
    return false;
  } 
  for(size_t i = 0; i < step; i++){
    for(size_t j = i + 1; j < step; j++) {
      double na = number[i];
      double nb = number[j];
      unsigned char op1=op[i];
      unsigned char op2=op[j];
      op[j] = op[step - 1];
      number[j] = number[step - 1];
      bool ba=true, bb=true;
      size_t v=getop(op1)+getop(op2);
      
      if (v==5) ba=bb=false;
      else if (v==2) ba=false;
      else if (v==8) bb=false;
      // else if (v==1 || v==4) {
        // unsigned char ch2= op1 + op2;      
        // if (ch2=='-') ba=false;
        // else if (ch2=='/') bb=false;
      // } 
    
       
      //if (v==5) ba=bb=false;
      // else if (((v-1)&v)==0) { //case: 1 2 4 8
        // if (v==2) ba=false;
        // else if (v==8) bb=false;
        // else {
          // unsigned char ch2= op1 | op2;      
          // if (ch2=='-') ba=false;
          // else if (ch2=='/') bb=false;          
        // }   
      // }   
      
      //if (1) ba=bb=true;         
      if (ba) {
        if (calc2(step, i, na, nb, '+')) return true;
        if (calc2(step, i, na, nb, '-')) return true;
        if (calc2(step, i, nb, na, '-')) return true;
      }
      if (bb) {
        if (calc2(step, i, na, nb, '*')) return true;
        if (! iszero(nb) && calc2(step, i,na, nb, '/')) return true;
        if (! iszero(na) && calc2(step, i,nb, na, '/')) return true; 
      } 
     
      number[i] = na;
      number[j] = nb;
      op[i] = op1;
      op[j] = op2;     
    }
  }
  return false;
}

int main()
{
  for (size_t i=0; i<Cards; ++i) pos[i]=i;
  cout<< calc(Cards)<<endl;
  cout<< count1<<"  "<<count2<<endl; 
}