首页 > 试题广场 > 跳台阶
[编程题]跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

1436个回答

添加回答
推荐

对于本题,前提只有 一次 1阶或者2阶的跳法。

a.如果两种跳法,1阶或者2阶,那么假定第一次跳的是一阶,那么剩下的是n-1个台阶,跳法是f(n-1);

b.假定第一次跳的是2阶,那么剩下的是n-2个台阶,跳法是f(n-2)

c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) 

d.然后通过实际的情况可以得出:只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

e.可以发现最终得出的是一个斐波那契数列:

        

              | 1, (n=1)

f(n) =     | 2, (n=2)

              | f(n-1)+f(n-2) ,(n>2,n为整数)
public class Solution {
    public int JumpFloor(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else if (target ==2) {
            return 2;
        } else {
            return  JumpFloor(target-1)+JumpFloor(target-2);
        }
    }
}


编辑于 2015-06-17 21:21:45 回复(52)
比较倾向于找规律的解法,f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5,  可以总结出f(n) = f(n-1) + f(n-2)的规律,但是为什么会出现这样的规律呢?假设现在6个台阶,我们可以从第5跳一步到6,这样的话有多少种方案跳到5就有多少种方案跳到6,另外我们也可以从4跳两步跳到6,跳到4有多少种方案的话,就有多少种方案跳到6,其他的不能从3跳到6什么的啦,所以最后就是f(6) = f(5) + f(4);这样子也很好理解变态跳台阶的问题了。
class Solution {
public:
    int jumpFloor(int number) {
        if (number <= 0) {
            return 0;
        }
        if (number == 1) {
            return 1;
        }
        if (number == 2) {
            return 2;
        }
        int first = 1, second = 2, third = 0;
        for (int i = 3; i <= number; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }
};
编辑于 2016-10-25 14:12:25 回复(42)

Fibonacci数列,python solution:

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, n):
        # write code here
        res=[1,1,2]
        while len(res)<=n:
            res.append(res[-1]+res[-2])
        return res[n]
发表于 2017-10-07 19:16:21 回复(2)

这道题如果用递归的话提交会显示:

运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大

于是考虑用迭代解决:

public int JumpFloor(int target) {

if(target == 1 || target == 2) {

return target;

}

// 第一阶和第二阶考虑过了,初始当前台阶为第三阶,向后迭代

// 思路:当前台阶的跳法总数=当前台阶后退一阶的台阶的跳法总数+当前台阶后退二阶的台阶的跳法总数

int jumpSum = 0;// 当前台阶的跳法总数

int jumpSumBackStep1 = 2;// 当前台阶后退一阶的台阶的跳法总数(初始值当前台阶是第3)

int jumpSumBackStep2 = 1;// 当前台阶后退二阶的台阶的跳法总数(初始值当前台阶是第3)

for(int i = 3; i <= target; i++) {

jumpSum= jumpSumBackStep1 + jumpSumBackStep2;

jumpSumBackStep2 = jumpSumBackStep1;// 后退一阶在下一次迭代变为后退两阶

jumpSumBackStep1 = jumpSum;                   // 当前台阶在下一次迭代变为后退一阶

}

return jumpSum;

}

注:思路引自答主 中大_打酱油,只是完善一下方便快速理解

发表于 2016-04-13 12:56:15 回复(14)
对于第n个台阶来说,只能从n-1或者n-2的台阶跳上来,所以
F(n) = F(n-1) + F(n-2)
斐波拉契数序列,初始条件
n=1:只能一种方法
n=2:两种
递归一下就好了
class Solution {
public:
    int jumpFloor(int number) {
        if(number <= 0)
            return 0;
        else if(number == 1)
            return 1;
        else if(number == 2)
            return 2;
        else
            return jumpFloor(number-1) + jumpFloor(number-2);
    }
};

发表于 2015-09-05 01:20:50 回复(17)
1.假设当有n个台阶时假设有f(n)种走法。
2.青蛙最后一步要么跨1个台阶要么跨2个台阶。
3.当最后一步跨1个台阶时即之前有n-1个台阶,根据1的假设即n-1个台阶有f(n-1)种走法。
4. 当最后一步跨2个台阶时即之前有n-2个台阶,根据1的假设即n-2个台阶有f(n-2 )种走法。
5.显然n个台阶的走法等于前两种情况的走法之和即f(n)=f(n-1)+f(n-2)。
6.找出递推公式后要找公式出口,即当n为1、2时的情况,显然n=1时f(1)等于1,f(2)等于2
7.        | 1, (n=1)

f(n) =  |2, (n=2)

           | f(n-1)+f(n-2) ,(n>2,n为整数)
编辑于 2016-05-12 19:27:11 回复(12)
问题描述:青蛙可跳1-2级台阶,现在需要跳n个台阶,共有多少中跳法

问题解析:设共跳x个1级台阶,y个2级台阶,可推出x+2y=n => x=n-2y,最终问题为对n-2y个一级台阶与y个2级台阶排列组合,即C(n-y,y)。y的范围:y>=0&&y<=(n/2) x的范围:x>=0&&x<=0。

代码:
//step.c
#include <stdio.h> 
//从m中取n个进行排列组合 

int com(int m,int n)

 
    int i = m;  
    int j; 

    int sum=1; 

    for(j = 0;j < n;j++,i--){ 

        sum = sum *i / (j+1); 

    } 

    return sum;

  

int step(int n)

    int two; /*跳两级台阶的次数*/ 

    int count = 0; 

    for(two = 0;two<= (n/2);two ++){ 

        count += com(n-two,two);

    } 

    return count;

  

void main(void)

{  

    int n,ret;

    printf("please input the value of n:\n");

    scanf("%d",&n);

    ret = step(n);

    printf("The way of dance steps are %d\n",ret);


编辑于 2015-05-15 17:35:34 回复(11)
总之就是用迭代不用递归就好
class Solution {
public:
    int jumpFloor(int number) {
        if(number==1||number==2)
        {return number;}
        
        int jumpFib=0;
        int NumberMinusOne=2;
        int NumberMinusTwo=1;
        for(int i=3;i<=number;i++){
            jumpFib = NumberMinusOne+NumberMinusTwo;
            NumberMinusTwo = NumberMinusOne;
            NumberMinusOne = jumpFib;
            
        }
            return jumpFib;
            
        
        
    }
};

发表于 2016-03-18 00:54:55 回复(5)
可以用动态规划来求解该题
跳到第n个台阶,只有两种可能
  1. 从第n-1个台阶跳1个台阶
  2. 从第n-2个台阶跳2个台阶
只需求出跳到第n-1个台阶和第n-2个台阶的可能跳法即可
F(n):n个台阶的跳法
递推公式:F(n)=F(n-1)+F(n-2)
不难发现这是一个斐波那契数列
起始条件为F(0)=1,F(1)=1
解法一:自底向上,使用迭代
public class Solution {
    public int JumpFloor(int target) {
        if(target==0)
            return 1;
        if(target==1)
			return 1;
		int si_1=1;
		int si_2=1;
		int result=0;
		for(int i=2;i<=target;i++){
			result=si_1+si_2;
			si_2=si_1;
			si_1=result;
		}
		return result;
    }
}
解法二:自顶向下,使用递归
public class Solution {
    public int JumpFloor(int target) {
	if(target==1)
            return 1;
        else if(target==2)
            return 2;
        return JumpFloor(target-1)+JumpFloor(target-2);
    }
}

发表于 2017-01-12 20:22:04 回复(0)
class Solution {
public:
    int jumpFloor(int number) {
        int t1=1,t2=2,total=0;
        if (number==1||number==2) return number;
        for(int i=3;i<=number;i++) {
            total=t1+t2;
            t1=t2;
            t2=total;
        }
        return total;
    }
};

发表于 2016-08-01 18:34:24 回复(4)
令f(n)表示从任意位置向上跳n个台阶的跳法个数,当从第一个台阶向上跳时,可以先跳一个,也可以先跳两个:跳一个时,则后续跳法为f(n-1)个;跳两个时,后续跳法为f(n-2),
故f(n)=f(n-1)+f(n-2)

可以进行扩展,若一次可以跳1至n个台阶,则f(n)=f(n-1)+f(n-2)+...f(1)
推导可得:f(n-1)=f(n-2)+(n-3)+...f(1) 即f(n)=2*f(n-1)

发表于 2015-07-06 21:07:43 回复(5)
/*
这一题就是延续上一题的斐波那契数列的思路,青蛙跳1级台阶有1种跳法,2级台阶有2种跳法
3级台阶时可以从1级台阶跳上来也可以从2级台阶跳上来,即等于1级台阶的跳法加2级台阶的跳法
因此n级台阶共有n-2级台阶跳法数+n-1级台阶跳法数;这不就变成了上一道题目么,只是初始数字变了
n=1,sum=1,n=2,sum=2,n=3,sum=3;
*/
public class Solution {
    public int JumpFloor(int target) {
		if(target<=0){
            return 0;
        }
        int fn1=1,fn2=2,sum=0;
        if(target<=2){
            if(target==1){
                return fn1;
            }else{
                return fn2;
            }
        }
        while(target>2){
            sum =fn1+fn2;
            fn1=fn2;
            fn2=sum;
            target--;
        }
        return sum;
    }
}
运行时间:35ms
占用内存:654k

发表于 2017-06-07 14:19:50 回复(0)
/**
*1.假设当有n个台阶时假设有f(n)种走法。
*2.青蛙最后一步要么跨1个台阶要么跨2个台阶。
*3.当最后一步跨1个台阶时即之前有n-1个台阶,根据1的假设即n-1个台阶有f(n-1)种走法。
*4. 当最后一步跨2个台阶时即之前有n-2个台阶,根据1的假设即n-2个台阶有f(n-2 )种走法。
*5.显然n个台阶的走法等于前两种情况的走法之和即f(n)=f(n-1)+f(n-2)。
*6.找出递推公式后要找公式出口,即当n为1、2时的情况,显然n=1时f(1)等于1,f(2)等于2
*7.          1, (n=1)
*f(n) =    2, (n=2)
*             f(n-1)+f(n-2) ,(n>2,n为整数)
*/


public class Solution {
    public int JumpFloor(int target) {
int fn1 = 1;
        int fn2 = 2;
        
        if(target <= 0) {
            return 0;
        }
        if(target == 1) {
            return fn1;
        }
        if(target == 2) {
            return fn2;
        }
        
        while(target>2) {
            fn2 += fn1;
            fn1 = fn2-fn1;
            target--;
        }
        return fn2;
    }
}
发表于 2016-08-10 17:35:55 回复(0)
class Solution {//动态规划
public:
    int jumpFloor(int number) {
        int res1 =1,res2 = 1;
        while(number--){
            res2+=res1;
            res1 =res2 - res1;
        }
        return res1;
    }
};
编辑于 2016-03-12 10:39:01 回复(1)
public class Solution {
    public int JumpFloor(int target) {
        int[] sum = new int[100];
        int a = 1;
        int b = 0;
        if(target == 1){
            return 1;
        }
        if(target == 2){
            return 2;
        }
        while(target >= 0){
            b = a + b;
            a = b - a;
            target -= 1;
        }
        return b;
    }
}
使用了动态规划
发表于 2018-08-03 11:31:21 回复(0)
public class Solution {
    public int JumpFloor(int target) {
        if(target==1)
            return 1;
        if(target==2)
            return 2;
        return JumpFloor(target-1)+JumpFloor(target-2);

    }
}
对于N级台阶,可以从N-1级和N-2级上来,所以JumpFloor(N) =  JumpFloor(N-1)+ JumpFloor(N-2)
N=1时,只有一种
N=2时,有两种:一次2级;两次1级
发表于 2016-11-23 11:47:38 回复(0)
public class Solution {
    public int JumpFloor(int target) {
        int result = 0;
        if(target > 0){
        if(target<=2)
            return target;
        else
            return result=JumpFloor(target-1)+JumpFloor(target-2);
     }
     return result;
     }
}
编辑于 2015-05-13 15:05:43 回复(4)
public class Solution {
    public int JumpFloor(int target) {
        if(target == 1)
            return 1;
        if(target == 2)
            return 2;
        int fibOne = 1;
        int fibTwo = 2;
        int fibN = 0;
        for(int i = 2; i < target ; i++){
            fibN = fibOne + fibTwo;
            fibOne = fibTwo;
            fibTwo = fibN;
        }
        return fibN;
        /*
        if(target == 1)
            return 1;
        if(target == 2)
            return 2;
        return JumpFloor(target-1)+JumpFloor(target - 2);
        */
    }
}
有两种解题方法:
一种是常规递归解法,时间复杂度太过于昂贵,如注释里面就是常规方法;
所以我们用的非递归方法,也就是方法二
具体思路请看斐波拉切数列的思路。
编辑于 2018-05-17 17:55:52 回复(0)
//递归方法 
   int jumpFloor(int number) 
    {   
       if(number<=2)
           return number;
       else
           return jumpFloor(number-1)+jumpFloor(number-2);
    }

//斐波那契方法
   int jumpFloor(int number) 
    {   
       int f1=1,f2=2;
       while(number>2)
       {
           f1=f1+f2;
           f2=f1+f2;
           number-=2;
       }
       return number==1?f1:f2;       
    }

//排列组合方法    
    int jumpFloor(int number) 
    {
        int kinds=0;
        //all 1 step
        ++kinds;
        //2 steps for 1:number/2
        int steps2=1;
        long long temp=1;
        while(2*steps2 <= number)
        {
            int bits= number-steps2;
            temp*=steps2;
            long long  sum=1;
            for(int i=0;i<steps2;i++)
                sum*= (bits-i);
            kinds+=sum/temp;    
            ++steps2;      
        }
        return kinds;        
    }
};
欢迎指正
编辑于 2018-04-16 17:37:19 回复(0)
很典型的采用分治法的思想来解决的问题
首先当问题规模很小时,即number=1和2时,分别对应1和2种跳台阶的方法;
当number>2时要考虑第一个台阶,如果跳1则还要考虑number-1的跳法有多少种,如果跳2则还要考虑number-2的跳法有多少种;
得到公式
                                        
                                       
程序设计时第一步先解决小规模问题,如问题规模较大,则将问题分解为小规模问题,再将小规模问题解合并,采用递归的方法,可能复杂度会比较高,因为各个子问题并不是独立的。
class Solution {
public:
    int jumpFloor(int number) {
        int n;
        if(number==0)
            return -1;
        if(number==1)
            return 1;
        if(number==2)
            return 2;
        if(number>2)
            n=jumpFloor(number-1)+jumpFloor(number-2);
        return n;
    }
};

发表于 2018-04-07 21:21:42 回复(0)
实际上本题最终结果就是一个斐波那契数列,这个前面很多都提到了,我就不再说。
主要分享一下自己的解题思路,开始步骤就是暴力穷举想找规律,以为是N!,但是很快证明不是,于是在纸上画图
很明显是一个二叉树,虽然不平衡,我在画完左半边之后发现,左边的4的子树其实是5的一个子集,5的为0的链接应该是4+3,这是一个典型的斐波那契情况。。一下就破题了,不过那个变态跳台阶的目前还没有想出来。。
发表于 2017-12-06 17:22:50 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号