当前位置： 首页 > news >正文

【2024年华为OD机试】(B卷,100分)- 求最小步数 （Java JS PythonC/C++）

news 2025/6/30 6:41:03

在这里插入图片描述

一、问题描述

题目描述

求从坐标零点到坐标点 n 的最小步数，一次只能沿横坐标轴向左或向右移动 2 或 3。

注意：途径的坐标点可以为负数。

输入描述

坐标点 n

输出描述

输出从坐标零点移动到坐标点 n 的最小步数。

备注

1 <= n <= 10^9

用例

用例 1

输入:

4

输出:

2

说明:
从坐标零点移动到 4，最小需要两步，即右移 2，再右移 2。

题目解析

题目要求我们找到将数字 n 分解为若干个 2 和 3 的和，使得分解后的项数最少。通过观察小数量级的例子，我们可以总结出以下规律：

1. 小数量级的规律

从 n = 1 到 n = 16 的分解情况如下：

n分解方式最少步数
1-2 + 32
221
331
42 + 22
53 + 22
63 + 32
73 + 2 + 23
83 + 3 + 23
93 + 3 + 33
103 + 3 + 2 + 24
113 + 3 + 3 + 24
123 + 3 + 3 + 34
133 + 3 + 3 + 2 + 25
143 + 3 + 3 + 3 + 25
153 + 3 + 3 + 3 + 35
163 + 3 + 3 + 3 + 2 + 26

2. 规律总结

从 n >= 4 开始，我们可以总结出以下规律：

  1. 每增加 3，最少步数增加 1：

    • 例如：
      • n = 4 的最少步数是 2。
      • n = 7 的最少步数是 3。
      • n = 10 的最少步数是 4。
    • 这是因为每增加 3，相当于增加一个 3，而 3 的分解步数为 1。

  2. 分解中的 2 和 3 的作用：

    • 如果分解中存在 2，那么 n + 1 可以通过将 2 替换为 3 来实现，此时最少步数保持不变。
      • 例如：
        • n = 4 的分解是 2 + 2，最少步数是 2。
        • n = 5 的分解是 3 + 2，最少步数仍然是 2。
    • 如果分解中不存在 2，那么 n + 1 需要通过将 3 替换为 2 + 2 来实现，此时最少步数增加 1。
      • 例如：
        • n = 6 的分解是 3 + 3，最少步数是 2。
        • n = 7 的分解是 3 + 2 + 2，最少步数增加到 3。

3. 通用规律

对于任意 n >= 4，最少步数可以通过以下方式计算：

  1. 计算 n 除以 3 的商和余数：

    • 设 n = 3 * k + r，其中 k 是商，r 是余数（r = 0, 1, 2）。
    • 如果 r = 0，则最少步数为 k。
    • 如果 r = 1，则最少步数为 k - 1 + 2（将最后一个 3 替换为 2 + 2）。
    • 如果 r = 2，则最少步数为 k + 1。

  2. 特殊情况：

    • 对于 n = 1，需要特殊处理，因为无法直接用 2 和 3 分解。
    • 对于 n = 2 和 n = 3，最少步数分别为 1。

4. 示例验证

示例 1：n = 7
  • 分解方式：3 + 2 + 2。
  • 最少步数：3。
  • 验证：
    • 7 = 3 * 2 + 1，余数 r = 1。
    • 最少步数 = 2 - 1 + 2 = 3。
示例 2：n = 10
  • 分解方式：3 + 3 + 2 + 2。
  • 最少步数：4。
  • 验证：
    • 10 = 3 * 3 + 1，余数 r = 1。
    • 最少步数 = 3 - 1 + 2 = 4。
示例 3：n = 12
  • 分解方式：3 + 3 + 3 + 3。
  • 最少步数：4。
  • 验证：
    • 12 = 3 * 4 + 0，余数 r = 0。
    • 最少步数 = 4。

5. 总结

通过观察小数量级的例子，我们可以总结出以下规律：

  1. 对于 n >= 4，最少步数与 n 除以 3 的商和余数有关。
  2. 如果余数为 0，最少步数为商。
  3. 如果余数为 1，最少步数为商减 1 加 2。
  4. 如果余数为 2，最少步数为商加 1。

