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

本文共 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

你可能感兴趣的文章
ubuntu用户如何打开root用户并允许远程登录
查看>>
我只是表明我的态度:我热爱这个行业,请不要再片面的黑我们了
查看>>
kibana做图表无法选取需要选的字段
查看>>
WCF 第六章 编码与序列化 使用NetDataContractSerializer共享类型
查看>>
wss的webpart的3种开发方式(转载)
查看>>
如何单独编译Android源代码中的模块
查看>>
atop工具检测linux硬件异常
查看>>
OSGI环境中Quartz2.2.0使用数据库连接池
查看>>
视图、索引、存储过程优缺点
查看>>
JS、JQuery和ExtJs动态创建DOM对象
查看>>
PhotoShop简介
查看>>
SwitchHosts简明教程
查看>>
11- jmeter主要元件
查看>>
Servlet实现验证码图片(一)
查看>>
sort
查看>>
Algs4-1.2.4以下这段代码会打印出什么?
查看>>
关于链表的一些重要操作(Important operations on a Linked List)
查看>>
用JavaScript编写简单斗地主效果Es6
查看>>
使用 CODING 进行 Spring Boot 项目的集成
查看>>
Apache Commons 常用工具类整理
查看>>