POJ 2787 算24：暴力演算法破解二十四點遊戲

05-12

小時候，媽媽經常會讓我和小夥伴們玩一個小遊戲，叫做二十四點。就是隨機從撲克牌堆抽出4張牌，想辦法用加減乘除將這四個數字湊成24，誰先算出來就給誰好吃噠！

?(??????‵?)

很鍛煉心算有木有！

直到有一天我看到了這道題：

OpenJudge - 2787:算24

2787:算24 描述給出4個小於10個正整數，你可以使用加減乘除4種運算以及括弧把這4個數連接起來得到一個表達式。現在的問題是，是否存在一種方式使得得到的表達式的結果等於24。
這裡加減乘除以及括弧的運算結果和運算的優先順序跟我們平常的定義一致（這裡的除法定義是實數除法）。

比如，對於5，5，5，1，我們知道5 * (5 – 1 / 5) = 24，因此可以得到24。又比如，對於1，1，4，2，我們怎麼都不能得到24。
輸入
輸入數據包括多行，每行給出一組測試數據，包括4個小於10個正整數。最後一組測試數據中包括4個0，表示輸入的結束，這組數據不用處理。
輸出
對於每一組測試數據，輸出一行，如果可以得到24，輸出「YES」；否則，輸出「NO」。樣例輸入

5 5 5 1
1 1 4 2
0 0 0 0
樣例輸出
YES

NO

我為什麼不早二十年學編程......

一、思路分析

從4個數字中取兩個，分別用+、-、*、/、算出結果，將結果再放回去，這個時候四個數就剩下三個數了，且對應4則運算就有4種不同的情況，這樣的過程再來兩遍，就只剩下一個數字了，如果在所有的情況中有一種以上的情況下，最後的數字是24，那麼就可以認為，原來的4個數字是有解的。

在這個過程中有兩點需要注意

1、每次從數組中取兩個數字進行計算的時候都要考慮到所有的可能。

2、本題很坑的一點在於，數字使用的是double，這意味著，最後一個數字並不一定要和24相等，只要足夠接近24就可以了！

二、AC CODE

內存:256kB 時間:2351ms

#include <iostream>#include <vector>#include <cmath>using namespace std;const double eps=1e-5;bool dfs(vector<double>vct);int main(int argc, const char * argv[]) { double a[4]; vector<double>vct; cin>>a[0]>>a[1]>>a[2]>>a[3]; while (a[0]!=0||a[1]!=0||a[2]!=0||a[3]!=0) { for(int i=0;i<4;i++) { vct.push_back(a[i]); } cout<<(dfs(vct)?"YES":"NO")<<endl; cin>>a[0]>>a[1]>>a[2]>>a[3]; vct.clear(); vector<double>().swap(vct); }}bool dfs(vector<double>vct){ if(vct.size()==1) { if(fabs(vct[0]-24)<eps)return true; else return false; } for(int i=0;i<vct.size();i++) { for(int j=0;j<vct.size();j++) { if(i!=j) { vector<double>temp1(vct),temp2(vct),temp3(vct),temp4(vct); double t1=vct[i],t2=vct[j]; temp1.push_back(t1+t2); temp1.erase(temp1.begin()+max(i,j)); temp1.erase(temp1.begin()+min(i,j)); if(dfs(temp1))return true; temp2.push_back(t1-t2); temp2.erase(temp2.begin()+max(i,j)); temp2.erase(temp2.begin()+min(i,j)); if(dfs(temp2))return true; temp3.push_back(t1*t2); temp3.erase(temp3.begin()+max(i,j)); temp3.erase(temp3.begin()+min(i,j)); if(dfs(temp3)) return true; if(t2!=0) { temp4.push_back(t1/t2); temp4.erase(temp4.begin()+max(i,j)); temp4.erase(temp4.begin()+min(i,j)); if(dfs(temp4))return true; } } } } return false;}

有幾個需要注意的地方：

1、該方案使用vector裝數字，每算完一組記得要清空

vct.clear();vector<double>().swap(vct);

2、算完兩個數字的四則運算結果後，需要將原來的數刪除，先刪序號大的，再刪序號小的

temp1.erase(temp1.begin()+max(i,j));temp1.erase(temp1.begin()+min(i,j));

3、被除數不能為0！

4、結果與24足夠接近即可。

該方案並非最佳，博客上有人給出了更快的方法，供參考：

內存:256kB 時間:58ms

#include<cstdio>#include<algorithm>#include<cmath>#include<iostream>#include<cstring>#define db double#define CLR(x) memset(x,0,sizeof(x))using namespace std;const db eps=1e-5;db a[5];int vis[5];int dfs(int step){ if(step==1){ if(fabs(a[0]-24)<eps) return 1; else return 0; } for(int i=0;i<step-1;i++){ for(int j=i+1;j<step;j++){ db x=a[i]; db y=a[j]; a[j]=a[step-1]; a[i]=x+y; if(dfs(step-1)) return 1; a[i]=x-y; if(dfs(step-1)) return 1; a[i]=y-x; if(dfs(step-1)) return 1; a[i]=y*x; if(dfs(step-1)) return 1; a[i]=x/y; if(dfs(step-1)) return 1; a[i]=y/x; if(dfs(step-1)) return 1; a[i]=x; a[j]=y; } } return 0;}int main() { while(~scanf("%lf%lf%lf%lf",&a[0],&a[1],&a[2],&a[3])){ CLR(vis); if(a[1]+a[2]+a[3]+a[0]==0){ break; } if(dfs(4)){ printf("YES "); } else printf("NO "); }}

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

為你讀最好的書~