精华内容
下载资源
问答
  • 题目:一只青蛙一次可以跳1级台阶,也可以跳2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。这道题还被ITEye放在了博文视点杯有奖答题活动里面。我提供种解法。1、递归求解:青蛙每跳一次前,有这样种情况:...

    题目:一只青蛙一次可以跳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;

    }

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

    欢迎和我讨论。 :)

    文章系本人原创,转载请注明作者和出处

    1

    0

    分享到:

    2012-01-07 20:50

    浏览 12377

    评论

    6 楼

    RayChase

    2012-01-18

    lethorld 写道

    既然都知道是斐波拉契数列了,那就给个通式吧:

    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)

    Good!

    5 楼

    lethorld

    2012-01-17

    既然都知道是斐波拉契数列了,那就给个通式吧:

    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)

    4 楼

    lethorld

    2012-01-17

    lethorld 写道

    RayChase 写道

    lethorld 写道

    这是个费布拉奇数列:

    F(N) = 2 * F(N-2) + 1 * {F(N-1) - F(N - 2)}

    = F(N - 1) + F(N - 2)

    解释如下:

    第N级台阶的走法可以分为:

    1)当前青蛙在N-2级台阶上,那么它跳到N级台阶有两种方法:

    I N-2 + (1) + (1) -- 跳一级到N-1,再跳一级到N

    II N-2 + (2) -- 直接跳到N级台阶

    所以有两种:即 2 * F(N-2)

    2)当前青蛙在N-1级台阶上,那它只能跳一次到N级上(但是这里面包含了上面提到的第I中情况,所以要减掉F(N - 2)

    即:1 * {F(N-1) - F(N - 2)}

    所以最后是:

    F(N) = F(N - 1) + F(N - 2)

    F(1) = 1

    F(2) = 2

    是的,不过你好像想复杂了

    跳到第N级话,

    可以先跳N-1级,再跳1级;

    也可以先跳N-2级,再跳2级。

    所以f(n)=f(n-1)+f(n-2),就是斐波那契数列。

    嗯,这样也行。但其实仔细想想,你提的和我提的是不完全一样的。可以仔细考虑如下问题:

    一个青蛙,它可以跳1、2、3、...、m步,这时候,问它跳到N级台阶的时候有多少种方法?

    你看看这个,就知道我开始列的那个式子的含义了。

    其实和你的第三种数学归纳法是异曲同工的,只是过程不一样罢了~~

    3 楼

    lethorld

    2012-01-17

    RayChase 写道

    lethorld 写道

    这是个费布拉奇数列:

    F(N) = 2 * F(N-2) + 1 * {F(N-1) - F(N - 2)}

    = F(N - 1) + F(N - 2)

    解释如下:

    第N级台阶的走法可以分为:

    1)当前青蛙在N-2级台阶上,那么它跳到N级台阶有两种方法:

    I N-2 + (1) + (1) -- 跳一级到N-1,再跳一级到N

    II N-2 + (2) -- 直接跳到N级台阶

    所以有两种:即 2 * F(N-2)

    2)当前青蛙在N-1级台阶上,那它只能跳一次到N级上(但是这里面包含了上面提到的第I中情况,所以要减掉F(N - 2)

    即:1 * {F(N-1) - F(N - 2)}

    所以最后是:

    F(N) = F(N - 1) + F(N - 2)

    F(1) = 1

    F(2) = 2

    是的,不过你好像想复杂了

    跳到第N级话,

    可以先跳N-1级,再跳1级;

    也可以先跳N-2级,再跳2级。

    所以f(n)=f(n-1)+f(n-2),就是斐波那契数列。

    嗯,这样也行。但其实仔细想想,你提的和我提的是不完全一样的。可以仔细考虑如下问题:

    一个青蛙,它可以跳1、2、3、...、m步,这时候,问它跳到N级台阶的时候有多少种方法?

    你看看这个,就知道我开始列的那个式子的含义了。

    2 楼

    RayChase

    2012-01-17

    lethorld 写道

    这是个费布拉奇数列:

    F(N) = 2 * F(N-2) + 1 * {F(N-1) - F(N - 2)}

    = F(N - 1) + F(N - 2)

    解释如下:

    第N级台阶的走法可以分为:

    1)当前青蛙在N-2级台阶上,那么它跳到N级台阶有两种方法:

    I N-2 + (1) + (1) -- 跳一级到N-1,再跳一级到N

    II N-2 + (2) -- 直接跳到N级台阶

    所以有两种:即 2 * F(N-2)

    2)当前青蛙在N-1级台阶上,那它只能跳一次到N级上(但是这里面包含了上面提到的第I中情况,所以要减掉F(N - 2)

    即:1 * {F(N-1) - F(N - 2)}

    所以最后是:

    F(N) = F(N - 1) + F(N - 2)

    F(1) = 1

    F(2) = 2

    是的,不过你好像想复杂了

    跳到第N级话,

    可以先跳N-1级,再跳1级;

    也可以先跳N-2级,再跳2级。

    所以f(n)=f(n-1)+f(n-2),就是斐波那契数列。

    1 楼

    lethorld

    2012-01-17

    这是个费布拉奇数列:

    F(N) = 2 * F(N-2) + 1 * {F(N-1) - F(N - 2)}

    = F(N - 1) + F(N - 2)

    解释如下:

    第N级台阶的走法可以分为:

    1)当前青蛙在N-2级台阶上,那么它跳到N级台阶有两种方法:

    I N-2 + (1) + (1) -- 跳一级到N-1,再跳一级到N

    II N-2 + (2) -- 直接跳到N级台阶

    所以有两种:即 2 * F(N-2)

    2)当前青蛙在N-1级台阶上,那它只能跳一次到N级上(但是这里面包含了上面提到的第I中情况,所以要减掉F(N - 2)

    即:1 * {F(N-1) - F(N - 2)}

    所以最后是:

    F(N) = F(N - 1) + F(N - 2)

    F(1) = 1

    F(2) = 2

    展开全文
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1: 输入:n = 2 输出:2 ...

    学习目标:

    目标:熟练运用 Java所学知识


    题目内容:

    本文内容: 使用Java实现:青蛙跳台阶问题


    题目描述

    一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
    答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
    示例 1:

    输入:n = 2
    输出:2

    示例 2:

    输入:n = 7
    输出:21

    示例 3:

    输入:n = 0
    输出:1

    实现思路:

    第一眼看到这个问题一点思路都没有,就把前四项结果列了出来,发现和我前段时间做的斐波那契数列有点像,然后就想到了递归;

    先设第n个台阶有f(n)种上法,会发现最后一步(上到第n个台阶的那一步)只有两种上法;
    第一种从n-1上一个;
    第二种从n-2上两个;
    所以f(n)就可以替换成f(n-1)+f(n-2),就得到的斐波那契数列的递推公式,题目就解决了

    实现代码:

    public class Practice_01 {
        public static void main(String[] args) {
           System.out.println(numWays(6)); 
        }
        public static int numWays(int n) {
            int a = 1;
            int b = 1;
            int c = 0;
    
            if (n < 2) return 1;
            else {
                for (int j = 0; j < n - 1; j++) {
                    c = a + b;
                    a = b;
                    b = c % 1000000007;
                }
            }
            return b;
        }
    }
    

    运行结果:

    13
    
    展开全文
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共需要多少种跳法。
  • 当第n级台阶时,因为青蛙只能跳一级或二级台阶,所以第n级只有两种方法过来, 即,从前级(n-1)或前两级(n-2),所以调到这两级的方法加起来即为n级方法总数 现在构成斐波那契数列(fěi bō nà qì shù liè) 注意 ...
    对于这个问题
    • 前三次都好算分别为1,2,3次,后面多的话不好简单计算
    • 当第n级台阶时,因为青蛙只能跳一级或二级台阶,所以第n级只有两种方法跳过来,
      即,从前一级(n-1)或前两级(n-2),所以调到这两级的方法加起来即为n级方法总数
    • 现在构成斐波那契数列(fěi bō nà qì shù liè)
    注意
    • 这个是斐波那契的变种,斐波那契为 1 1 2 3 5 8
    • 现在这个问题为            1 2 3 5 8
      仅仅少了个1,代码稍加改动即可

    下面代码都是基于1 2 3 5 8实现的

    1.斐波那契问题最简单的是递归实现,但是递归运行效率太低,而且python有最大递归深度,我试了一下基本上递归900次都需要很长时间.所以只简单写出来参考,不推荐

    注意:python3默认最大递归深度为998,可以通过sys.setrecursionlimit(1000)来设置最大递归深度,但是递归效率太低,所以不推荐,仅供了解

    def Fibonacci(num):
        if num <= 2:
            return num
        else:
            fn = Fibonacci(num-1) + Fibonacci(num - 2)
        return fn
    
    print(Fibonacci(30))
    
       # 运行时间   30次递归都要31秒
        Fibonacci executed in 31.423158 s
        1346269
    
    2.非递归实现
    def Fibonacci(n):
        if n <=2:
            return n
        else:
            last,last_last = 1, 2
            for i in range(n - 2):
                last,last_last = last_last, last + last_last
            return last_last
    print(Fibonacci(10000))
    
    # 非递归10000次才0.004秒
    Fibonacci executed in 0.003991 s
    544383731135652813387342609937503801353891845546959670262477
    
    3.非递归2
    def Fibonacci(n):
        if n <=3:
            return n
        else:
            last,last_last = 3,2
            for i in range((n//2)-1):
                last_last = last+last_last
                last = last+last_last
            return last_last if n%2 == 0 else last
    print(Fibonacci(30))
    
    4.列表实现(因为要添加列表元素,比2,3慢,也不太推荐)
    def Fibnacci(n):
        result = [1,2]
        if n <= 2:
            return n
        for i in range(2,n+1):
            result.append(result[i-1]+result[i-2])
        return result[n-1]
    print(Fibnacci(10000))
    
    Fibnacci executed in 0.012464 s
    5443837311356528133873426099375038013538918455469596702624
    
    展开全文
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1: 输入:n = 2 输出:2 ...

    描述:

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

    答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

    示例 1:

    输入:n = 2
    输出:2
    示例 2:

    输入:n = 7
    输出:21
    示例 3:

    输入:n = 0
    输出:1
    提示:

    0 <= n <= 100

    来源:力扣(LeetCode)

     

    代码:

    class Solution {
        
        //利用斐波那契数列会超出限制
        //要利用非递归的方式进行计算
        public int numWays(int n) {
            if(n==0){
                return 1;
            }if(n<3){
                return n;
            }
            int[] dp=new int[n+1];
            dp[1]=1;
            dp[2]=2;
            
            for(int i=3;i<=n;i++){
                dp[i]=dp[i-1]+dp[i-2];
                dp[i]=dp[i]%1000000007;
            }
            return dp[n];
    
        }
       
    }

    思路:

    利用了递归的思想,但是递归操作重复太多,会超时。所以采用非递归的方法,思路就是    假如有五阶台阶 可以看做 4+3 。。。。。。。一直到 三阶时候 可以看做2+1.

    性能:

    解法更新:

    class Solution {
        
        public int numWays(int n) {
            if(n==0){
                return 1;
            }if(n<3){
                return n;
            }
            int d1=1;
            int d2=2;
            int sum=0;
            for(int i=3;i<=n;i++){
                sum=(d1+d2)%1000000007;
                d1=d2;
                d2=sum;
    
            }
            return d2;
    
        }
       
    }

    斐波那契数列的不同表现形式  有别于最常见的表现形式

    展开全文
  • 编程题青蛙跳台阶问题Java实现题目描述...有三级台阶时,青蛙有三种跳法,由于青蛙只有两种跳法,次跳级或者次跳两级,设青蛙先采用第种方式开始跳,则跳上级,还剩两级台阶,这时它相当于选择跳上两级台阶
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。请用递归和循环2中方法实现 答案来源:https://www.cnblogs.com/minrh/p/8496549.html 如有侵权,请联系我删除! */ ...
  • 2 时,第的时候有两种不同的方式:跳一级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,f(n-1);另外种是第两级,此时跳法数目为后面剩下的n-2级台阶的跳法数目,即为f(n-2),即总数目为f...
  • 题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级.求该青蛙跳上一个n级的台阶总共有多少种跳法. 青蛙每一次跳跃只有两种选择:一是再跳1级阶梯到达第n级阶梯,此时小青蛙处于第n-1级阶梯;或者再跳2级阶梯到达第n...
  • 青蛙跳台阶

    2018-04-28 19:24:59
    一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 题目描述(2) 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有...
  • //一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 public class Solution { //方法一:递归求解 public static int JumpFloor1(int n) { if(n<1){ ...
  • 题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 分析: 方法(1):找规律发现f(n)=2^(n-1) 方法(2):可以分析,跳到当前台阶总可能数=...
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法? 分析 对于n级台阶,第一步的跳法有n种:跳1级、跳2级、跳3级…跳n级 跳1级,剩下的n-1级的跳法是f(n...
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 假设,一级台阶,有f(1)种方法,二级有f(2)种,以此类推,n级有f(n)种方法。 可以看出,f(1)=1;f(2)=2。 ...
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 该题有种解法: 一、递归的方法求解斐波那契数列 有j个台阶的时候,可以一次跳1步,再跳完j-1个台阶,也...
  • 暴力法 思路: 按照函数调用的递归树,记录符合条件的跳跃操作: python代码: class Solution: def __init__(self): self.solutions = 0 ... def jump(self, start, end): ... return self.jump(start + 1, end) + ...
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 其实就是斐波那契数列问题。 假设f(n)是n个台阶跳的次数。 f(1) = 1 f(2) 会有两个跳得方式,一...
  • 那么,假设n级台阶,那么第步就有两种情况,一步,跟两步。 情况一步,那么接下去的就是f(n-1); 情况二:两步,那么接下去的就是f(n-2)。 所以总数是f(n)=f(n-1)+f(n-2)。 public int ...
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法 参考:https://blog.csdn.net/weixin_39580031/article/details/117306937?spm=1001.2014.3001.5501 问题二 一只...
  • 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 变态跳台阶题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求...
  • 种跳法:第台阶,那么还剩下n-1个台阶还没,so 剩下的n-1个台阶的跳法有f(n-1)种 第二种跳法:第了两个台阶,那么还剩下n-2个台阶还没,so 剩下的n-2个台阶的跳法有f(n-2)种 所以,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,150
精华内容 1,260
关键字:

一只青蛙跳三级台阶