爬楼梯
2018-06-17 23:10:45来源:未知 阅读 ()
问题描述:
假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?
样例:
n=3,1+1+1=1+2=2+1=3,共有3中不同的方法
数据输入:1 2 3 4 5 10 100 50 25
数据输出:1 2 3 5 8 89 null null 121393
涉及的数据类型:int
解题思路:
St1、1阶楼梯--》1--》1种方法
2阶楼梯--》1+1,2--》2种方法
3阶楼梯--》1+1+1,1+2,2+1--》3中方法
4阶楼梯--》1+1+1+1,2+1+1,1+2+1,1+1+2,2+2,--》5中方法
St2、因为只能走1或2个台阶,所以,最后一步要么是1,要么是2。假设为n阶楼梯,则 最后一步为从n-2走两步或者从n-1走一步
St3、如果为n-2,则又将重复st2,又分为两种情况,不难得出可以用递归思想解决问题。F(n)=f(n-1)+f(n-2) 当n>2时,可以进行如上做法,当n依次递减,等于2或1时,由在st1中可得,都可一步完成。然后程序结束
得如下函数代码
if(n==1)
return 1;
else if(n==2)
return 2;
else return fun(n-1)+fun(n-2);
易错点(需要考虑的特殊情况):
由于使用的是递归函数,占用内存较大,使用的又是int数据类型,范围有限,所以在输入数字较大的时候发生了溢出现象。如果要计算较大范围的话,使用double类型会比较好
主要算法描述(伪代码):
Cin>>n
Cout<<Fun(n)
Repeat{
Fun(n)
{if(n==1) +1
Else If(n==2) +2
Else if fun(n-1)+fun(n-2)}}
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:18:验证子串
- P1358 扑克牌 2020-05-06
- 表达式·表达式树·表达式求值 2020-04-29
- C++ 函数模板 2020-04-24
- WDK驱动调试问题点滴 2020-04-21
- 螺旋矩阵问题 2020-04-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash