C語言實現經典24點算法代碼分享

本篇內容主要講解“C語言實現經典24點算法代碼分享”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C語言實現經典24點算法代碼分享”吧!

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 則恢復數組，以確保當前遞歸調用獲得下一個正確的排列。

　　括號 () 的作用只是改變運算符的優先級，也就是運算符的計算順序。所以在以上算法中，無需考慮括號。括號只是在輸出時需加以考慮。

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

使用任一個 c++ 編譯器編譯即可。

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

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

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

　　(3) 因為 + * 滿足交換率而 - / 不滿足，所以程序中，從數組生成兩個數的排列，

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

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

　　其內層循環 j 是從 i+1 -> n，而非從 0->n ，因為對于交換率來說，兩個數字的順序是無所謂的。當然，循環內部對 - / 做了特殊處理，計算了 a-b b-a a/b b/a 四種情況。

　　(4) 此程序只求出第一個解。當求出第一個解時，通過層層 return true 返回并輸出結果，然后程序結束。

　　(5) 以 double 來進行求解，定義精度，用以判斷是否為 24 。考慮 (5-1/5)*5 這個表達式就知道這么做的原因了。

　　(6) 輸出時，為每個表達式都添加了括號。

到此，相信大家對“C語言實現經典24點算法代碼分享”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！