这种规律可以帮助我们快速计算任意 n 的最少步数，而无需逐个分解。

如果有其他问题，欢迎随时提问！

二、JavaScript算法源码

以下是 JavaScript 代码 的详细中文注释和逻辑讲解：

代码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");// 创建 readline 接口实例
const rl = readline.createInterface({input: process.stdin,  // 输入流为标准输入output: process.stdout, // 输出流为标准输出
});// 监听输入事件
rl.on("line", (line) => {// 将输入转换为整数并调用 getResult 函数console.log(getResult(parseInt(line)));
});// 计算最少步数的函数
function getResult(n) {// 处理特殊情况if (n == 1) return 2; // n=1 时，最少步数为 2if (n == 2) return 1; // n=2 时，最少步数为 1if (n == 3) return 1; // n=3 时，最少步数为 1// 基础步数let base = 2; // 从 n=4 开始，最少步数为 2// 计算 n >= 4 时的最少步数return Math.floor((n - 4) / 3) + base;
}

代码逻辑讲解

1. 输入处理
  • 使用 readline 模块创建一个接口实例 rl，用于从控制台读取输入。
  • 监听 line 事件，当用户输入一行内容时，触发回调函数。
  • 在回调函数中：
    • 将输入内容 line 转换为整数 n。
    • 调用 getResult(n) 函数计算最少步数，并输出结果。
2. 最少步数计算
  • 特殊情况处理：
    • 当 n = 1 时，最少步数为 2（因为 1 = -2 + 3）。
    • 当 n = 2 时，最少步数为 1（因为 2 = 2）。
    • 当 n = 3 时，最少步数为 1（因为 3 = 3）。
  • 通用规律：
    • 对于 n >= 4，最少步数的计算方式为：
      • 基础步数 base = 2（从 n = 4 开始，最少步数为 2）。
      • 每增加 3，最少步数增加 1。
      • 公式：Math.floor((n - 4) / 3) + base。
3. 公式推导
  • 从 n = 4 开始：
    • n = 4：最少步数为 2。
    • n = 5：最少步数为 2。
    • n = 6：最少步数为 2。
    • n = 7：最少步数为 3。
    • n = 8：最少步数为 3。
    • n = 9：最少步数为 3。
    • n = 10：最少步数为 4。
    • 以此类推。
  • 规律：
    • 每增加 3，最少步数增加 1。
    • 公式：Math.floor((n - 4) / 3) + base。
4. 示例验证
示例 1：n = 4
  • 计算：
    • Math.floor((4 - 4) / 3) + 2 = 0 + 2 = 2。
  • 结果：
    • 最少步数为 2（符合 4 = 2 + 2）。
示例 2：n = 7
  • 计算：
    • Math.floor((7 - 4) / 3) + 2 = 1 + 2 = 3。
  • 结果：
    • 最少步数为 3（符合 7 = 3 + 2 + 2）。
示例 3：n = 10
  • 计算：
    • Math.floor((10 - 4) / 3) + 2 = 2 + 2 = 4。
  • 结果：
    • 最少步数为 4（符合 10 = 3 + 3 + 2 + 2）。

总结

  • 功能：计算将数字 n 分解为若干个 2 和 3 的和，使得分解后的项数最少。
  • 核心逻辑：
    1. 处理特殊情况（n = 1, 2, 3）。
    2. 对于 n >= 4，使用公式 Math.floor((n - 4) / 3) + base 计算最少步数。
  • 适用场景：需要将数字分解为 2 和 3 的和，且要求分解项数最少的场景。
  • 注意事项：
    • 输入必须为正整数。
    • 对于 n = 1，需要特殊处理。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是 Java 代码 的详细中文注释和逻辑讲解：

代码

import java.util.Scanner; // 导入 Scanner 类，用于读取输入public class Main {public static void main(String[] args) {// 创建 Scanner 对象，用于读取控制台输入Scanner sc = new Scanner(System.in);// 读取输入的整数 nint n = sc.nextInt();// 调用 getResult 方法计算最少步数，并输出结果System.out.println(getResult(n));}// 计算最少步数的方法public static int getResult(int n) {// 处理特殊情况if (n == 1) return 2; // n=1 时，最少步数为 2（-2 + 3）if (n == 2) return 1; // n=2 时，最少步数为 1（2）if (n == 3) return 1; // n=3 时，最少步数为 1（3）// 基础步数int base = 2; // 从 n=4 开始，最少步数为 2// 计算 n >= 4 时的最少步数return (n - 4) / 3 + base;}
}

代码逻辑讲解

1. 输入处理
  • 使用 Scanner 类从控制台读取输入。
  • 通过 sc.nextInt() 读取一个整数 n，表示需要分解的数字。
2. 最少步数计算
  • 特殊情况处理：
    • 当 n = 1 时，最少步数为 2（因为 1 = -2 + 3）。
    • 当 n = 2 时，最少步数为 1（因为 2 = 2）。
    • 当 n = 3 时，最少步数为 1（因为 3 = 3）。
  • 通用规律：
    • 对于 n >= 4，最少步数的计算方式为：
      • 基础步数 base = 2（从 n = 4 开始，最少步数为 2）。
      • 每增加 3，最少步数增加 1。
      • 公式：(n - 4) / 3 + base。
3. 公式推导
  • 从 n = 4 开始：
    • n = 4：最少步数为 2。
    • n = 5：最少步数为 2。
    • n = 6：最少步数为 2。
    • n = 7：最少步数为 3。
    • n = 8：最少步数为 3。
    • n = 9：最少步数为 3。
    • n = 10：最少步数为 4。
    • 以此类推。
  • 规律：
    • 每增加 3，最少步数增加 1。
    • 公式：(n - 4) / 3 + base。
4. 示例验证
示例 1：n = 4
  • 计算：
    • (4 - 4) / 3 + 2 = 0 + 2 = 2。
  • 结果：
    • 最少步数为 2（符合 4 = 2 + 2）。
示例 2：n = 7
  • 计算：
    • (7 - 4) / 3 + 2 = 1 + 2 = 3。
  • 结果：
    • 最少步数为 3（符合 7 = 3 + 2 + 2）。
示例 3：n = 10
  • 计算：
    • (10 - 4) / 3 + 2 = 2 + 2 = 4。
  • 结果：
    • 最少步数为 4（符合 10 = 3 + 3 + 2 + 2）。

总结

  • 功能：计算将数字 n 分解为若干个 2 和 3 的和，使得分解后的项数最少。
  • 核心逻辑：
    1. 处理特殊情况（n = 1, 2, 3）。
    2. 对于 n >= 4，使用公式 (n - 4) / 3 + base 计算最少步数。
  • 适用场景：需要将数字分解为 2 和 3 的和，且要求分解项数最少的场景。
  • 注意事项：
    • 输入必须为正整数。
    • 对于 n = 1，需要特殊处理。

如果有其他问题，欢迎随时提问！

四、Python算法源码

以下是 Python 代码 的详细中文注释和逻辑讲解：

代码

# 输入获取
n = int(input())  # 从控制台读取输入的整数 n# 算法入口
def getResult():# 处理特殊情况if n == 1:return 2  # n=1 时，最少步数为 2（-2 + 3）if n == 2:return 1  # n=2 时，最少步数为 1（2）if n == 3:return 1  # n=3 时，最少步数为 1（3）# 基础步数base = 2  # 从 n=4 开始，最少步数为 2# 计算 n >= 4 时的最少步数return (n - 4) // 3 + base# 算法调用
print(getResult())  # 调用 getResult 函数并输出结果

代码逻辑讲解

1. 输入处理
  • 使用 input() 函数从控制台读取输入，并通过 int() 将输入转换为整数 n。
2. 最少步数计算
  • 特殊情况处理：
    • 当 n = 1 时，最少步数为 2（因为 1 = -2 + 3）。
    • 当 n = 2 时，最少步数为 1（因为 2 = 2）。
    • 当 n = 3 时，最少步数为 1（因为 3 = 3）。
  • 通用规律：
    • 对于 n >= 4，最少步数的计算方式为：
      • 基础步数 base = 2（从 n = 4 开始，最少步数为 2）。
      • 每增加 3，最少步数增加 1。
      • 公式：(n - 4) // 3 + base。
3. 公式推导
  • 从 n = 4 开始：
    • n = 4：最少步数为 2。
    • n = 5：最少步数为 2。
    • n = 6：最少步数为 2。
    • n = 7：最少步数为 3。
    • n = 8：最少步数为 3。
    • n = 9：最少步数为 3。
    • n = 10：最少步数为 4。
    • 以此类推。
  • 规律：
    • 每增加 3，最少步数增加 1。
    • 公式：(n - 4) // 3 + base。
4. 示例验证
示例 1：n = 4
  • 计算：
    • (4 - 4) // 3 + 2 = 0 + 2 = 2。
  • 结果：
    • 最少步数为 2（符合 4 = 2 + 2）。
示例 2：n = 7
  • 计算：
    • (7 - 4) // 3 + 2 = 1 + 2 = 3。
  • 结果：
    • 最少步数为 3（符合 7 = 3 + 2 + 2）。
示例 3：n = 10
  • 计算：
    • (10 - 4) // 3 + 2 = 2 + 2 = 4。
  • 结果：
    • 最少步数为 4（符合 10 = 3 + 3 + 2 + 2）。

总结

  • 功能：计算将数字 n 分解为若干个 2 和 3 的和，使得分解后的项数最少。
  • 核心逻辑：
    1. 处理特殊情况（n = 1, 2, 3）。
    2. 对于 n >= 4，使用公式 (n - 4) // 3 + base 计算最少步数。
  • 适用场景：需要将数字分解为 2 和 3 的和，且要求分解项数最少的场景。
  • 注意事项：
    • 输入必须为正整数。
    • 对于 n = 1，需要特殊处理。

如果有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是 C 语言代码 和 C++ 代码 的详细中文注释和逻辑讲解：

C 语言代码

#include <stdio.h>  // 引入标准输入输出库int main() {int n;  // 定义变量 n，用于存储输入的数字scanf("%d", &n);  // 从控制台读取输入的整数 nint ans;  // 定义变量 ans，用于存储计算结果// 使用 switch 语句处理不同情况switch (n) {case 1:ans = 2;  // n=1 时，最少步数为 2（-2 + 3）break;case 2:ans = 1;  // n=2 时，最少步数为 1（2）break;case 3:ans = 1;  // n=3 时，最少步数为 1（3）break;default:ans = (n - 4) / 3 + 2;  // n >= 4 时，使用公式计算最少步数}printf("%d\n", ans);  // 输出结果return 0;  // 程序正常结束
}

C++ 代码

#include <iostream>  // 引入输入输出流库
using namespace std;  // 使用标准命名空间int main() {int n;  // 定义变量 n，用于存储输入的数字cin >> n;  // 从控制台读取输入的整数 nint ans;  // 定义变量 ans，用于存储计算结果// 使用 switch 语句处理不同情况switch (n) {case 1:ans = 2;  // n=1 时，最少步数为 2（-2 + 3）break;case 2:ans = 1;  // n=2 时，最少步数为 1（2）break;case 3:ans = 1;  // n=3 时，最少步数为 1（3）break;default:ans = (n - 4) / 3 + 2;  // n >= 4 时，使用公式计算最少步数}cout << ans << endl;  // 输出结果return 0;  // 程序正常结束
}

代码逻辑讲解

1. 输入处理
  • C 语言：
    • 使用 scanf("%d", &n) 从控制台读取输入的整数 n。
  • C++：
    • 使用 cin >> n 从控制台读取输入的整数 n。
