欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 新闻 > 会展 > 【2024年华为OD机试】 (C卷,100分)- 求解连续数列（Java JS PythonC/C++）

【2024年华为OD机试】 (C卷,100分)- 求解连续数列（Java JS PythonC/C++）

2025/1/16 3:36:07 来源：https://blog.csdn.net/m0_63168877/article/details/145136928  浏览:  次   关键词：【2024年华为OD机试】 (C卷,100分)- 求解连续数列（Java JS PythonC/C++）

在这里插入图片描述

一、问题描述

题目描述

已知连续正整数数列{K}=K1,K2,K3…Ki的各个数相加之和为S，i=N (0<S<100000, 0<N<100000), 求此数列K。

输入描述

输入包含两个参数，1）连续正整数数列和S，2）数列里数的个数N。

输出描述

如果有解输出数列K，如果无解输出-1。

用例

输入

525 6

输出

85 86 87 88 89 90

输入

3 5

输出

-1

题目解析

本题解题思路：

  1. 计算中间值：由于要求连续正整数数列的和，因此，S / N 的结果必然是数列的中间值。例如：

    • 对于数列 85 86 87 88 89 90，其和为 525，个数为 6，中间值为 525 / 6 = 87.5，由于 6 是偶数个，因此 87.5 实际上是 87 和 88 的中间值。
    • 对于数列 2 3 4，其和为 9，个数为 3，中间值为 9 / 3 = 3，由于 3 是奇数个，因此 3 就是数列的中间值。

  2. 确定边界值：得到中间值后，我们可以根据连续正整数数列的半径求出连续数列的两个边界值。半径为 N / 2（对于偶数个数列）或 (N - 1) / 2（对于奇数个数列）。

    • 对于偶数个数列，左边界为 中间值 - 半径，右边界为 中间值 + 半径。
    • 对于奇数个数列，左边界为 中间值 - 半径，右边界为 中间值 + 半径。

  3. 验证解：如果左边界到右边界之间的元素之和为 S，则这些边界值就是符合要求的。否则，说明无解。

  4. 返回结果：如果有解，返回两个边界之内的所有整数；如果无解，返回 -1。

通过这种方法，我们可以有效地求出连续正整数数列，时间复杂度为 O(1)，因为只需要计算中间值和边界值，然后验证解即可。

二、JavaScript算法源码

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

JavaScript 代码实现

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline"); // 引入 readline 模块，用于读取控制台输入// 创建 readline 接口
const rl = readline.createInterface({input: process.stdin,  // 输入流为标准输入output: process.stdout, // 输出流为标准输出
});// 监听输入事件
rl.on("line", (line) => {// 将输入行按空格分隔，并转换为数字数组const [sum, n] = line.split(" ").map(Number);// 调用 getResult 函数，计算并输出结果console.log(getResult(sum, n));
});/*** 计算满足条件的连续整数序列** @param {number} sum - 目标和* @param {number} n - 连续整数的个数* @return {string} - 返回满足条件的序列，用空格分隔；如果没有满足条件的序列，返回 "-1"*/
function getResult(sum, n) {// 计算中间值const mid = Math.floor(sum / n); // 目标和除以个数，取整得到中间值let left, right; // 定义序列的起始和结束值// 根据 n 的奇偶性，计算序列的起始和结束值if (n % 2 == 0) { // 如果 n 是偶数const half = n / 2; // 计算一半的长度left = mid - half + 1; // 起始值为中间值减去一半长度加 1right = mid + half;    // 结束值为中间值加上一半长度} else { // 如果 n 是奇数const half = (n - 1) / 2; // 计算一半的长度left = mid - half;        // 起始值为中间值减去一半长度right = mid + half;       // 结束值为中间值加上一半长度}// 生成序列const arr = []; // 定义数组 arr，用于存储序列let total = 0;  // 定义变量 total，用于计算序列的总和for (let i = left; i <= right; i++) {arr.push(i); // 将当前值添加到数组中total += i;  // 累加当前值到总和}// 检查序列的总和是否等于目标和if (total == sum) {return arr.join(" "); // 如果相等，返回序列，用空格分隔} else {return "-1"; // 如果不相等，返回 "-1"}
}

代码讲解

1. 输入处理

  • 使用 readline 模块读取控制台输入。
  • 将输入行按空格分隔，并转换为数字数组 [sum, n]：
    • sum 表示目标和。
    • n 表示连续整数的个数。

