【华为机试】猴子爬山问题

题目描述：

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

输入描述

输入只有一个这个数n 0 < n < 50 此阶梯有多个台阶

输出描述

有多少种跳跃方式

示例1

输入
50
输出
122106097

示例2

输入
3
输出
2

代码

import java.util.Scanner;
public class OneStar_04 {
          
   
    public static void main(String[] args) {
          
   
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入阶梯的台阶数：");
        int n = scanner.nextInt();
        solution(n);
        // System.out.println(fun(n));
    }

    //使用循环实现，共执行n-2次循环
    private static void solution(int n) {
          
   
        int step1 = 1 , step2 = 1 , step3=2;
        //step4 用来存储最后的跳跃方式数量。
        //由于当n为1或2时只有一种跳跃方式，n大于1或2时有2种及以上的跳跃方式
        int step4 = n == 1 || n == 2 ? 1 : 2;
        //当n=3时，必定有2种跳跃方式
        //当n>3时，有大于2种跳跃方式

        /**
         * n = 1 s1 = 1
         * n = 2 s2 = 1
         * n = 3 s3 = 2
         * n = 4 s4 = 1 + 2
         * n = 5 s4 = 1 + 3
         * n = 6 s4 = 2 + 4
         * n = 7 s4 = 3 + 6
         * 
         */
        for(int i = 4 ; i <= n ; i++){
          
   
            step4 = step1 + step3;
            //观察每一种台阶数下的跳跃方式总数
            //System.out.println(step4);
            step1 = step2;
            step2 = step3;
            step3 = step4;
        }

        System.out.println(step4);
    }

    //使用递归实现，同理斐波那契数列（112358...）
    private static int fun(int n) {
          
   
        if (n == 1 || n == 2) {
          
   
            return 1;
        }
        if (n == 3) {
          
   
            return 2;
        }
        int sum = 0;
        if (n > 3) {
          
   
            sum = fun(n - 1) + fun(n - 3);
        }
        return sum;
    }

    
}