爬楼梯

2018-06-17 23:10:45来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

问题描述:

假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

样例:

n=31+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

解题思路:

St11阶楼梯--1--1种方法

     2阶楼梯--1+1,2--2种方法

     3阶楼梯--1+1+1,1+2,2+1--3中方法

     4阶楼梯--1+1+1+1,2+1+11+2+11+1+2,2+2,--5中方法

 

St2、因为只能走12个台阶,所以,最后一步要么是1,要么是2。假设为n阶楼梯,则 最后一步为从n-2走两步或者从n-1走一步

 

St3、如果为n-2,则又将重复st2,又分为两种情况,不难得出可以用递归思想解决问题。F(n)=f(n-1)+f(n-2) n>2时,可以进行如上做法,当n依次递减,等于21时,由在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:验证子串

下一篇:统计页码数字0~9分别出现了多少次