2. 最少步数计算
  • 特殊情况处理：
    • 当 n = 1 时，最少步数为 2（因为 1 = -2 + 3）。
    • 当 n = 2 时，最少步数为 1（因为 2 = 2）。
    • 当 n = 3 时，最少步数为 1（因为 3 = 3）。
  • 通用规律：
    • 对于 n >= 4，最少步数的计算方式为：
      • 基础步数 2（从 n = 4 开始，最少步数为 2）。
      • 每增加 3，最少步数增加 1。
      • 公式：(n - 4) / 3 + 2。
3. 公式推导
  • 从 n = 4 开始：
    • n = 4：最少步数为 2。
    • n = 5：最少步数为 2。
    • n = 6：最少步数为 2。
    • n = 7：最少步数为 3。
    • n = 8：最少步数为 3。
    • n = 9：最少步数为 3。
    • n = 10：最少步数为 4。
    • 以此类推。
  • 规律：
    • 每增加 3，最少步数增加 1。
    • 公式：(n - 4) / 3 + 2。
4. 示例验证
示例 1：n = 4
  • 计算：
    • (4 - 4) / 3 + 2 = 0 + 2 = 2。
  • 结果：
    • 最少步数为 2（符合 4 = 2 + 2）。
示例 2：n = 7
  • 计算：
    • (7 - 4) / 3 + 2 = 1 + 2 = 3。
  • 结果：
    • 最少步数为 3（符合 7 = 3 + 2 + 2）。
示例 3：n = 10
  • 计算：
    • (10 - 4) / 3 + 2 = 2 + 2 = 4。
  • 结果：
    • 最少步数为 4（符合 10 = 3 + 3 + 2 + 2）。

总结

  • 功能：计算将数字 n 分解为若干个 2 和 3 的和，使得分解后的项数最少。
  • 核心逻辑：
    1. 处理特殊情况（n = 1, 2, 3）。
    2. 对于 n >= 4，使用公式 (n - 4) / 3 + 2 计算最少步数。
  • 适用场景：需要将数字分解为 2 和 3 的和，且要求分解项数最少的场景。
  • 注意事项：
    • 输入必须为正整数。
    • 对于 n = 1，需要特殊处理。

如果有其他问题，欢迎随时提问！

http://www.lryc.cn/news/520222.html

相关文章：

  • ＜C++＞ XlsxWriter写EXCEL
  • 接上一主题，实现QtByteArray任意进制字符串转为十进制数
  • CNN-GRU-MATT加入贝叶斯超参数优化，多输入单输出回归模型
  • Java 如何传参xml调用接口获取数据
  • uniapp 之 uni-forms校验提示【提交的字段[‘xxx‘]在数据库中并不存在】解决方案
  • excel VBA 基础教程
  • 基于异步IO的io_uring
  • 【江协STM32】10-2/3 MPU6050简介、软件I2C读写MPU6050
  • 仓颉笔记——写一个简易的web服务并用浏览器打开
  • DolphinScheduler自身容错导致的服务器持续崩溃重大问题的排查与解决
  • ecmascript 标准+ 严格模式与常规模式 + flat-flatMap 应用
  • 基于ILI9341液晶屏+STM32U5单片的显示试验
  • 最短路径算法
  • 如何用 ESP32-CAM 做一个实时视频流服务器
  • Centos7 解决Maven scope=system依赖jar包没有打包到启动jar包中的问题（OpenCV-4.10）
  • iOS实际开发中使用Alamofire实现多文件上传（以个人相册为例）
  • 如何将分割的mask转为为分割标签
  • 【动手学电机驱动】STM32-MBD（5）Simulink 模型开发之 PWM 输出
  • MySQL进阶突击系列(05)突击MVCC核心原理 | 左右护法ReadView视图和undoLog版本链强强联合
  • vue2日历组件
  • 【PyQt】多行纯文本框
  • workerman5.0篇〡异步非阻塞协程HTTP客户端
  • JavaScript 延迟加载的方法（ 7种 ）
  • python+pymysql
  • 基于 Selenium 实现上海大学校园网自动登录
  • 啥！GitHub Copilot也免费使用了
  • Spring配置文件中：密码明文改为密文处理方式（通用方法）
  • Linux下ext2文件系统
  • BUUCTF：web刷题记录(1)
  • 【微服务】面试题 6、分布式事务