斐波那契数列解楼梯走法问题

Love The Way You Lie 2022-06-18 04:07 136阅读 0赞

/\*  
题目描述  
N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）   
输入描述:  
输入包括一个整数N,(1<=N<90)。  
  
  
输出描述:  
可能有多组测试数据，对于每组数据，  
输出当楼梯阶数是N时的上楼方式个数。  
  
  
输入例子:  
4  
  
  
输出例子:  
5  
  
  
解法：  
一次可以走两阶或一阶，  
N = 1的时候只有一种方法。  
N = 2的时候有两种方法。  
N = K的时候，可以先走到k-1那里，然后向前走一阶，或者先走到k-2那里然后前走两阶，所以后一个答案是前两个的答案之和。  
到第N阶楼梯的方式为F(N)=F(N-1)+F(N-2).

\* \*/

package com.ldp;
    
    import java.util.Scanner;
    
    public class Fibonacci {
        public static void main(String[] args)
        {
            Scanner sc=new Scanner(System.in);
            
            while(sc.hasNext())
            {
                int n=sc.nextInt();
                if(n>=1&&n<90)
                {
                    //long out=fibonacci(n);
                	//System.out.println(out);
                    long out2=fibonacci2(n);
                	System.out.println(out2);
                }
                
            }
        }
        
    
    	//非递归解法
         public static long fibonacci(int n)
         {
        	 long[] arr=new long[n+1];
             arr[1]=1;
             arr[2]=2;
             for(int i=3;i<=n;i++)
             {
                 arr[i]=arr[i-1]+arr[i-2];
             }
             return arr[n];
         }
         
         //递归解法,太慢了。。。
         public static long fibonacci2(int n)
         {
        	 if(n==1)
        		 return 1;
        	 else if(n==2)
        		 return 2;
        	 else
        	 {	 
        		 return fibonacci2(n-1)+fibonacci2(n-2);
        	 }
        		 
         }
    }