美文网首页
1. n级台阶问题

1. n级台阶问题

作者: 月巴月巴 | 来源:发表于2018-06-03 17:19 被阅读0次

Q:n级台阶,每次只能上一级,或者两级。那么到第n级台阶一共有多少种走法。

思路:到第n级台阶的最后一步只有两种情况
1. 从第n-1级上去
2. 从第n-2级上去
也就是说,到第n级台阶走法可以当做从1到第n-1级的所有可能,加上从1到第n-2级的所有可
能。也就是 f(n) = f(n-1) + f(n-2)
同时可知初始条件 f(2) = 1; f(3) = 2

由这个思路,我们可以很自然地得出这样的代码

public static int f(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return f(n - 1) + f(n - 2);
 }

这个解法看起来没什么问题,但是如果真的运行起来,很容易就会出现递归层数过多导致的StackOverflowError.所以这个解法并不能真的用来做计算。

如果不用递归,可以这样写 (参照SICP)

public static int f2(int n) {
        int a = 0;
        int b = 0;
        for (int i = 0; i <= n; i++) {
            if (i == 0) {
                a = 0;
                continue;
            }
            if (i == 1) {
                a = 1;
                b = 0;
                continue;
            }
            a = a + b;
            b = a - b;
        }
        return a;
    }

简单的测试:

public static void main(String[] args) {
    for(int i=0; i<=5; i++) {
        System.out.println(i + " steps : " + f2(i) + " ways");
    }
 }
/*
Test Results: 
0 steps : 0 ways
1 steps : 1 ways
2 steps : 1 ways
3 steps : 2 ways
4 steps : 3 ways
5 steps : 5 ways
*/

相关文章

  • 1. n级台阶问题

    Q:n级台阶,每次只能上一级,或者两级。那么到第n级台阶一共有多少种走法。 思路:到第n级台阶的最后一步只有两种情...

  • 跳台阶

    问题描述:?一次可以跳1级台阶,也可以跳2级台阶,问?跳上n级台阶有多少种跳法。 寻找递推关系:1.如果第一次跳1...

  • 动态规划

    青蛙跳台阶问题 问题:一个青蛙,一次只能跳一级台阶,或者跳两级台阶,这个青蛙跳 n 级台阶有多少种跳法? 如果这只...

  • 常用的几种简单算法

    1. 台阶问题/斐波那契(伪) 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少...

  • 青蛙跳台阶-递归思想解算

    问题:一只青蛙一次可以跳上一级台阶,也可以跳上两级台阶。求该青蛙跳上n级台阶总共有多少种跳法? 思路:要跳上 第n...

  • 跳台阶(JumpFloor)

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

  • 疯狂跳台阶

    ?一次可以选择跳1、2...n级台阶,问跳到n级台阶有多少种跳法 设F(n-i)表示第一次跳i(i

  • python编程题

    1、台阶问题、斐波那契 一只青蛙可以跳上一级台阶,也可以跳上两级台阶,求青蛙跳上一个n级台阶共有多少种跳法 方法一...

  • 剑指offer习题---跳台阶

    一只?一次可以跳上1级台阶,也可以跳上2级。求该?跳上一个n级台阶总共有多少种跳法 对于N级台阶,可以从N-1 和...

  • 算法---青蛙跳台阶问题

    一只青蛙可以一次跳一级台阶,也可以一次跳两级台阶,如果青蛙要跳上n级台阶,共有多少钟跳法? 问题分析 当青蛙即将跳...

网友评论

      本文标题:1. n级台阶问题

      本文链接:https://www.haomeiwen.com/subject/tnvjsftx.html