本文實(shí)例為大家分享了C語(yǔ)言經(jīng)典24點(diǎn)算法的具體實(shí)現(xiàn)代碼，供大家參考，具體內(nèi)容如下

1、概述

　　給定4個(gè)整數(shù)，其中每個(gè)數(shù)字只能使用一次；任意使用 + - * / ( ) ，構(gòu)造出一個(gè)表達(dá)式，使得最終結(jié)果為24，這就是常見(jiàn)的算24點(diǎn)的游戲。這方面的程序很多，一般都是窮舉求解。本文介紹一種典型的算24點(diǎn)的程序算法，并給出兩個(gè)具體的算24點(diǎn)的程序：一個(gè)是面向過(guò)程的C實(shí)現(xiàn)，一個(gè)是面向?qū)ο蟮膉ava實(shí)現(xiàn)。

2、基本原理

　　基本原理是窮舉4個(gè)整數(shù)所有可能的表達(dá)式，然后對(duì)表達(dá)式求值。

　　表達(dá)式的定義： expression = (expression|number) operator (expression|number)

　　因?yàn)槟苁褂玫?種運(yùn)算符 + - * / 都是2元運(yùn)算符，所以本文中只考慮2元運(yùn)算符。2元運(yùn)算符接收兩個(gè)參數(shù)，輸出計(jì)算結(jié)果，輸出的結(jié)果參與后續(xù)的計(jì)算。

　　由上所述，構(gòu)造所有可能的表達(dá)式的算法如下：

　　(1) 將4個(gè)整數(shù)放入數(shù)組中

　　(2) 在數(shù)組中取兩個(gè)數(shù)字的排列，共有 P(4,2) 種排列。對(duì)每一個(gè)排列，

　　(2.1) 對(duì) + - * / 每一個(gè)運(yùn)算符，

　　(2.1.1) 根據(jù)此排列的兩個(gè)數(shù)字和運(yùn)算符，計(jì)算結(jié)果

　　(2.1.2) 改表數(shù)組：將此排列的兩個(gè)數(shù)字從數(shù)組中去除掉，將 2.1.1 計(jì)算的結(jié)果放入數(shù)組中

　　(2.1.3) 對(duì)新的數(shù)組，重復(fù)步驟 2

　　(2.1.4) 恢復(fù)數(shù)組：將此排列的兩個(gè)數(shù)字加入數(shù)組中，將 2.1.1 計(jì)算的結(jié)果從數(shù)組中去除掉

　　可見(jiàn)這是一個(gè)遞歸過(guò)程。步驟 2 就是遞歸函數(shù)。當(dāng)數(shù)組中只剩下一個(gè)數(shù)字的時(shí)候，這就是表達(dá)式的最終結(jié)果，此時(shí)遞歸結(jié)束。

　　在程序中，一定要注意遞歸的現(xiàn)場(chǎng)保護(hù)和恢復(fù)，也就是遞歸調(diào)用之前與之后，現(xiàn)場(chǎng)狀態(tài)應(yīng)該保持一致。在上述算法中，遞歸現(xiàn)場(chǎng)就是指數(shù)組，2.1.2 改變數(shù)組以進(jìn)行下一層遞歸調(diào)用，2.1.3 則恢復(fù)數(shù)組，以確保當(dāng)前遞歸調(diào)用獲得下一個(gè)正確的排列。

　　括號(hào) () 的作用只是改變運(yùn)算符的優(yōu)先級(jí)，也就是運(yùn)算符的計(jì)算順序。所以在以上算法中，無(wú)需考慮括號(hào)。括號(hào)只是在輸出時(shí)需加以考慮。

3、面向過(guò)程的C實(shí)現(xiàn)

　　這是 csdn 算法論壇前版主海星的代碼，程序非常簡(jiǎn)練、精致：

