递归递推测试题分析讲解.ppt

递归递推测试题分析讲解.ppt

ID:52399076

大小:226.01 KB

页数:16页

时间:2020-04-05

递归递推测试题分析讲解.ppt_第1页
递归递推测试题分析讲解.ppt_第2页
递归递推测试题分析讲解.ppt_第3页
递归递推测试题分析讲解.ppt_第4页
递归递推测试题分析讲解.ppt_第5页
资源描述:

《递归递推测试题分析讲解.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、逆波兰表达式问题描述:逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2+3的逆波兰表示法为+23。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2+3)*4的逆波兰表示法为*+234。本题求解逆波兰表达式的值,其中运算符包括+-*/四个。输入数据:输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。输出要求:输出为一行,表达式的值输入样例:*+11.012.0+24.035.0输出样例:1357.0000001分析解题思路:这个问题看上去有些复杂,如果只是简单地模拟计算步骤不太容易想清楚,但是如果用递归的

2、思想就非常容易想清楚,让我们根据逆波兰表达式的定义进行递归求解。在这个递归函数中,针对当前的输入,有五种情况:1、输入是常数,则表达式的值就是这个常数2、输入的是‘+’,则表达式的值是再继续读入两个表达式并计算出它们的值3、输入的是‘-’;4、输入的是‘*’;5、输入的是‘/’;后面几种情况与2相同,只是计算从‘+’变成‘-’‘*’‘/’。2#include#includedoubleexp(){chara[10];scanf(“%s”,a);switch(a[0]){case’+’:returnexp()+exp();case’

3、-’:returnexp()-exp();case’*’:returnexp()*exp();case’/’:returnexp()/exp();default:returnatof(a);}}voidmain(){doubleans;ans=exp();printf(“%f”,ans);}3实现中常见的问题问题一:不适应递归的思路,直接分析输入的字符串,试图自己写进栈出栈的程序,写得逻辑复杂,因考虑不周出错。问题二:不会使用atof()函数,自己处理浮点数的读入,逻辑复杂出错。4放苹果问题描述:把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多

4、少种不同的放法?(用K表示)注意:5,1,1和1,5,1是同一种分法。输入数据第一行是测试数据的数目t(0<=t<=20),以下每行均包含两个整数M和N,以空格分开。1<=M,N<=10。输出要求对输入的每组数据M和N,用一行输出相应的K。输入样例173输出样例85解题思路:1、所有不同的摆放方法可以分为两类:至少有一个盘子空着和所有的盘子都不空。我们可以分别计算这两类摆放方法的数目,然后把它们加起来。对于至少空着一个盘子的情况,则N个盘子摆放M个苹果的摆放数目与N-1个盘子摆放M个苹果的摆放方法数目相同。对于所有盘子都不空的情况,则N个盘子摆放M个苹果的摆放方法

5、数目等于N个盘子摆放M-N个苹果的摆放方法数目。我们可以据此来用递归的方法求解这个问题。2、设f(m,n)为m个苹果,n个盘子的放法数目,则先对n作讨论,如果n>m,必定有n-m个盘子永远空着,去掉它们对摆放苹果放法数目不产生影响;即if(n>m)f(m,n)=f{m,m}。当n<=m时,不同的方法可以分为两类:即有至少一个盘子空着或者所有盘子都有苹果,前一种情况相当于f(m,n)=f(m,n-1);后一种情况可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即f(m,n)=f(m-n,n)。总的放苹果的放法数目等于两者的和,即f(m,n)=f(m,n-1)+f

6、(m-n,n)。整个递归过程描述如下:intf(intm,intn){if(n==1

7、

8、m==0)return1;if(n>m)returnf(m,m);returnf(m,n-1)+f(m-n,n)}3、出口条件说明:当n=1是,所有苹果都必须放到一个盘子里,所有返回1,当没有苹果可放时,定义为1种放法。递归的两条路,第一条n会逐渐减少,终会达到出口n==1;第二条m会逐渐减少,因为n>m时,我们会returnf(m,m)所以终会到达出口m==0.6#includeintcount(intx,inty){if(y==1

9、

10、x==0)return

11、1;if(x

12、块黑色的瓷

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。