当前位置:编程学习 > C/C++ >>

算24点程序:面向过程与面向对象的C++

1、概述

  给定4个整数,其中每个数字只能使用一次;任意使用 + - * / ( ) ,构造出一个表达式,使得最终结果为24,这就是常见的算24点的游戏。这方面的程序很多,一般都是穷举求解。本文介绍一种典型的算24点的程序算法,并给出两个具体的算24点的程序:一个是面向过程的C实现,一个是面向对象的java实现。

  2、基本原理

  基本原理是穷举4个整数所有可能的表达式,然后对表达式求值。

  表达式的定义: expression = (expression|number) operator (expression|number)

  因为能使用的4种运算符 + - * / 都是2元运算符,所以本文中只考虑2元运算符。2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算。

  由上所述,构造所有可能的表达式的算法如下:

  (1) 将4个整数放入数组中
  (2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,
  (2.1) 对 + - * / 每一个运算符,
  (2.1.1) 根据此排列的两个数字和运算符,计算结果
  (2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中
  (2.1.3) 对新的数组,重复步骤 2
  (2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉

  可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束。

  在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致。在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列。

  括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序。所以在以上算法中,无需考虑括号。括号只是在输出时需加以考虑。


、面向过程的C实现

  这是 csdn 算易做图坛前版主海星的代码,程序非常简练、精致:

#include    
#include   
#include   

using  namespace  std; 

const  double  PRECISION  =  1E-6; 
const  int  COUNT_OF_NUMBER    =  4; 
const  int  NUMBER_TO_BE_CAL  =  24; 

double  number[COUNT_OF_NUMBER]; 
string  expression[COUNT_OF_NUMBER]; 

bool  Search(int  n) 

       if  (n  ==  1)  { 
               if  (  fabs(number[0]  -  NUMBER_TO_BE_CAL)  <  PRECISION  )  { 
                       cout  <<  expression[0]  <<  endl; 
                       return  true; 
               }  else  { 
                       return  false; 
               } 
       } 

       for  (int  i  =  0;  i  <  n;  i++)  { 
               for  (int  j  =  i  +  1;  j  <  n;  j++)  { 
                       double  a,  b; 
                       string  expa,  expb; 

                       a  =  number[i]; 
                       b  =  number[j]; 
                       number[j]  =  number[n  -  1]; 

                       expa  =  expression[i]; 
                       expb  =  expression[j]; 
                       expression[j]  =  expression[n  -  1]; 

                       expression[i]  =  (  +  expa  +  +  +  expb  +  ); 
                       number[i]  =  a  +  b; 
                       if  (  Search(n  -  1)  )  return  true; 
                        
                       expression[i]  =  (  +  expa  +  -  +  expb  +  ); 
                       number[i]  =  a  -  b; 
                       if  (  Search(n  -  1)  )  return  true; 
                        
                       expression[i]  =  (  +  expb  +  -  +  expa  +  ); 
                       number[i]  =  b  -  a; 
                       if  (  Search(n  -  1)  )  return  true; 
                                                

&nbs
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,