青蛙跳台阶问题的三种解法

青蛙跳台阶问题的三种解法 题目:一只青蛙一次可以跳1级台阶,也可以跳2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

这道题还被ITEye放在了博文视点杯有奖答题活动里面。

我提供三种解法。

1、递归求解:

青蛙每跳一次前,有这样三种情况:

  • (1)只剩1级或0级台阶了,只能跳一步或者无法再跳了,那么这条路也走到了终点,走法的种类数可以加1;
  • (2)可以走2级台阶;
  • (3)可以走1级台阶。

于是递归方法求解:

/** 
 * 递归方法 
 */  
public static int calc(int n) {  
    return recursiveCalc(n, 0);  
}  
  
private static int recursiveCalc(int n, int total) {  
    if (1 == n || 0 == n)  
        return ++total;  
  
    total = recursiveCalc(n - 1, total);  
    return recursiveCalc(n - 2, total);  
}  

2、概率论思路求解:

首先把问题抽象成简单的数学模型,设2步台阶跳了x次,1步台阶跳了y次,那么:

2x + y = n

于是,当 x = i ,可知 x >= 0 ,且 x < n/2 (向下取整),设某时刻的 x = i ,那么有 y = n – 2 * x ,于是,总共需要走 z = i + n – 2 * x 步。

这时,问题即转化为:

z步骤中,有x个两步,y个一步,相当于z个空当,由x、y去填充,那么不同填充方法的数目符合概率公式:

C(x,z) = z! / ((z-x)!x!)

即从排列z中取其中x个数的种类,x内部无序:

/** 
 * 概率论 
 */  
public static int calc2(int n) {  
    int total = 0;  
    for (int i = 0; i <= n / 2; i++)  
        total += factorial((i) + (n - 2 * i)) / factorial(i)  
                / factorial(n - 2 * i);  
    return total;  
}  
  
private static int factorial(int n) {  
    if (0 == n)  
        return 1;  
  
    int total = 1;  
    for (int i = 1; i <= n; i++)  
        total *= i;  
    return total;  
}  

3、数学归纳法求解:

如果n=1,总步数f(n)=1;如果n=2,总步数f(n)=2。

另一方面,当n>=3,当前还剩的步数f(n),如果接下去跳一步,那么还剩下的步数是f(n-1);如果接下去跳两步,那么还剩下的步数是f(n-2),故:f(n)=f(n-1)+f(n-2)。

现设s3=f(n),s2=f(n-2),s1=f(n-1),从时间、空间复杂度来说,这也是最简单的一种方法:

/** 
 * 数学归纳法 
 */  
public static int calc3(int n) {  
    if (1 == n || 2 == n)  
        return n;  
  
    int s1 = 1, s2 = 2, s3 = 1;  
    for (int i = 3; i <= n; i++) {  
        s3 = s1 + s2;  
        s1 = s2;  
        s2 = s3;  
    }  
    return s3;  
}  

聪明的你,还有什么办法?

欢迎和我讨论。 :)

—————————————————————————————————————-

补充:

跳到第N级话,
可以先跳N-1级,再跳1级;
也可以先跳N-2级,再跳2级。
所以f(n)=f(n-1)+f(n-2),就是斐波那契数列。

既然都知道是斐波拉契数列了,那就给个通式吧:
F(N) =
  ((5+5^(1/2))/10)*(((1+5^(1/2))/2)^n) +
  ((5-5^(1/2))/10)*(((1-5^(1/2))/2)^n)
N >= 1

时间复杂度O(1)。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

3 comments

  1. 蒋小强 说道:

    递归法和斐波那契数列方法非常不错!

  2. 冯大宝 说道:

    其实不完全是斐波纳契数列,相当于是从斐波纳契数列的第二个数开始的一个数列。斐波纳契数列是1,1,2,3,5,8,而这道题是1,2,3,5,8

  3. 红色石头 说道:

    碉堡了,我只能想到递归…http://50vip.com/blog.php?i=77
    你这个验证码太难了~都没有评论的欲望了~

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: