Java 华为真题-猴子爬山

需求：

  一天一只顽猴想去从山脚爬到山顶，途中经过一个有个N个台阶的阶梯，但是这猴子有一个习惯：每一次只能跳1步或跳3步，试问猴子通过这个阶梯有多少种不同的跳跃方式？

输入描述

        输入只有一个整数N（0<N<=50）此阶梯有多少个台阶。

输出描述

        输出有多少种跳跃方式（解决方案数）。

 

输入

3

输出

2

 

输入

50

输出

122106097

分析:

上山最后一步到达第50级台阶，完成上山，共有f（50）种不同的爬法，

到第50级之前位于哪一级呢？无非是位于第49级（上跳1级即到），有f（49）种；

或位于第48级（上跳3级即到），有f（48）种，于是：

f（50）=f（49）+f（47）
f（49）= f（48）+f（46）
f（48）= f（47）+f（45）
依次类推
以此类推，一般地有递推关系：

f（n）=f（n-1）+f（n-3） （n>3）
初始条件：

f（1）=1，即1=1；

f（2）=1，即2=1+1（注意：跳法中不允许直接跳2级）；

f（3）=2，即3=1+1+1，3=3；

故此递推设计比较简单，时间复杂度为O（n）

编码：

public class TestDump {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.print("请输入阶梯数：");
        int num=scanner.nextInt();
        System.out.println(showF(num));
    }

    /**
     * 递归算法f(n) = f(n-1) + f(n-3);
     * f(1) =1;f(2) =1;f(3) = 2
     */
    public static long showF(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        return showF(n - 1) + showF(n - 3);
    }
}

效果：