#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;　
　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　 expression[i]　=　'('　+　expa　+　'*'　+　expb　+　')';　
　　　　　　　　　　　 number[i]　=　a　*　b;　
　　　　　　　　　　　 if　(　Search(n　-　1)　)　return　true;　
　　　　　　　　　　　 if　(b　!=　0)　{　
　　　　　　　　　　　　　　　 expression[i]　=　'('　+　expa　+　'/'　+　expb　+　')';　
　　　　　　　　　　　　　　　 number[i]　=　a　/　b;　
　　　　　　　　　　　　　　　 if　(　Search(n　-　1)　)　return　true;　
　　　　　　　　　　　 }　　
　　　　　　　　　　　 if　(a　!=　0)　{　
　　　　　　　　　　　　　　　 expression[i]　=　'('　+　expb　+　'/'　+　expa　+　')';　
　　　　　　　　　　　　　　　 number[i]　=　b　/　a;　
　　　　　　　　　　　　　　　 if　(　Search(n　-　1)　)　return　true;　
　　　　　　　　　　　 }　
　　　　　　　　　　　 number[i]　=　a;　
　　　　　　　　　　　 number[j]　=　b;　
　　　　　　　　　　　 expression[i]　=　expa;　
　　　　　　　　　　　 expression[j]　=　expb;　
　　　　　　　 }　
　　　 }　
　　　 return　false;　
}　
void　main()　
{　
　　　 for　(int　i　=　0;　i　<　COUNT_OF_NUMBER;　i++)　{　
　　　　　　　 char　buffer[20];　
　　　　　　　 int　　x;　
　　　　　　　 cin　>>　x;　
　　　　　　　 number[i]　=　x;　
　　　　　　　 itoa(x,　buffer,　10);　
　　　　　　　 expression[i]　=　buffer;　
　　　 }　
　　　 if　(　Search(COUNT_OF_NUMBER)　)　{　
　　　　　　　 cout　<<　"Success."　<<　endl;　
　　　 }　else　{　
　　　　　　　 cout　<<　"Fail."　<<　endl;　
　　　 }　　　　　　　　　
}

使用任一個(gè) c++ 編譯器編譯即可。

　　這個(gè)程序的算法與 2、基本原理所述的算法基本相同。其中 bool Search(int n) 就是遞歸函數(shù)，double number[] 就是數(shù)組。程序中比較重要的地方解釋如下：

　　(1) string expression[] 存放每一步產(chǎn)生的表達(dá)式，最后的輸出中要用到。expression[] 與 number[] 類似，也是遞歸調(diào)用的現(xiàn)場(chǎng)，必須在下一層遞歸調(diào)用前改變、在下一層遞歸調(diào)用后恢復(fù)。

　　(2) number[] 數(shù)組長(zhǎng)度只有4。在 search() 中，每次取出兩個(gè)數(shù)后，使用局部變量 a, b 保存這兩個(gè)數(shù)，同時(shí)數(shù)組中加入運(yùn)算結(jié)果，并調(diào)整數(shù)組使得有效的數(shù)字都排列在數(shù)組前面。在下一層遞歸調(diào)用后，利用局部變量 a, b 恢復(fù)整個(gè)數(shù)組。對(duì) expression[] 的處理與 number[] 類似。

　　(3) 因?yàn)?+ * 滿足交換率而 - / 不滿足，所以程序中，從數(shù)組生成兩個(gè)數(shù)的排列，

　　for (int i = 0; i < n; i++) {

　　for (int j = i + 1; j < n; j++) {

　　其內(nèi)層循環(huán) j 是從 i+1 -> n，而非從 0->n ，因?yàn)閷?duì)于交換率來(lái)說(shuō)，兩個(gè)數(shù)字的順序是無(wú)所謂的。當(dāng)然，循環(huán)內(nèi)部對(duì) - / 做了特殊處理，計(jì)算了 a-b b-a a/b b/a 四種情況。

　　(4) 此程序只求出第一個(gè)解。當(dāng)求出第一個(gè)解時(shí)，通過(guò)層層 return true 返回并輸出結(jié)果，然后程序結(jié)束。

　　(5) 以 double 來(lái)進(jìn)行求解，定義精度，用以判斷是否為 24 ?？紤] (5-1/5)*5 這個(gè)表達(dá)式就知道這么做的原因了。

　　(6) 輸出時(shí)，為每個(gè)表達(dá)式都添加了括號(hào)。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論