变态跳台阶(思路和实现)

KLQ 2020-05-12 10:31:04 java常见问答 5779

下面要给大家分享的实例是和变态跳台阶相关的内容,一起详细的来看看相关题目,和解决思路代码实现吧!

题目:

一只清完,一次可以跳上1级台阶,也可以跳上2级台阶,它也可以跳上n级台阶。

求:

这个青蛙跳上一个n级的台阶一共有几种跳法。

思路1:

每一个台阶我们可以看做是一块木板,让青蛙跳上去,n个台阶的话,就有n块木板,最后一块木板是青蛙到达的位置, 这是必须存在的。

其他(n-1)块木板可以任意选择是否存在,那么,每块木板有存在和不存在两种选择,(n-1)块木板就有[2^(n-1)]种跳法,最后,可以直接得到结果。

序列:0,1,2,4,8,16,……

所以,除去第一位之外,其他位的数都是前面一位的数去乘以二所得到的积。

代码实现:

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;
    //	}
}

思路2:

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的时候,会有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);
        }
    }
}

思路3:

2^(n-1)可以用位移操作进行。

代码实现:

class Solution {
public:
    int jumpFloorII(int number) {
                int a=1; return a<<(number-1);
    }
};

以上的几种思路和代码实现仅供参考。

假如你还想了解更多的实例,请继续关注奇Q工具网的java实例栏目了解吧!

推荐阅读:

矩形覆盖(思路和实现)

二进制中1的个数(思路和实现)

求数值的整数次方(思路和实现)