24点
最编程
2024-08-03 10:15:41
...
hiho一下,第九十八周:给定四个整数,判断是否能计算出24
思路:假设我们用⊙表示运算,⊙除了可以表示基本的”+”,”-“,”*”,”/”外。我们还引入两个新的运算,”反-“,和”反/”。
比如(a 反/ b)的意思是(b / a)。则对形如(c / (a + b))的形式,就可以等价的描述为((a + b) 反/ c)。
利用这6种运算,可以将所有可能的计算过程归结为2类:
(((a ⊙ b) ⊙ c ) ⊙ d)
((a ⊙ b) ⊙ (c ⊙ d))
输入
第1行:1个正整数, t,表示数据组数,2≤t≤100。
第2..t+1行:4个正整数, a,b,c,d,1≤a,b,c,d≤10。
输出
第1..t行:每行一个字符串,第i行表示第i组能否计算出24点。若能够输出”Yes”,否则输出”No”。
样例输入
2
5 5 5 1
9 9 9 9
样例输出
Yes
No
代码实现:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
#define eps 1e-8
#define rep(i,a,b) for(int i=a;i<=b;i++)
int operand[4];
char opt[3];
char optType[] = { '+', '-', '*', '/', '#', '\\' };
float calcExpression(float a,float b,char opt)
{
float result=0.0;
switch (opt)
{
case '+':
result = a + b;
break;
case '-':
result = a - b;
break;
case'*':
result = a*b;
break;
case '/':
result = a / b;
break;
case'#':
result = b - a;
break;
case '\\':
result = b / a;
break;
default:
break;
}
return result;
}
bool calcResult()
{
float result,result1,result2;
result = calcExpression(operand[0], operand[1], opt[0]);
result = calcExpression(result, operand[2], opt[1]);
result = calcExpression(result, operand[3], opt[2]);
if (fabs(result - 24) < eps)
return true;
result1 = calcExpression(operand[0], operand[1], opt[0]);
result2 = calcExpression(operand[2], operand[3], opt[2]);
result = calcExpression(result1, result2, opt[1]);
if (fabs(result - 24) < eps)
return true;
return false;
}
bool dfsOpt(int depth)
{
if (depth == 3)
return calcResult();
for (int i = 0; i < 6; i++)
{
opt[depth] = optType[i];
if(dfsOpt(depth + 1))
return true;
}
return false;
}
bool dfsNum(int depth)
{
if (depth == 4)
return dfsOpt(0);
for (int i = depth; i < 4; i++)
{
swap(operand[i], operand[depth]);
if(dfsNum(depth + 1))
return true;
swap(operand[i], operand[depth]);
}
return false;
}
int main()
{
int test;
scanf("%d", &test);
while (test--)
{
scanf("%d%d%d%d", &operand[0], &operand[1], &operand[2], &operand[3]);
if (dfsNum(0))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
上一篇: 24点