给出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 样例输出 YESNO
用递归将问题分解为规模更小的子问题进行求解 可以从4个数中,先选出2个数进行运算,将得到的结果和剩下的2个数找它们的运算结果可否为24,(这时为3个数查找找运算结果可否为24),继续从中选取2个数进行运算,再将结果与剩下的一个数 进行运算(这时为2个数找运算结果为24),最后就变成了1个看是否为24。 递归的结束条件即为只剩1个数时 ,若为24输出YES,否则输出NO 注意浮点数判断是否相等不能用 ==,而要看两个数只差是否足够小,比如小于1e-6. ๑乛◡乛๑get一个小知识,枚举数组中的每一对组合可以用2个for循环int a[n+1];for(int i=0; i
#include#include using namespace std;double a[5];#define EPS 1e-6bool isZero(double x){ return fabs(x)<=EPS;}bool count24(double a[],int n){ if(n==1) { if(isZero(a[0]-24)) return true; else return false; } double b[5]; for(int i=0; i >a[i]; if(isZero(a[0])&&isZero(a[1])&&isZero(a[2])&&isZero(a[3])) break; cout<<(count24(a,4) ? "YES":"NO")<