青蛙跳台阶系列

68 阅读 0 评论 45 点赞

我是靠谱客的博主义气小懒猪，最近开发中收集的这篇文章主要介绍青蛙跳台阶系列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

青蛙每次只能跳1个或2个台阶，有n阶台阶，青蛙有多少种跳法？

一次只能挑一阶或者两阶时。如果只有1阶，那么一共有1种跳法；
如果有2阶，那么一共有2种跳法。如果有n阶时，这要倒过来想，最后一步青蛙只能从第n-1或者n-2这两种情况往上跳。

f(n)=f(n-1)+f(n-2)
f(0)=0 f(1)=1 f(2)=2

//递归
   public int digui2(int num) {
       if (num<=0) {
           return 0;
       }else if (num == 1) {
           return 1;
       }else if (num == 2) {
           return 2;
       }else {
           return digui2(num-1)+digui2(num-2);
       }
   }

   //循环
   public int loop2(int num) {
       int x=1, y=2, temp;
       if (num<=0) {
           return 0;
       }else if (num == 1) {
           return 1;
       }else if (num == 2) {
           return 2;
       }else {
           for(int i=0; i<num-2; i++){
               temp = y;
   y = x + y;
   x = temp;
           }
           return y;
       }
   }

青蛙每次能跳1个或2个，……n个台阶，有n阶台阶青蛙有多少种跳法？

假设一共有n阶，同样共有f(n)种跳法，那么这种情况就比较多，最后一步超级蛙可以从n-1阶往上跳，也可以n-2阶，也可以n-3…等等等，一次类推。

f(n)=f(n-1)+f(n-2)+..
f(n-1)=f(n-2)+..
f(n)=2f(n-1) f(1)=1 f(n)=2^(n-1)

//递归
   public int digui1(int num) {
       if (num<=0) {
           return 0;
       }else if (num == 1) {
           return 1;
       }else {
           return 2*digui1(num-1);
       }
   }

   //循环
   public int loop1(int num) {
       int sum=1;
       if (num<=0) {
           return 0;
       }else if (num == 1) {
           return 1;
       }else {
           for (int i = 0; i < num-1; i++) {
               sum*=2;
           }
           return sum;
       }

   }