有一个100个台阶的阶梯，一次可以选择上一个台阶，或者两个台阶，问从第一层到最后一层有多少种走法 要求代码实现

神马都是浮云

好像是蓝桥杯初试的一个题目，不过100层的数据貌似很大。把递归方程写出来之后就会发现是斐波那契数列

1. class Test2
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 System.out.println(fun(100));
   
6.         }
   
7.         //递归方程 ：f(n)=f(n-1)+f(n-2)  f(i)为走到第i层的时候的种数。
   
8.         //边界：f(0)=1;f(n<0)=0;  
   
9.         public static long fun(int n)
   
10.         {
    
11.                 long temp1=1,temp2=1,tempn=0;
    
12.                 if(n==1||n==2)return 1;
    
13.                 for(int i=3;i<=n;i++)
    
14.                 {
    
15.                         tempn=temp1+temp2;
    
16.                         temp1=temp2;
    
17.                         temp2=tempn;
    
18.                 }
    
19.                 return tempn;
    
20.         }
    
21. }
    

复制代码

这种方法最好想，当然，你也可以用递推，不过感觉数据好大，是我想错了吗?PS：换成递推了，但是数据存不下，要高精度处理

假设最后到达第n层分为两种情况，一步迈一个台阶上去和一步迈两个台阶上去
那么到达第n层的方法f[n]就分为了两大类
第一类是迈上第（n-1）的方法f[n-1]，第二类是迈上第（n-2）层的方法f[n-2]
so  f[n]=f[n-1]+f[n-2]
f[1]=1
f[2]=2
so 用一个for循环就可以了，搞什么递归啊{:soso_e113:}

lihaotian_120 发表于 2013-8-22 14:05
好像是蓝桥杯初试的一个题目，不过100层的数据貌似很大。把递归方程写出来之后就会发现是斐波那契数列这种 ...

原理是一样的，现在的问题不是说算法，估计是大数据的处理问题

1. import java.math.*;
   
2. class Test2
   
3. {
   
4.         public static void main(String[] args)
   
5.         {               
   
6.                 System.out.println(fun(100));
   
7.         }
   
8.         //递归方程 ：f(n)=f(n-1)+f(n-2)  f(i)为走到第i层的时候的种数。
   
9.         //边界：f(0)=1;f(n<0)=0;  
   
10.         public static BigInteger  fun(int n)
    
11.         {
    
12.                 BigInteger temp1=new BigInteger("1");
    
13.                 BigInteger temp2=new BigInteger("1");
    
14.                 BigInteger tempn=new BigInteger("0");
    
15.                
    
16.                 for(int i=3;i<=n;i++)
    
17.                 {
    
18.                         tempn=temp1.add(temp2);
    
19.                         temp1=temp2;
    
20.                         temp2=tempn;
    
21.                 }
    
22.                 return tempn;
    
23.         }
    
24. }
    
25. //运行结果：354224848179261915075

复制代码

这样应该可以了吧

lihaotian_120 发表于 2013-8-22 16:35
这样应该可以了吧

其实没必要用BigInteger..用double就可以.
另外这一题正确答案约为5.7E20

这道题不能用递归解.原因是用递归的话,函数每次就要调用自己2次,而这里传了一个100进来 可想而知这里调用总次数大概是2的100次方次.
2的100次方具体是多少我不知道,但是可以确定的是他肯定比5.7E20要大.运算次数已经超过了实际的结果..这样的算法是不明智的.
所以用for循环是比较简单的一种方法..
我是来求其他方法的..

白堇翎 发表于 2013-8-22 16:47
其实没必要用BigInteger..用double就可以.
另外这一题正确答案约为5.7E20

嗯嗯，谢谢指导{:soso_e113:}