剑指offer之青蛙跳台阶问题

1 问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求该青蛙跳上一个n级的台阶总共有多少种跳法？

2 分析

我们可以定位函数f(n),n为n级别的台阶，f(n)的值是青蛙有多少种跳法，我们知道当n为1的时候，f(1) = 1;

当n为2的时候，我们知道可以先跳一级再跳一级，或者直接跳2级，这里就有2种跳法，所以f(2) = 2;

当n为3的时候，我们可以这样理解，青蛙先跳一级，后面还有n-1级需要跳，所以这里的跳法为f(n - 1);

或者青蛙先跳两级，后面还有n-2级需要跳，所以这里的跳法为f(n - 2); 所以我们知道当n大于2时，f(n) = f(n - 1) + f(n - 2);

  

   

    

     

    
    

     

      f(1) = 1; (n = 1)
     
    
   

    

     

    
    

     

      f(2) = 2; (n = 2)
     
    
   

    

     

    
    

     

      f(n) = f(n - 1) + f(n - 2); (n > 2)
     
    
  
 

3 代码实现

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      long long fibonacciOne(unsigned int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (n <= 0)
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     
 if (n == 1)
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

     
 if (n == 2)
     
    
   

    

     

    
    

     
 return 2;
     
    
   

    

     

    
    

     
 return fibonacciOne(n - 1) + fibonacciOne(n - 2);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      long long fibonacciTwo(unsigned int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (n <= 0)
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     
 if (n == 1)
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

     
 if (n == 2)
     
    
   

    

     

    
    

     
 return 2;
     
    
   

    

     

    
    

     
 long long first = 1;
     
    
   

    

     

    
    

     
 long long second = 2;
     
    
   

    

     

    
    

     
 long long sum = 0;
     
    
   

    

     

    
    

     
 for (int  i = 3; i <=n ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sum = first + second;
     
    
   

    

     

    
    

     

       first = second;
     
    
   

    

     

    
    

     

       second = sum;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return sum;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(void) 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 long long resultOne = fibonacciOne(4);
     
    
   

    

     

    
    

     
 long long resultTwo = fibonacciTwo(4);
     
    
   

    

     

    
    

     
 printf("resultOne is %lld\n", resultOne);
     
    
   

    

     

    
    

     
 printf("resultTwo is %lld\n", resultTwo);
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

  

   

    

     

    
    

     

      resultOne is 5
     
    
   

    

     

    
    

     

      resultTwo is 5
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/101568390