首页 > 资讯 > 后端开发 > 其他教程 >【华为OD机试真题】46、猴子爬山 | 机试真题+思路参考+代码解析（C语言、C++、Java、Py、JS）

444

分享到

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

华为od c语言 c++华为OD机试真题 python java 猴子爬山 2023-08-17 09:08:25 444人浏览薄情痞子

摘要

文章目录一、题目🎃题目描述🎃输入输出🎃样例1🎃样例2 二、代码与思路参考🎈C语言思路🎉C代码 🎈C++语

文章目录

作者：KJ.JK

🍂个人博客首页： KJ.JK

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

一、题目

🎃题目描述

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

🎃输入输出

输入
输入只有一个整数N (0
输出
输出有多少种跳跃方式(解决方案数)。

🎃样例1

输入50输出122106097

🎃样例2

输入3输出2

二、代码与思路参考

🎈C语言思路

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

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

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

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

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

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

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

🎉C代码

#include 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++语言思路

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

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

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

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

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

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

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

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

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

输出结果

🎉C++代码

#include #include using namespace std;int countJumpWays(int n) {    if (n == 0 || n == 1) {        return 1;    } else if (n == 2) {        return 1;    }    // 创建一个长度为n+1的向量来保存跳跃方式数，初始值都为0    vector 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语言思路

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

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

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

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

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

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

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

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

读取输入的阶梯台阶数

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

输出结果

🎉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步或者跳3步。因此，到达第i个阶梯的跳跃方式数只与到达第i-1个阶梯和第i-3个阶梯的跳跃方式数有关。

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

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

最后，返回 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个台阶的跳跃方式数。

🎉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();  });