程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 算24點程序:面向過程與面向對象的C++

算24點程序:面向過程與面向對象的C++

編輯: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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved