首页 > 试题广场 > 变态跳台阶
[编程题]变态跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1449个回答

添加回答
推荐

关于本题,前提是n个台阶会有一次n阶的跳法。分析如下:

f(1) = 1

f(2) = f(2-1) + f(2-2)         //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3) 

...

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

 

说明: 

1)这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。

2)n = 1时,只有1种跳法,f(1) = 1

3) n = 2时,会有两个跳得方式,一次1阶或者2阶,这回归到了问题(1) ,f(2) = f(2-1) + f(2-2) 

4) n = 3时,会有三种跳得方式,1阶、2阶、3阶,

    那么就是第一次跳出1阶后面剩下:f(3-1);第一次跳出2阶,剩下f(3-2);第一次3阶,那么剩下f(3-3)

    因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

5) n = n时,会有n中跳的方式,1阶、2阶...n阶,得出结论:

    f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)

    

6) 由以上已经是一种结论,但是为了简单,我们可以继续简化:

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

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

    可以得出:

    f(n) = 2*f(n-1)

    

7) 得出最终结论,在n阶台阶,一次有1、2、...n阶的跳的方式时,总得跳法为:

              | 1       ,(n=0 ) 

f(n) =     | 1       ,(n=1 )

              | 2*f(n-1),(n>=2)
public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else {
            return 2 * JumpFloorII(target - 1);
        }
    }
}

编辑于 2015-06-17 21:30:40 回复(149)
class Solution {
public:
    int jumpFloorII(int number) {
                int a=1; return a<<(number-1);
    }
};
2^(n-1)可以用位移操作进行,更快。
发表于 2015-08-16 00:29:46 回复(18)
因为n级台阶,第一步有n种跳法:跳1级、跳2级、到跳n级
跳1级,剩下n-1级,则剩下跳法是f(n-1)
跳2级,剩下n-2级,则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)
编辑于 2018-03-28 20:41:06 回复(36)
//头像 //

每个台阶都有跳与不跳两种情况(除了最后一个台阶),最后一个台阶必须跳。所以共用2^(n-1)中情况

发表于 2015-06-03 22:36:45 回复(89)
HXY头像 HXY
一行代码 return  1<<--number;
编辑于 2015-04-25 20:40:41 回复(120)
【分析】 每个台阶可以看作一块木板,让青蛙跳上去,n个台阶就有n块木板,最后一块木板是青蛙到达的位子, 必须存在,其他 (n-1) 块木板可以任意选择是否存在,则每个木板有存在和不存在两种选择,(n-1) 块木板 就有 [2^(n-1)] 种跳法,可以直接得到结果。

其实我们所要求的序列为:0,1,2,4,8,16,……
所以除了第一位外,其他位的数都是前一位的数去乘以2所得到的积。

【参考代码】
package javaTest;

import java.util.Scanner;


public class JavaTest {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int target = input.nextInt();
		System.out.println("跳上一个" + target + "级的台阶总共有"
				+ jumpFloor(target) + "种跳法");
	}
	// 第一种做法
	public static int jumpFloor(int target) {
		if (target <= 0) return 0;
		return (int) Math.pow(2, target - 1);
	}
//       第二种做法
//	public static int jumpFloor(int target) {
//		if (target <= 0) return 0;
//		if (target == 1) return 1;
//		int a = 1;
//		int b = 2;
//		for (int i = 2; i <= target; i++) {
//			b = 2 * a;
//			a = b;
//		}
//		return b;
//	}
}

发表于 2016-10-08 22:30:44 回复(3)

python solution:

return 2**(number-1)
发表于 2017-10-14 13:24:19 回复(10)
        根据上一个题目:青蛙只跳1或2可以得出是一个斐波那契问题,即a[n]=a[n-1]+a[n-2],那么能跳1,2,3个台阶时a[n]=a[n-1]+a[n-2]+a[n-3],......
        依次类推,能推出本题的a[n]=a[n-1]+a[n-2]+......+a[1];由此得出代码:
class Solution {
public:
    int jumpFloorII(int number) {
        int *a=new int[number+1];
        a[0]=1;
        a[1]=1;
        for(int i=2;i<=number;i++){
            a[i]=0;
            for(int j=i-1;j>=0;j--){
                a[i]+=a[j];
            }
        }
        return a[number];
    }
};
但是上述代码时间复杂度达到O(n^2),空间复杂度也达到O(n),重新看一下上述结论:
a[n]=a[n-1]+a[n-2]+......+a[1];..........................①
a[n-1]=        a[n-2]+......+a[1];..........................②
两式相减可知:a[n]=2*a[n-1];
所以代码进一步简化:
class Solution {
public:
    int jumpFloorII(int number) {
        int f=1,fn=1;
        for(int i=2;i<=number;i++){
            fn=2*f;
            f=fn;
        }
        return fn;
    }
};

编辑于 2016-06-13 13:14:06 回复(10)
拒绝时间开销,拒绝递归调用
class Solution {
public:
    int jumpFloorII(int number) {
    	int jumpFlo=1;
        while(--number)
        {
            jumpFlo*=2;
        }
        return jumpFlo;
    }
};

编辑于 2016-07-19 17:14:58 回复(8)

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

(2)总跳法为: f(n) = 1+f(n-1) + f(n-2)+....+f(1)  (第一个1是跳n阶只有一种方法)

(3)根据(2)可以得出有一阶的时候 f(1) = 1 ;有两阶的时候可以有 f(2) = 1+f(1)=2;有三阶的时候可以有 f(3) = 1+f(2)+f(1)=4...依次内推,有n阶时f(n)=2^(n-1)。

为了加快运算速度,可以通过向左移移位来完成乘以2的工作:
class Solution{
public:
    int jumpFloorII(int number) {
        //通过移位计算2的次方
        return 1<<(number-1);        
    }
};

编辑于 2016-09-05 11:40:55 回复(3)
直接看图就知道:
发表于 2015-05-11 14:59:02 回复(10)
其实是隔板问题,假设n个台阶,有n-1个空隙,可以用0~n-1个隔板分割,c(n-1,0)+c(n-1,1)+...+c(n-1,n-1)=2^(n-1),其中c表示组合。
有人用移位1<<--number,这是最快的。直接连续乘以2不会慢多少,编译器会自动优化。不过移位还是最有启发的!
发表于 2015-09-05 21:31:40 回复(4)
public class Solution {
    public int JumpFloorII(int target) {
        if(target<=0)
            return 0;
        return 1<<(target-1);
    }
}

发表于 2016-04-18 14:03:46 回复(0)
假设有n级的台阶,其实就是找组合数,将n分成n个0或者1(1,1,0,0,0,1)第一个必须是1,其中1表示未被前面步数包含,0表示被前面步数包含,比如如果是4步,(1,1,1,1)表示一次跳一步,(1,0,0,1)表示3,1(1,1,0,1)表示1,2,1所以组合应该为2的n-1次方
发表于 2015-10-10 13:20:41 回复(1)
数学问题, n个台阶最多有n-1个分段,  每个分段可以跳也可以不跳,所以有2的n-1次方
class Solution {
public:
    int jumpFloorII(int number) {
        return pow(2,number-1);
    }
};
编辑于 2017-08-14 17:35:02 回复(0)
class Solution {
public:
    int jumpFloorII(int number) {
/*        //第一种
        long int sum=0;
        if(number==0) return 1;
        else if(number==1) return 1;
        else if(number==2) return 2;
        else
        {
               for(int i=number-1; i>=0; i--)
                   sum += jumpFloorII(i);
        }
        
        return sum;
        */
        //第二种做法
        return pow(2, number-1);
    }
};
发表于 2015-10-09 16:36:30 回复(0)
这不是一个编程逻辑题,其实就是一个数学归纳法罢了!最后可以推出这是一个首项是1,公比为2的等比数列!
public int jumpFloorPlus(int target) {
    if(target == 0)
      return 0;
    if(target == 1)
      return 1;
    return 2*jumpFloorPlus(target-1);
  }


发表于 2017-12-27 21:22:46 回复(0)
class Solution {
public:
    int jumpFloorII(int number) {
			return pow(2,number-1);
    }
};

发表于 2016-11-18 20:08:04 回复(0)
public class Solution {
    public int JumpFloorII(int target) {
        int sum = 1;
        while(target > 1){
            sum *= 2;
            target--;
        }
        return sum;
    }
}
或者是使用位运算
发表于 2018-08-03 11:55:29 回复(0)
class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<(number-1);
    }
};
发表于 2017-10-20 22:57:26 回复(0)
public class Solution {
    public int JumpFloorII(int target) {
        // 假设:f(n)表示:n个台阶第一次1,2,...n阶的跳法数;
        // 若第一次跳了1阶,则还剩n-1阶,
        // 假设:f(n-1)表示:n-1个台阶第一次1,2,...n-1阶的跳法数;
        // 若第一次跳了2阶,则还剩n-2阶,
        // 假设:f(n-2)表示:n-1个台阶第一次1,2,...n-2阶的跳法数;
        // ...
        // 把所以可能的情况(第一次可能跳1,2,...,n阶)加起来:
        // 可以求出:f(n) = f(n-1) + f(n-2) + ... + f(1)
        // 递归:f(n-1) = f(n-2) + ... + f(1)
        // 可以求出:f(n) = 2*f(n-1) 
        
        /*
        if (target <= 0) {
            return 0;
        } else if (target == 1) {
            return 1;
        } else {
            return 2 * JumpFloorII(target - 1);
        }
        */ 
        // 更实用的解法是:从下往上计算,避免了递归的多余计算量
        int a = 1, b = 0;
        if (target <= 0) {
            return 0;
        } else if (target == 1) {
            return 1;
        } else {
            for (int i = 2; i <= target; i++) {
                b = 2 * a;
                a = b;
            }
            return b;
        }
    }
}

编辑于 2017-03-14 01:31:46 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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

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