N阶台阶,每次走一步或两步,计算共有多少种走法,打印出每种走法。

 

一 走台阶算法(本质上是斐波那契数列)在面试中常会遇到,描述就如题目那样:总共100级台阶(任意级都行),小明每次可选择走1步、2步或者3步,问走完这100级台阶总共有多少种走法?

一、 题目分析

这个问题本质上是斐波那契数列,假设只有一个台阶,那么只有一种跳法,那就是一次跳一级,f(1)=1;如果有两个台阶,那么有两种跳法,第一种跳法是一次跳一级,第二种跳法是一次跳两级,f(2)=2。如果有大于2级的n级台阶,那么假如第一次跳一级台阶,剩下还有n-1级台阶,有f(n-1)种跳法,假如第一次条2级台阶,剩下n-2级台阶,有f(n-2)种跳法。这就表示f(n)=f(n-1)+f(n-2)。将上面的斐波那契数列代码稍微改一下就是本题的答案。我们来看一下代码的实现。
 

二、斐波那契数列法

public class Test {
    static final int s = 100; //自定义的台阶数

    static int compute(int stair){
        if ( stair <= 0){
            return 0;
        }
        if (stair == 1){
            return 1;
        }
        if (stair == 2){
            return 2;
        }
        return compute(stair-1) + compute(stair-2);
    }

    public static void main(String args[]) {
        System.out.println("共有" + compute(s) + "种走法");
    }
}

 

三、 走台阶问题的简单解决算法

但我自己对于这个题目最早的想法是使用树(多叉树)的方式,100为根节点,每次选择的分支有两种(1、2),然后生成深度为1的树,再从每个2级节点延伸出1、2两个分支,直到所有节点的值<=0,最后统计出所有值为0的叶子节点的数目,就是结果。

不过自己想法实际上把问题复杂化了,下面这种使用递归方式实现的算法本质上和我的思想差不多,但是很明显下面这个算***简单很多。接下来我们来看看这个算法的实现方式。


其实这个就是回溯法 深度优先搜索

/**
 * @Auther: liuhaidong
 * Data: 2020/4/26 0026、14:50
 * Description:
 * @version: 1.0
 */
public class Test7 {
    static final int s = 4;
    //自定义的台阶数
    static int len = 0, sum = 0;
    //最多也只有走100步就到了
    static int step[] = new int[s];
    static void compute(final int stair) {
        if (stair < 0){
            return;
        }
        //表示已经走完了
        if (stair == 0) {
            printSum();
            sum++;
            return;
        }
        //每次到下一步选择时都可以走1-2步
        for (int i = 1; i <= 2; i++) {
            step[len] = i;
            len++;
            //进行下一步的迭代,迭代完之后将每后加上的一步去掉,换成其它的步数(如从1换成2)
            compute(stair - i);
            len--;
        }
    }
    static void printSum() {
        System.out.print("走法:");
        for (int i = 0; i < len; i++) {
            System.out.print(step[i] + " ");
        }
        System.out.println();
    }
    public static void main(String args[]) {
        compute(s);
        System.out.println("共有" + sum + "种走法");
    }
}