2. 主算法函数 getResult

  • 功能：计算满足条件的连续整数序列。
  • 逻辑：
    1. 计算中间值 mid：
      • mid = Math.floor(sum / n)，即目标和除以个数，取整得到中间值。
    2. 根据 n 的奇偶性，计算序列的起始值 left 和结束值 right：
      • 如果 n 是偶数：
        • left = mid - half + 1。
        • right = mid + half。
      • 如果 n 是奇数：
        • left = mid - half。
        • right = mid + half。
    3. 生成序列：
      • 使用 for 循环从 left 到 right，将每个整数添加到数组 arr 中。
      • 同时计算序列的总和 total。
    4. 检查序列的总和是否等于目标和 sum：
      • 如果相等，返回序列，用空格分隔。
      • 如果不相等，返回 -1。

示例分析

示例 1

输入：

15 3

输出：

4 5 6

解释：

  • 目标和 sum = 15，连续整数个数 n = 3。
  • 中间值 mid = Math.floor(15 / 3) = 5。
  • 因为 n 是奇数，所以：
    • left = 5 - 1 = 4。
    • right = 5 + 1 = 6。
  • 生成的序列为 [4, 5, 6]，总和为 15，满足条件。

示例 2

输入：

10 4

输出：

1 2 3 4

解释：

  • 目标和 sum = 10，连续整数个数 n = 4。
  • 中间值 mid = Math.floor(10 / 4) = 2。
  • 因为 n 是偶数，所以：
    • left = 2 - 2 + 1 = 1。
    • right = 2 + 2 = 4。
  • 生成的序列为 [1, 2, 3, 4]，总和为 10，满足条件。

示例 3

输入：

20 5

输出：

2 3 4 5 6

解释：

  • 目标和 sum = 20，连续整数个数 n = 5。
  • 中间值 mid = Math.floor(20 / 5) = 4。
  • 因为 n 是奇数，所以：
    • left = 4 - 2 = 2。
    • right = 4 + 2 = 6。
  • 生成的序列为 [2, 3, 4, 5, 6]，总和为 20，满足条件。

复杂度分析

  1. 时间复杂度：

    • 生成序列的循环时间复杂度为 O(n)，其中 n 是连续整数的个数。

  2. 空间复杂度：

    • 使用了一个数组 arr 存储序列，空间复杂度为 O(n)。

总结

  • 该代码通过计算中间值，并根据 n 的奇偶性确定序列的起始和结束值，生成满足条件的连续整数序列。
  • 使用 readline 模块处理输入，适合 ACM 模式。
  • 如果有其他问题，欢迎继续提问！

三、Java算法源码

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

Java 代码实现

import java.util.Scanner; // 导入 Scanner 类，用于读取输入
import java.util.StringJoiner; // 导入 StringJoiner 类，用于拼接字符串public class Main {// 主函数，程序入口public static void main(String[] args) {Scanner sc = new Scanner(System.in); // 创建 Scanner 对象，用于读取标准输入int sum = sc.nextInt(); // 读取目标和 sumint n = sc.nextInt();   // 读取连续整数的个数 n// 调用 getResult 方法，计算并输出结果System.out.println(getResult(sum, n));}/*** 计算满足条件的连续整数序列** @param sum - 目标和* @param n - 连续整数的个数* @return 返回满足条件的序列，用空格分隔；如果没有满足条件的序列，返回 "-1"*/public static String getResult(int sum, int n) {int mid = sum / n; // 计算中间值，即目标和除以个数int left, right, half; // 定义序列的起始值、结束值和一半长度// 根据 n 的奇偶性，计算序列的起始值 leftif (n % 2 == 0) { // 如果 n 是偶数half = n / 2; // 计算一半的长度left = mid - half + 1; // 起始值为中间值减去一半长度加 1} else { // 如果 n 是奇数half = (n - 1) / 2; // 计算一半的长度left = mid - half;  // 起始值为中间值减去一半长度}right = mid + half; // 结束值为中间值加上一半长度// 使用 StringJoiner 拼接序列StringJoiner sj = new StringJoiner(" "); // 创建 StringJoiner 对象，用空格分隔int total = 0; // 定义变量 total，用于计算序列的总和for (int i = left; i <= right; i++) { // 遍历从 left 到 right 的整数sj.add(i + ""); // 将当前整数添加到 StringJoiner 中total += i;     // 累加当前整数到总和}// 检查序列的总和是否等于目标和if (total == sum) {return sj.toString(); // 如果相等，返回拼接后的序列} else {return "-1"; // 如果不相等，返回 "-1"}}
}

