雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

《编程之美》读书笔记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的冗余计算已经严重影响了性能。要如何减少这些不必要计算呢?

可以记录得到某个计算结果时所进行操作。比如: abcd4个数取前2个,进行加法计算得到 a+b,则记录‘+’。另外,假设加减号的优先级为0,乘除号的优先级为1

ab进行减/除计算时,实际上得到 a-bb-aa/bb/a

当取出2个数ab,进行计算,这两个数上次的操作符有下面这几种情况:

都为空:

要计算6个结果,即 a+b, a-b, b-a, a*b, a/b, b/a

 

只有一个为空:假设: a = a1 op1 a2

   ⑴ 一种剪枝方法是: op1为减(除)号,则不进行加减(乘除)计算。

       因为: (a-b)-c可以转为a-(b+c),这两个表达式只要计算一个就可以。

 

⑵ 另一种剪枝方法:额外记录每次计算最靠后的那个数的位置。比如位置顺序:abcd,进行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 a2op3 (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个数计算有可能无解。显然在无解时,采用尽可能多的剪枝方法,必然会极大的提高性能。

 

另外,对于输出表达式,书上的程序进行了大量的字符串操作,实际上可以只记录,每一步取出的两个数的位置(即记录ij值),在需要输出时,再根据所记录的位置,进行相应的字符串操作就可以了。

 

书上的解法二实现



下面的代码是个半成品:




#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; 
}


posted on 2010-08-01 22:50 flyinghearts 阅读(989) 评论(0)  编辑 收藏 引用 所属分类: 编程之美C++

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理