博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
算24 (递归)
阅读量:7115 次
发布时间:2019-06-28

本文共 1158 字,大约阅读时间需要 3 分钟。

给出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个数中,先选出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")<

转载于:https://www.cnblogs.com/zhanyeye/p/9746108.html

你可能感兴趣的文章
VC 6.0下载 VC 6.0英文版下载 Visual C++ 6.0 英文企业版 集成SP6完美版(最新更新地址,百度网盘)...
查看>>
递归-汉诺塔
查看>>
SAMtools: SAM格式的处理利器
查看>>
AI工程师成长之路--机器学习之模型评估与选择
查看>>
菜鸟排查数据库异常的事
查看>>
CSS:关于元素宽度与高度的讨论 系列文章(一)
查看>>
webstorm、phpstorm、idea等使用技巧记录
查看>>
腾讯内核团队发布 TCPA,为何是 OPEN 而非开源?
查看>>
Linux 用户被差别对待?无法通过 apple.com 管理 Apple ID
查看>>
芯片巨人英特尔的 Linux 开源驱动加入支持其独显的代码
查看>>
Elasticsearch批量导入数据脚本(python)
查看>>
Android Studio 3.5 Canary 12 发布
查看>>
我在 DC010 听了一场黑客版“奇葩说”|ISC2018
查看>>
js算法初窥06(算法模式03-函数式编程)
查看>>
【视频教程】微信小程序开发【一个实例】
查看>>
一看就懂的Mybatis框架入门笔记
查看>>
Rails 5.2.3 RC1 发布,Ruby Web 应用开发框架
查看>>
Android RecyclerView从入门到玩坏
查看>>
Riot v4.0.0-alpha.10 发布,JavaScript 的 MVP 框架
查看>>
Linux中管理用户和组命令
查看>>