代码讲解

1. 输入处理

  • 使用 Scanner 类读取标准输入：
    • sum 表示目标和。
    • n 表示连续整数的个数。

2. 主算法函数 getResult

  • 功能：计算满足条件的连续整数序列。
  • 逻辑：
    1. 计算中间值 mid：
      • mid = sum / n，即目标和除以个数。
    2. 根据 n 的奇偶性，计算序列的起始值 left：
      • 如果 n 是偶数：
        • left = mid - half + 1。
      • 如果 n 是奇数：
        • left = mid - half。
    3. 计算序列的结束值 right：
      • right = mid + half。
    4. 使用 StringJoiner 拼接序列：
      • 遍历从 left 到 right 的整数，将其添加到 StringJoiner 中。
      • 同时计算序列的总和 total。
    5. 检查序列的总和是否等于目标和 sum：
      • 如果相等，返回拼接后的序列。
      • 如果不相等，返回 -1。

示例分析

示例 1

输入：

15 3

输出：

4 5 6

解释：

  • 目标和 sum = 15，连续整数个数 n = 3。
  • 中间值 mid = 15 / 3 = 5。
  • 因为 n 是奇数，所以：
    • left = 5 - 1 = 4。
    • right = 5 + 1 = 6。
  • 生成的序列为 [4, 5, 6]，总和为 15，满足条件。

示例 2

输入：

10 4

输出：

1 2 3 4

解释：

  • 目标和 sum = 10，连续整数个数 n = 4。
  • 中间值 mid = 10 / 4 = 2。
  • 因为 n 是偶数，所以：
    • left = 2 - 2 + 1 = 1。
    • right = 2 + 2 = 4。
  • 生成的序列为 [1, 2, 3, 4]，总和为 10，满足条件。

示例 3

输入：

20 5

输出：

2 3 4 5 6

解释：

  • 目标和 sum = 20，连续整数个数 n = 5。
  • 中间值 mid = 20 / 5 = 4。
  • 因为 n 是奇数，所以：
    • left = 4 - 2 = 2。
    • right = 4 + 2 = 6。
  • 生成的序列为 [2, 3, 4, 5, 6]，总和为 20，满足条件。

复杂度分析

  1. 时间复杂度：

    • 生成序列的循环时间复杂度为 O(n)，其中 n 是连续整数的个数。

  2. 空间复杂度：

    • 使用 StringJoiner 存储序列，空间复杂度为 O(n)。

总结

  • 该代码通过计算中间值，并根据 n 的奇偶性确定序列的起始和结束值，生成满足条件的连续整数序列。
  • 使用 StringJoiner 拼接序列，适合需要格式化输出的场景。
  • 如果有其他问题，欢迎继续提问！

四、Python算法源码

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

Python 代码实现

# 输入获取
sumV, n = map(int, input().split())  # 读取输入，将输入的两个值分别赋值给 sumV（目标和）和 n（连续整数的个数）# 算法入口
def getResult():mid = sumV // n  # 计算中间值，即目标和除以个数，取整# 根据 n 的奇偶性，计算序列的起始值 left 和结束值 rightif n % 2 == 0:  # 如果 n 是偶数half = n // 2  # 计算一半的长度left = mid - half + 1  # 起始值为中间值减去一半长度加 1right = mid + half  # 结束值为中间值加上一半长度else:  # 如果 n 是奇数half = (n - 1) // 2  # 计算一半的长度left = mid - half  # 起始值为中间值减去一半长度right = mid + half  # 结束值为中间值加上一半长度# 生成序列arr = [i for i in range(left, right + 1)]  # 使用列表推导式生成从 left 到 right 的连续整数序列total = sum(arr)  # 计算序列的总和# 检查序列的总和是否等于目标和if total != sumV:  # 如果总和不等于目标和return "-1"  # 返回 "-1"else:  # 如果总和等于目标和return " ".join(map(str, arr))  # 将序列转换为字符串，用空格分隔并返回# 算法调用
print(getResult())  # 调用 getResult 函数并输出结果

代码讲解

1. 输入处理

  • 使用 input().split() 读取输入，并将其转换为整数：
    • sumV 表示目标和。
    • n 表示连续整数的个数。

