精华内容
下载资源
问答
  • 青蛙跳台阶算法

    2020-02-10 19:58:14
    青蛙跳台阶算法 一只青蛙可以一次跳上1级台阶,也可以跳上2级台阶.求该青蛙跳上一个n级的台阶总数一共需要多少种跳法? 思路: 想清楚特殊情况的存在,当n分别等于0,1,时,计算f(n)各自有几种跳法? n代表跳的台阶数f(0)=0...

    青蛙跳台阶算法
    一只青蛙可以一次跳上1级台阶,也可以跳上2级台阶.求该青蛙跳上一个n级的台阶总数一共需要多少种跳法?
    思路:
    想清楚特殊情况的存在,当n分别等于0,1,时,计算f(n)各自有几种跳法?
    n代表跳的台阶数f(0)=0,f(1)=1,
    当n等于2时,青蛙可以一次跳一级或者一次直接2级,因此f(2)=2
    当n等于3时,青蛙第一跳有两种情况:跳一级台阶或者跳两级台阶,假如跳一级台阶,那么剩下的两极台阶就是f(2), 假如跳2级台阶,那么剩下的一级台阶就是f(1),
    f(3)=f(1)+f(2)
    也可以这样理解:直接看一共n=3时,青蛙一共跳完有几种方法 ,
    假如第一次跳一级台阶,后面也都跳一级.(跳法1)
    假如第一次跳一级台阶,后面跳2级.(跳法2)
    假如第一次跳两级台阶,后面跳一级.(跳法3)
    综上:当n=3时,一共有3种跳法.f(3)=3=f(1)+f(2)
    n=4时,将各种情况依次列出来,其结果恰好等于f(2)+f(3)
    依次类推:f(n)=f(n-1)+f(n-2)

    //递归实现:
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int Func(int n){
    	if (n == 0){
    		return 0;
    	}
    	if (n == 1){
    		return 1 ;
    	}
    	if (n == 2){
    		return 2;
    	}
    	if (n>=3){
    		return Func(n-1) + Func(n-2);
    	}
    }
    
    int main(){
    	int n = 0;
    	printf("请输入青蛙一共要跳的台阶总数: \n");
    	scanf("%d",&n);
    	printf("%d\n", Func(n));
    	system("pause");
    	return 0;
    }
    

    运行结果:
    在这里插入图片描述
    递归的两个必要条件:
    1.存在限制条件,当满足这个递归条件的时候,递归将不再继续执行下去.
    2.每次递归调用之后,越来越接近限制条件

    //迭代实现:
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int Func(int n){
       // i代表几级台阶总数 n代表一共的台阶总数
    	int last1 = 1;
    	int last2 = 2;
    	int cur;
    	int i;
    	if (n == 0){
    		return 0;
    	}
    	if (n == 1){
    		return 1 ;
    	}
    	if (n == 2){
    		return 2;
    	}
    	for (i = 3;i<= n;i++){
    		cur = last1 + last2;
    		last1 = last2;
    		last2 = cur;
    	}
    	return  cur ;
    }
    
    int main(){
    	int n ;
    	printf("请输入青蛙一共要跳的台阶总数: \n");
    	scanf("%d",&n);
    	printf("%d\n", Func(n));
    	system("pause");
    	return 0;
    }
    

    运行结果:
    在这里插入图片描述
    迭代法相比递归法效率要高,避免了重复计算

    展开全文
  • 解读青蛙跳台阶算法

    2021-05-24 10:03:26
    青蛙跳台阶 题目描述: 在爬楼梯时,每次可向上走1阶台阶或2阶台阶,问有n阶楼 梯有多少种上楼的方式。 题目分析: 假设有1层楼梯,每次只能向上1阶台阶,那上楼的方式1种。 假设有2层楼梯,可以选择每次上1阶...

    青蛙跳台阶

    题目描述:

    在爬楼梯时,每次可向上走1阶台阶或2阶台阶,问有n阶楼 梯有多少种上楼的方式。

    题目分析:

    假设有1层楼梯,每次只能向上1阶台阶,那上楼的方式 1 种。

    假设有2层楼梯,可以选择每次上1阶台阶,也可以选择每次上2阶台阶,上楼方式有 2 种。

    假设有3层楼梯,相当于2阶+1阶,2 + 1 = 3 种

    假设有4阶楼梯,相当于3阶+2阶,3 + 2 =

    以此类推····

    假设有n阶楼梯,等于(n-1)阶 + (n-2)阶种

    列算式分析:

    n=1,1种方式,1

    n=2, 2种方式,(1,1 ) (2) 

    n=3, 3种方式,(1,1,1)(1,2)(2,1)

    n=4, 5种方式,(1,1,1,1)(1,1,2)(1,2,1)(2,1,1)(2,2)

    n=5, 8种方式,(1,1,1,1,1)(1,1,1,2)(1,1,2,1)(1,2,1,1)(2,1,1,1)(2,2,1)(1,2,2)(2,1,2)

    n=6, 13种方式,(1,1,1,1,1,1)(2,2,2)(1,1,1,1,2)(1,1,1,2,1)(1,1,2,1,1)(1,2,1,1,1)(2,1,1,1,1)(2,2,1,1)(2,1,1,2)(1,1,2,2)(1,2,2,1)(1,2,1,2)(2,1,2,1)

    以此类推····

    代码实现:

    public class Test {
        private int getNum(int n){
            if(n <= 2){
                return n;
            }
            return getNum(n-1)+getNum(n-2);
        }
        public static void main(String[] args) {
            System.out.println(new Test().getNum(6));
        }
    }

    以上如有问题,欢迎指正~

     

    问题来源:https://blog.csdn.net/ljfirst/article/details/103082359

    展开全文
  • 青蛙跳台阶算法分析

    千次阅读 2018-12-18 09:30:11
    青蛙跳台阶问题在面试中经常会被问到,如果你之前没听过这个算法问题,那么在面试短时间内能给出完整的答案还是有一定的难度的,但是其实也并不算很难,看完这篇文章,相信你会恍然大悟的。   一只青蛙一次可以跳...

     

    青蛙跳台阶问题在面试中经常会被问到,如果你之前没听过这个算法问题,那么在面试短时间内能给出完整的答案还是有一定的难度的,但是其实也并不算很难,看完这篇文章,相信你会恍然大悟的。

     

    一只青蛙一次可以跳一级台阶,也可以一次跳两级台阶,现在有 n 级台阶,问青蛙一共有多少种跳法?

     

    咋一看到这种问题,好像没有什么思路,不知道从哪里着手分析,那么我们就从最简单的情况开始分析,假如 n = 1,即一共只有一级台阶,显然一共就只有一种跳法,假如 n = 2,一共有两级台阶,那么可以每次跳一级跳两次,或者也可以一次跳两级,也就是说一共有两种跳法。n 越大跳法就越多,但是我们可以发现一个规律,就是把 n 拆分成各个比他小的数来分析,这里有点像分而治之的思想,即把大问题划分为若干个小问题来处理,最后再把小问题汇总去解决大问题。

     

    我们先令 f(n) 为 n 级台阶的总跳法数,那么第一次如果选择跳一级的话,那么剩下的 n-1 级台阶的跳法数就为 f(n-1),如果第一次跳两级的话,那么剩下的 n-2 级台阶的跳法就是 f(n-2),然后再回到题目中要求来看,青蛙一次只能挑一级或两级,也就是说刚刚列举的这两种情况的和就是青蛙一共有多少种跳法,所以 f(n) = f(n-1) + f(n-2)。到了这一步,我们不难看出,这其实就是数学中的斐波拉契数列,看到这里应该会有恍然大悟的感觉了,如果还没明白的话,请回到文章开头再次认真看。

     

    问题的思路已经找到了,接下来我们就用 python 来实现这个斐波拉契数列吧。关于斐波拉契数列的实现,我这里用了两种方式,一种是递归,一种是循环,其中一旦 n 数据较大时递归的效率是非常非常差的,大家可以用 n = 100 简单试一下就知道有多慢了,估计没个 10 分钟计算机是算不出来的,其时间复杂度为 O(2^n),随 n 的增加时间复杂度成指数级增长,因为在这递归过程中,我们在不断重复计算 f(n-1) 和 f(n-2) 的值,即每计算数列中的某个数,都会从 1 重新开始计算,这样的效率能不慢么,所以递归这种方式不可取。用一个简单的循环效率一下子就上来了,时间复杂度为 O(n)。 

     

    # 斐波拉契数列实现方法一:递归
    
    def fibonacci(n):
        if n > 2:
            return fibonacci(n-1) + fibonacci(n-2)
        else:
            return n    
    
    print(fibonacci(10))
    

     

    # 斐波拉契数列实现方法二:for循环
    
    def fibonacciFor(n):
        for i in range(3,n+1):
            n = (i-1) + (i-2)
        return n
    
    print(fibonacciFor(4))
    

    最后大家还可以继续思考下,如果题目条件改为一次可以跳一级,也可以一次跳 n 级,那么总共的跳法又是多少呢?这里直接给出答案吧,f(n) = 2^(n-1),这个结果是数学公式换算推导出来的,大家可以尝试去验证下。

     

    展开全文
  • python实现青蛙跳台阶算法

    千次阅读 2019-07-09 11:53:42
    青蛙每次跳台阶每次只能跳一个台阶或两个台阶,跳到第N个台阶总共有多少种跳法 解决方法: 可以转化为斐波那契数列的方式进行求解,假设要跳N阶台阶,那么第一步有两种跳法: (1)跳一步,后面还有n-1个台阶需要跳...

    问题描述:
    青蛙每次跳台阶每次只能跳一个台阶或两个台阶,跳到第N个台阶总共有多少种跳法

    解决方法:
    可以转化为斐波那契数列的方式进行求解,假设要跳N阶台阶,那么第一步有两种跳法:
    (1)跳一步,后面还有n-1个台阶需要跳;
    (2)跳两步,后面还有n-2个台阶需要跳。
    可以看到跳n阶台阶的跳法数等于跳n-1和n-2阶台阶数的和,即f(n) = f(n-1) + f(n-2)

    求解方式:
    (1)递归,代码很简洁,但不推荐此方式,有大量的重复计算

    def JumpSteps_digui(n):
        if n in (1, 2):
            return n
        return JumpSteps_digui(n-1)+JumpSteps_digui(n-2)
    

    (2)很简单的从下往上计算,时间复杂度为0(n),通常软件中采用这种写法。

    def JumpFloor_new(n):
        if n in (1, 2):
            return n
        temp1, temp2 = 1, 2
        while n > 2:
            temp = temp1 + temp2
            temp1, temp2 = temp2, temp
            n -= 1
        return temp
    
    展开全文
  • 青蛙跳台阶算法,每次可以跳1级或两级,请问有n级台阶,有多少种算法,递归求解 1.当青蛙跳跳一个台阶时,只有1中跳法 2.当青蛙跳跳2个台阶时,只有2中跳法 3.在3个台阶时,因为青蛙只能一次跳1级或者两级 因此在...
  • 青蛙在n-1阶,有f(n-1)种跳法。 在n-2阶,有f(n-2)种跳法。 那么n-1到n有一种跳法,就是一阶。 n-2到n有一种跳法,两阶。 **那为什么最后到n阶的跳法不是 f(n)=f(n-1)+f(n-2)+2呢?**
  • 青蛙跳台阶算法,每次可以跳1级或两级,请问有n级台阶,有多少种算法,递归和非递归如何写 假设,一级台阶,有f(1)种方法,二级有f(2)种,以此类推,n级有f(n)种方法。 可以看出,f(1)=1;f(2)=2。 那么,假设n...
  • 青蛙跳台阶算法 java版

    千次阅读 2019-03-17 18:02:37
    在楼梯台阶为n阶情况下,每次可1次或者2次,结果返回为到达n阶楼梯的跳法 假设在第i层台阶之前,可以通过i-1处1阶台阶到达第i层,也可通过i-2处2阶到达第i层....... 同理如果允许一次三层台阶则 可在i - 3...
  • 青蛙跳台阶问题 一只青蛙一次可以跳上 1 级台阶,也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法? 1个台阶有1种跳法 2个台阶有2种跳法 3个台阶有3种跳法 4个台阶有5种跳法 1 我们可以发现 n层...
  • 青蛙跳台阶算法,n m

    2018-11-04 23:10:29
    问题描述:一个青蛙,一次可以1级台阶,也可以2级,…也可以n级,总共有m级台阶,问青蛙总共有多少种跳法? 问题分析: 以n=2为例 当m =1 时f(1) = 1 当m =2 时f(2) = 2 当m =3 时f(3) = 3 = f(2)+f(1) 当m =4...
  • 题目:青蛙跳台阶算法,每次可以跳1级或两级,请问有n级台阶,有多少种算法 package bianchengti; /* * 青蛙跳台阶算法 * 每次可以跳1级或两级,请问有n级台阶,有多少种算法 * 递归算法 */ public ...
  • 二、青蛙跳台阶算法 类似于Fibonacci数列的算法问题 台阶数为number或n,跳法数为ret,f(n)代表跳到第n阶台阶的跳法数 算法流程分析 由于青蛙每次只能跳一个台阶或者两个台阶,故 f(n) = f(n-1) + f(n-2) 注:青蛙...
  • 青蛙跳台阶算法

    2015-08-17 20:07:04
    1、一只青蛙一次可以跳上1级台阶,也可以跳...求该青蛙跳上一个n级的台阶总共有多少种跳法。     2、一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
  • 求该青蛙跳上一个n级的台阶总共有多少种跳法。 设:青蛙从第0阶跳到第n阶有f(n)种跳法 那么青蛙跳到第n阶就有f(n)=f(0)+f(1)+f(2)+f(3)+...+f(n-1)种跳法,因为青蛙在第n阶时,有可能是从第0,1,2,3...阶跳上去的 ...
  • 算法青蛙跳台阶

    千次阅读 2019-05-02 17:22:08
    青蛙跳台阶plus版本 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 关于本题,前提是n个台阶会有一次n阶的跳法。分析如下: f(1) = 1 f(2) = f...
  • 求该青蛙跳上一个n级的台阶总共有多少种跳法。 前言 这种题目解题思路:应该是先从数学逻辑的角度来推和演算这道题,也就是先用数学公式完整地把这道题写出来,能保证写对答案。之后再结合题目,用代码来把这道题...
  • 题目:青蛙跳台阶 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1:输入:...
  • 笔试算法青蛙跳台阶 1、题目表述 //假设青蛙正在跳台阶。需要 n 阶你能到达楼顶。 //每次青蛙可以跳 1 或 2 个台阶,但不可以连续跳2个。请问有多少种不同的方法可以到楼顶呢? //注意:给定 n 是一个正整数。 2、...
  • 求该青蛙跳上一个 n 级的台阶总共有多少种跳法 参考:https://blog.csdn.net/weixin_39580031/article/details/117306937?spm=1001.2014.3001.5501 问题二 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶,…, 也...
  • 正常跳台阶:一只青蛙一次可以跳上1级台阶,也可以跳上2级,也可以跳上3级。 求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 变态跳台阶: 一只青蛙一次可以跳上1级台阶,也可以跳上...
  • 算法——青蛙跳台阶

    2021-01-01 23:02:37
    求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 规律观察: n=1,【1】 n=2,【1,1】,【2】 n=3,【1,1,1】,【1,2】,【2,1】 n=4,【1,1,1,1】,【1,2,1】,【2,1,1...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 514
精华内容 205
关键字:

青蛙跳台阶算法