2-08. 用扑克牌计算24点(25) (ZJU_PAT 数学 枚举)

时间:2023-03-10 03:31:22
2-08. 用扑克牌计算24点(25) (ZJU_PAT 数学 枚举)

题目链接:http://pat.zju.edu.cn/contests/ds/2-08

一副扑克牌的每张牌表示一个数(J、Q、K分别表示11、12、13,两个司令都表示6)。任取4张牌。即得到4个1~13的数,请加入运算符(规定为加+ 减- 乘* 除/ 四种)使之成为一个运算式。

每一个数仅仅能參与一次运算。4个数顺序能够随意组合,4个运算符随意取3个且能够反复取。运算遵从一定优先级别,可加括号控制。终于使运算结果为24。请输出一种解决方式的表达式,用括号表示运算优先。假设没有一种解决方式,则输出-1表示无解。

输入格式说明:

输入在一行中给出4个整数,每一个整数取值在[1, 13]。

输出格式说明:

输出一种解决方式的表达式,用括号表示运算优先。假设没有解决方式。请输出-1。

例子输入与输出:

序号 输入 输出
1
2 3 12 12
((3-2)*12)+12
2
5 5 5 5
(5*5)-(5/5)
3
1 3 5 6
(1+(3*6))+5
4
8 13 9 4
8+((13-9)*4)
5
2 13 7 7
2*(13-(7/7))
6
5 5 5 2
-1

PS:

此题思路:http://blog.sina.com.cn/s/blog_81727a7f01017e9a.html

暴力枚举每次所选的数字和运算符的五种不同运算姿势!

代码例如以下:

#include <cstdio>

char op[5]= {'#','+','-','*','/',};

double cal(double x,double y,int op)
{
switch(op)
{
case 1:
return x+y;
case 2:
return x-y;
case 3:
return x*y;
case 4:
return x/y;
}
} double cal_m1(double i,double j,double k,double t,int op1,int op2,int op3)
{
double r1,r2,r3;
r1 = cal(i,j,op1);
r2 = cal(r1,k,op2);
r3 = cal(r2,t,op3);
return r3;
} double cal_m2(double i,double j,double k,double t,int op1,int op2,int op3)
{
double r1,r2,r3 ;
r1 = cal(i,j,op1);
r2 = cal(k,t,op3);
r3 = cal(r1,r2,op2);
return r3;
} double cal_m3(double i,double j,double k,double t,int op1,int op2,int op3)
{
double r1,r2,r3;
r1 = cal(j,k,op2);
r2 = cal(i,r1,op1);
r3 = cal(r2,t,op3);
return r3;
} double cal_m4(double i,double j,double k,double t,int op1,int op2,int op3)
{
double r1,r2,r3 ;
r1 = cal(k,t,op3);
r2 = cal(j,r1,op2);
r3 = cal(i,r2,op1);
return r3;
} double cal_m5(double i,double j,double k,double t,int op1,int op2,int op3)
{
double r1,r2,r3;
r1 = cal(j,k,op2);
r2 = cal(r1,t,op3);
r3 = cal(i,r2,op1);
return r3;
} int get_24(int i,int j,int k,int t)
{
for(int op1 = 1; op1 <= 4; op1++)
{
for(int op2 = 1; op2 <= 4; op2++)
{
for(int op3 = 1; op3 <= 4; op3++)
{
if(cal_m1(i,j,k,t,op1,op2,op3) == 24)
{
printf("((%d%c%d)%c%d)%c%d\n",i,op[op1],j,op[op2],k,op[op3],t);
return 1;
}
if(cal_m2(i,j,k,t,op1,op2,op3) == 24)
{
printf("(%d%c%d)%c(%d%c%d)\n",i,op[op1],j,op[op2],k,op[op3],t);
return 1;
}
if(cal_m3(i,j,k,t,op1,op2,op3) == 24)
{
printf("(%d%c(%d%c%d))%c%d\n",i,op[op1],j,op[op2],k,op[op3],t);
return 1;
}
if(cal_m4(i,j,k,t,op1,op2,op3) == 24)
{
printf("%d%c(%d%c(%d%c%d))\n",i,op[op1],j,op[op2],k,op[op3],t);
return 1;
}
if(cal_m5(i,j,k,t,op1,op2,op3) == 24)
{
printf("%d%c((%d%c%d)%c%d)\n",i,op[op1],j,op[op2],k,op[op3],t);
return 1;
} }
}
}
return 0;
} int main()
{
int a[4];
int t1, t2, t3, t4;
int flag;
for(int i = 0; i < 4; i++)
scanf("%d",&a[i]);
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
if(j==i)
continue;
for(int k = 0; k < 4; k++)
{
if(i==k||j==k)
continue;
for(int t = 0; t < 4; t++)
{
if(t==i||t==j||t==k)
continue;
t1 = a[i], t2= a[j], t3= a[k], t4= a[t]; flag = get_24(t1,t2,t3,t4);
if(flag ==1)
break;
}
if(flag == 1)
break;
}
if(flag == 1)
break;
}
if(flag == 1)
break;
}
if(flag == 0)
printf("-1\n"); return 0;
}