2. 主算法函数 getResult

  • 功能：计算满足条件的连续整数序列。
  • 逻辑：
    1. 计算中间值 mid：
      • mid = sumV // n，即目标和除以个数，取整。
    2. 根据 n 的奇偶性，计算序列的起始值 left 和结束值 right：
      • 如果 n 是偶数：
        • left = mid - half + 1。
        • right = mid + half。
      • 如果 n 是奇数：
        • left = mid - half。
        • right = mid + half。
    3. 生成序列：
      • 使用列表推导式 [i for i in range(left, right + 1)] 生成从 left 到 right 的连续整数序列。
    4. 计算序列的总和 total：
      • 使用 sum(arr) 计算序列的总和。
    5. 检查序列的总和是否等于目标和 sumV：
      • 如果总和不等于目标和，返回 "-1"。
      • 如果总和等于目标和，将序列转换为字符串，用空格分隔并返回。

示例分析

示例 1

输入：

15 3

输出：

4 5 6

解释：

  • 目标和 sumV = 15，连续整数个数 n = 3。
  • 中间值 mid = 15 // 3 = 5。
  • 因为 n 是奇数，所以：
    • left = 5 - 1 = 4。
    • right = 5 + 1 = 6。
  • 生成的序列为 [4, 5, 6]，总和为 15，满足条件。

示例 2

输入：

10 4

输出：

1 2 3 4

解释：

  • 目标和 sumV = 10，连续整数个数 n = 4。
  • 中间值 mid = 10 // 4 = 2。
  • 因为 n 是偶数，所以：
    • left = 2 - 2 + 1 = 1。
    • right = 2 + 2 = 4。
  • 生成的序列为 [1, 2, 3, 4]，总和为 10，满足条件。

示例 3

输入：

20 5

输出：

2 3 4 5 6

解释：

  • 目标和 sumV = 20，连续整数个数 n = 5。
  • 中间值 mid = 20 // 5 = 4。
  • 因为 n 是奇数，所以：
    • left = 4 - 2 = 2。
    • right = 4 + 2 = 6。
  • 生成的序列为 [2, 3, 4, 5, 6]，总和为 20，满足条件。

复杂度分析

  1. 时间复杂度：

    • 生成序列的循环时间复杂度为 O(n)，其中 n 是连续整数的个数。

  2. 空间复杂度：

    • 使用列表 arr 存储序列，空间复杂度为 O(n)。

总结

  • 该代码通过计算中间值，并根据 n 的奇偶性确定序列的起始和结束值，生成满足条件的连续整数序列。
  • 使用列表推导式和 sum 函数简化了代码逻辑。
  • 如果有其他问题，欢迎继续提问！

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

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

C 语言代码实现

#include <stdio.h>
#include <string.h>int main() {int sum, n; // 定义变量 sum（目标和）和 n（连续整数的个数）scanf("%d %d", &sum, &n); // 读取输入，将输入的两个值分别赋值给 sum 和 nint mid = sum / n; // 计算中间值，即目标和除以个数，取整int left, right, half; // 定义变量 left（序列起始值）、right（序列结束值）和 half（一半长度）// 根据 n 的奇偶性，计算序列的起始值 leftif (n % 2 == 0) { // 如果 n 是偶数half = n / 2; // 计算一半的长度left = mid - half + 1; // 起始值为中间值减去一半长度加 1} else { // 如果 n 是奇数half = (n - 1) / 2; // 计算一半的长度left = mid - half;  // 起始值为中间值减去一半长度}right = mid + half; // 结束值为中间值加上一半长度char res[100000] = ""; // 定义字符数组 res，用于存储结果序列，初始化为空字符串int total = 0; // 定义变量 total，用于计算序列的总和// 遍历从 left 到 right 的整数，生成序列并计算总和for (int i = left; i <= right; i++) {char tmp[1000]; // 定义字符数组 tmp，用于临时存储当前整数的字符串形式sprintf(tmp, "%d", i); // 将当前整数转换为字符串并存储到 tmp 中strcat(res, tmp); // 将 tmp 拼接到 res 中if (i < right) { // 如果当前整数不是最后一个strcat(res, " "); // 在 res 中添加一个空格}total += i; // 累加当前整数到总和}// 检查序列的总和是否等于目标和if (total == sum) { // 如果相等puts(res); // 输出结果序列} else { // 如果不相等puts("-1"); // 输出 "-1"}return 0; // 程序正常结束
}

