【华为OD机试真题】46、 猴子爬山 | 机试真题+思路参考+代码解析（C语言、C++、Java、Py、JS）

🍂个人博客首页： KJ.JK
 
🍂专栏介绍： 华为OD机试真题汇总，定期更新华为OD各个时间阶段的机试真题，每日定时更新，本专栏将使用C语言、C++、Java、Python、JS语言进行更新解答，包含真题，思路分析，代码参考，欢迎大家订阅学习

一、题目

🎃题目描述

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

🎃输入输出

输入
输入只有一个整数N (0<N<=50) 此阶梯有多少个台阶。
 
输出
输出有多少种跳跃方式(解决方案数)。

🎃样例1

输入
50

输出
122106097

🎃样例2

输入
3

输出
2

二、代码与思路参考

🎈C语言思路

1、首先我们定义一个函数 jumpWaysCount，它接受一个整数参数 n，表示台阶的数量，并返回通过这些台阶的不同跳跃方式数量。

2、我们观察到最后一步可以是跳 1 步到达第 n 个台阶，或者是跳 3 步到达第 n 个台阶。因此，不同的跳跃方式数量等于通过跳 1 步到达第 n 个台阶的方式数量加上通过跳 3 步到达第 n 个台阶的方式数量。

3、为了解决这个问题，我们使用一个动态规划数组 dp，其中 dp[i] 表示通过 i 个台阶的不同跳跃方式数量。

4、我们需要初始化一些特殊情况：当 n 为 1 时，只有一种跳跃方式；当 n 为 2 时，只有一种跳跃方式；当 n 为 3 时，有两种跳跃方式。

5、接下来，我们使用循环从 4 开始遍历到 n，并使用状态转移方程 dp[i] = dp[i - 1] + dp[i - 3] 计算不同台阶数量的跳跃方式数量。

6、最后，我们返回 dp[n]，即通过 n 个台阶的不同跳跃方式数量

在主函数中，我们提示用户输入台阶数，并调用 jumpWaysCount 函数来计算跳跃方式数量，并将结果输出到屏幕上。

🎉C代码

#include <stdio.h>

int jumpWaysCount(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 1;
    }
    if (n == 3) {
        return 2;
    }
    int dp[n + 1];  // 创建动态规划数组，用于存储跳跃方式数量
    dp[1] = 1;  // 初始化状态：1个台阶只有1种跳跃方式
    dp[2] = 1;  // 初始化状态：2个台阶只有1种跳跃方式
    dp[3] = 2;  // 初始化状态：3个台阶有2种跳跃方式
    for (int i = 4; i <= n; i++) {  // 从4个台阶开始计算跳跃方式数量
        dp[i] = dp[i - 1] + dp[i - 3];  // 使用状态转移方程计算跳跃方式数量
    }
    return dp[n];  // 返回通过n个台阶的不同跳跃方式数量
}

int main() {
    int n;
    printf("Enter the number of steps: ");
    scanf("%d", &n);  // 输入台阶数
    int ways = jumpWaysCount(n);  // 调用函数计算跳跃方式数量
    printf("Number of jump ways: %d\n", ways);  // 输出跳跃方式数量
    return 0;
}

🎈C++语言思路

1、首先，定义一个函数countJumpWays，接收一个参数n，表示阶梯台阶数，返回跳跃方式数

2、判断n的值，如果n为0或1，则返回1，表示只有一种跳跃方式

3、如果n为2，则返回1，表示只有一种跳跃方式

4、创建一个长度为n+1的向量jumpWays来保存每个位置的跳跃方式数，初始值都为0

5、初始化前几个位置的跳跃方式数：初始位置为1，第一步跳1步为1，第一步跳2步为1

6、使用一个循环，从第3个位置开始，计算每个位置的跳跃方式数，通过累加前一个位置和前三个位置的跳跃方式数得到

7、返回jumpWays[n]，即最后一个位置的跳跃方式数

8、在主函数main中，读取输入的阶梯台阶数n

10、调用函数countJumpWays，计算跳跃方式数

11、输出结果

🎉C++代码

#include <iostream>
#include <vector>
using namespace std;

int countJumpWays(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else if (n == 2) {
        return 1;
    }

    // 创建一个长度为n+1的向量来保存跳跃方式数，初始值都为0
    vector<int> jumpWays(n + 1, 0);

    // 初始化前几个位置的跳跃方式数
    jumpWays[0] = 1;  // 初始位置，只有一种方式
    jumpWays[1] = 1;  // 第一步跳1步，只有一种方式
    jumpWays[2] = 1;  // 第一步跳2步，只有一种方式

    // 计算每个位置的跳跃方式数
    for (int i = 3; i <= n; i++) {
        jumpWays[i] = jumpWays[i - 1] + jumpWays[i - 3];
    }

    return jumpWays[n];
}

int main() {
    // 读取输入的阶梯台阶数
    int n;
    cin >> n;

    // 调用函数计算跳跃方式数
    int result = countJumpWays(n);

    // 输出结果
    cout << result << endl;

    return 0;
}

🎈Java语言思路

1、首先判断n的值，如果n为0或1，则只有一种跳跃方式，直接返回1

2、如果n为2，则也只有一种跳跃方式，直接返回1

3、创建一个长度为n+1的数组jumpWays来保存每个位置的跳跃方式数，初始值都为0

4、初始化数组的前几个位置的跳跃方式数：初始位置为1，第一步跳1步为1，第一步跳2步为1

5、从第3个位置开始，通过迭代计算每个位置的跳跃方式数

6、对于每个位置i，跳跃方式数等于前一步位置(i-1)的跳跃方式数加上前三步位置(i-3)的跳跃方式数

7、迭代完成后，跳跃方式数数组jumpWays中的第n个位置即为所求的跳跃方式数

8、返回第n个位置的跳跃方式数作为结果

9、读取输入的阶梯台阶数

10、调用函数countJumpWays计算跳跃方式数

11、输出结果

🎉Java代码

import java.util.Scanner;

public class Main {
    public static int countJumpWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        } else if (n == 2) {
            return 1;
        }

        // 创建一个长度为n+1的数组来保存跳跃方式数，初始值都为0
        int[] jumpWays = new int[n + 1];

        // 初始化前几个位置的跳跃方式数
        jumpWays[0] = 1;  // 初始位置，只有一种方式
        jumpWays[1] = 1;  // 第一步跳1步，只有一种方式
        jumpWays[2] = 1;  // 第一步跳2步，只有一种方式

        // 计算每个位置的跳跃方式数
        for (int i = 3; i <= n; i++) {
            jumpWays[i] = jumpWays[i - 1] + jumpWays[i - 3];
        }

        return jumpWays[n];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取输入的阶梯台阶数
        scanner.close();

        int result = countJumpWays(n); // 调用函数计算跳跃方式数
        System.out.println(result); // 输出结果
    }
}

🎈Python语言思路

1、对于跳跃阶梯问题，每一步只能跳1步或者跳3步。因此，到达第i个阶梯的跳跃方式数只与到达第i-1个阶梯和第i-3个阶梯的跳跃方式数有关。

2、我们可以定义一个长度为n+1的列表 jump_ways，其中 jump_ways[i] 表示到达第i个阶梯的跳跃方式数。初始时，jump_ways[0] 和 jump_ways[1] 都为1，表示初始位置和第一步跳1步的方式数为1。

3、然后，我们可以使用一个循环来计算每个位置的跳跃方式数。从第2个位置开始，对于每个位置i，可以根据题目要求的跳跃方式规则，通过 jump_ways[i - 1] 和 jump_ways[i - 3] 计算出 jump_ways[i]。具体计算方式为 jump_ways[i] = jump_ways[i - 1] + jump_ways[i - 3]。

4、最后，返回 jump_ways[n]，即到达第n个阶梯的跳跃方式数

🎉Python代码

def count_jump_ways(n):
    if n == 0 or n == 1:
        return 1
    elif n == 2:
        return 1

    # 创建一个长度为n+1的列表来保存跳跃方式数，初始值都为0
    jump_ways = [0] * (n + 1)

    # 初始化前几个位置的跳跃方式数
    jump_ways[0] = 1  # 初始位置，只有一种方式
    jump_ways[1] = 1  # 第一步跳1步，只有一种方式
    jump_ways[2] = 1  # 第一步跳2步，只有一种方式

    # 计算每个位置的跳跃方式数
    for i in range(3, n + 1):
        jump_ways[i] = jump_ways[i - 1] + jump_ways[i - 3]

    return jump_ways[n]


# 读取输入的阶梯台阶数
n = int(input())

# 调用函数计算跳跃方式数
result = count_jump_ways(n)

# 输出结果
print(result)

🎈JS语言思路

假设有n个阶梯台阶，我们要计算到达第n个台阶的跳跃方式数。

首先，我们定义一个长度为n+1的数组 jumpWays 来保存每个位置的跳跃方式数。

接着，我们初始化前几个位置的跳跃方式数：

• jumpWays[0] 为初始位置，只有一种方式，所以设置为1。
• jumpWays[1] 为第一步跳1步，只有一种方式，所以设置为1。
• jumpWays[2] 为第一步跳2步，只有一种方式，所以设置为1。

然后，我们从第3个位置开始，计算每个位置的跳跃方式数。对于第i个位置，可以从 i-1 跳1步到达，也可以从 i-3 跳3步到达。所以，第i个位置的跳跃方式数等于第 i-1 个位置的跳跃方式数加上第 i-3 个位置的跳跃方式数。

最后，返回 jumpWays[n] 即可得到到达第n个台阶的跳跃方式数。文章来源地址https://www.toymoban.com/news/detail-646041.html

🎉JS代码

function countJumpWays(n) {
    if (n === 0 || n === 1) {
      return 1;
    } else if (n === 2) {
      return 1;
    }
  
    // 创建一个长度为n+1的数组来保存跳跃方式数，初始值都为0
    const jumpWays = new Array(n + 1).fill(0);
  
    // 初始化前几个位置的跳跃方式数
    jumpWays[0] = 1; // 初始位置，只有一种方式
    jumpWays[1] = 1; // 第一步跳1步，只有一种方式
    jumpWays[2] = 1; // 第一步跳2步，只有一种方式
  
    // 计算每个位置的跳跃方式数
    for (let i = 3; i <= n; i++) {
      jumpWays[i] = jumpWays[i - 1] + jumpWays[i - 3];
    }
  
    return jumpWays[n];
  }
  
  // 读取输入的阶梯台阶数
  const readline = require('readline');
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });
  
  rl.question('请输入阶梯台阶数：', (n) => {
    // 调用函数计算跳跃方式数
    const result = countJumpWays(parseInt(n));
  
    // 输出结果
    console.log(result);
  
    rl.close();
  });
  

作者：KJ.JK

到了这里，关于【华为OD机试真题】46、 猴子爬山 | 机试真题+思路参考+代码解析（C语言、C++、Java、Py、JS）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！