要注意题目要求从小到大枚举,符号也是有优先级,只需有循环控制即可(我们也可以从样例发现,数字顺序可以改变)
对数字进行全排列
如果有解,输出一个解即可
描述
4点游戏是经典的纸牌益智游戏。
常见游戏规则:
从扑克中每次取出4张牌(只有1-10点)。使用加减乘除,第一个能得出24者为赢。按照要求编程解决24点游戏。
按照要求编程解决24点游戏。
对输入的4个数据A,B,C,D
(1)按从小到大枚举
(2)对三个符号位按照+,-,*,/的优先级枚举(例如+优先级> - > * > / > +-+ > … > /// )
对每种情况按如下公式顺序枚举
牧举公式顺序:
(1) (AoB)o(CoD)
(2) ((AoB)oC)oD
(3) (Ao(BoC))oD
(4) Ao((BoC)oD)
(5) Ao(Bo(CoD))输出第一次找到的公式。
如果无法找到,输出“No match”
输入
输入4个十以下整数
输出
输出第一次找到的公式。
如果无法找到,输出“No match”
样例输入
5 5 1 5
5 5 5 1
8 8 3 3
7 3 7 3
1 2 3 4
样例输出
(5-(1/5))*5==24
(5-(1/5))*5==24
8/(3-(8/3))==24
(3+(3/7))*7==24
((1+2)+3)*4==24
Code
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#define eps 1e-4
using namespace std;
bool search(double a,double b,double c,double d);
int caculate1(double a,double b,double c,double d,int i,int j,int k);
double caculate2(double a,int i,double b);
char symbol[5]={'+','-','*','/'};
int main(){
vector<double> ans(4);
while(cin>>ans[0]>>ans[1]>>ans[2]>>ans[3]){
bool flag=false;
sort(ans.begin(),ans.end());
do{
if(search(ans[0],ans[1],ans[2],ans[3])){
flag = true;
break;
}
}while(next_permutation(ans.begin(),ans.end()));
if(!flag) cout<<"No match"<<endl;
}
return 0;
}
bool search(double a,double b,double c,double d){
int i,j,k,result;
for( i=0;i<4;i++){
for( j=0;j<4;j++){
for( k=0;k<4;k++){
result=caculate1(a,b,c,d,i,j,k);
if(result) return true;
}
}
}
return false;
}
int caculate1(double a,double b,double c,double d,int i,int j,int k){
int ans=0;
//1
if(fabs(caculate2(caculate2(a,i,b),j,caculate2(c,k,d))-24)<eps) {
printf("(%.0lf%c%.0lf)%c(%.0lf%c%.0lf)==24\n",a,symbol[i],b,symbol[j],c,symbol[k],d);
ans=1;
return ans;
}
//2
if(fabs(caculate2(caculate2(caculate2(a,i,b),j,c),k,d)-24)<eps){
printf("((%.0lf%c%.0lf)%c%.0lf)%c%.0lf==24\n",a,symbol[i],b,symbol[j],c,symbol[k],d);
ans=1;
return ans;
}
//3
if(fabs(caculate2(caculate2(a,i,caculate2(b,j,c)),k,d)-24)<eps){
printf("(%.0lf%c(%.0lf%c%.0lf))%c%.0lf==24\n",a,symbol[i],b,symbol[j],c,symbol[k],d);
ans=1;
return ans;
}
//4
if(fabs(caculate2(a,i,caculate2(caculate2(b,j,c),k,d))-24)<eps){
printf("%.0lf%c((%.0lf%c%.0lf)%c%.0lf)==24\n",a,symbol[i],b,symbol[j],c,symbol[k],d);
ans=1;
return ans;
}
//5
if(fabs(caculate2(a,i,caculate2(b,j,caculate2(c,k,d)))-24)<eps){
printf("%.0lf%c(%.0lf%c(%.0lf%c%.0lf))==24\n",a,symbol[i],b,symbol[j],c,symbol[k],d);
ans=1;
return ans;
}
return ans;
}
double caculate2(double a,int i,double b){
switch(symbol[i]){
case '+':return (a+b);break;
case '-':return (a-b);break;
case '*':
return (a*b);break;
case '/': return (a/b);break;
}
}