C++ 代码实现

#include <iostream>
#include <sstream>
using namespace std;int main() {int sum, n; // 定义变量 sum（目标和）和 n（连续整数的个数）cin >> sum >> n; // 读取输入，将输入的两个值分别赋值给 sum 和 nint mid = sum / n; // 计算中间值，即目标和除以个数，取整int left, right, half; // 定义变量 left（序列起始值）、right（序列结束值）和 half（一半长度）// 根据 n 的奇偶性，计算序列的起始值 leftif (n % 2 == 0) { // 如果 n 是偶数half = n / 2; // 计算一半的长度left = mid - half + 1; // 起始值为中间值减去一半长度加 1} else { // 如果 n 是奇数half = (n - 1) / 2; // 计算一半的长度left = mid - half;  // 起始值为中间值减去一半长度}right = mid + half; // 结束值为中间值加上一半长度ostringstream oss; // 定义字符串流 oss，用于拼接结果序列int total = 0; // 定义变量 total，用于计算序列的总和// 遍历从 left 到 right 的整数，生成序列并计算总和for (int i = left; i <= right; i++) {oss << i; // 将当前整数添加到字符串流中if (i < right) { // 如果当前整数不是最后一个oss << " "; // 在字符串流中添加一个空格}total += i; // 累加当前整数到总和}// 检查序列的总和是否等于目标和if (total == sum) { // 如果相等cout << oss.str() << endl; // 输出结果序列} else { // 如果不相等cout << "-1" << endl; // 输出 "-1"}return 0; // 程序正常结束
}

代码讲解

1. 输入处理

  • C 语言：
    • 使用 scanf 读取输入，将输入的两个值分别赋值给 sum 和 n。
  • C++：
    • 使用 cin 读取输入，将输入的两个值分别赋值给 sum 和 n。

2. 计算中间值

  • 计算中间值 mid：
    • mid = sum / n，即目标和除以个数，取整。

3. 根据 n 的奇偶性计算序列的起始值和结束值

  • 如果 n 是偶数：
    • left = mid - half + 1。
    • right = mid + half。
  • 如果 n 是奇数：
    • left = mid - half。
    • right = mid + half。

4. 生成序列并计算总和

  • C 语言：
    • 使用 sprintf 将整数转换为字符串，并使用 strcat 拼接结果。
    • 使用 total 累加序列的总和。
  • C++：
    • 使用 ostringstream 拼接结果序列。
    • 使用 total 累加序列的总和。

5. 检查序列的总和是否等于目标和

  • 如果总和等于目标和，输出结果序列。
  • 如果总和不等于目标和，输出 -1。

示例分析

示例 1

输入：

15 3

输出：

4 5 6

解释：

  • 目标和 sum = 15，连续整数个数 n = 3。
  • 中间值 mid = 15 / 3 = 5。
  • 因为 n 是奇数，所以：
    • left = 5 - 1 = 4。
    • right = 5 + 1 = 6。
  • 生成的序列为 [4, 5, 6]，总和为 15，满足条件。

示例 2

输入：

10 4

输出：

1 2 3 4

解释：

  • 目标和 sum = 10，连续整数个数 n = 4。
  • 中间值 mid = 10 / 4 = 2。
  • 因为 n 是偶数，所以：
    • left = 2 - 2 + 1 = 1。
    • right = 2 + 2 = 4。
  • 生成的序列为 [1, 2, 3, 4]，总和为 10，满足条件。

复杂度分析

  1. 时间复杂度：

    • 生成序列的循环时间复杂度为 O(n)，其中 n 是连续整数的个数。

  2. 空间复杂度：

    • C 语言：使用字符数组 res 存储结果序列，空间复杂度为 O(n)。
    • C++：使用 ostringstream 存储结果序列，空间复杂度为 O(n)。

总结

  • C 语言 和 C++ 代码通过计算中间值，并根据 n 的奇偶性确定序列的起始和结束值，生成满足条件的连续整数序列。
  • C 语言 使用字符数组和字符串函数拼接结果，C++ 使用字符串流简化了拼接逻辑。
  • 如果有其他问题，欢迎继续提问！

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词

WINFORM - DevExpress -＞ alertControl1提示信息框 ffmpeg aac s16 encode_audio.c AS3 AIR路径问题 离线录制激光雷达数据进行建图 在 Ubuntu 22.04 上部署 AppArmor 应用安全教程 STM32供电参考设计