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

【华为OD-E卷 - 报数游戏 100分（python、java、c++、js、c）】

article 2025/2/3 2:10:20

【华为OD-E卷 - 报数游戏 100分（python、java、c++、js、c）】

题目

100个人围成一圈，每个人有一个编码，编号从1开始到100。
他们从1开始依次报数，报到为M的人自动退出圈圈，然后下一个人接着从1开始报数，直到剩余的人数小于M。
请问最后剩余的人在原先的编号为多少？

输入描述

输入一个整数参数 M

输出描述

如果输入参数M小于等于1或者大于等于100，输出“ERROR!”；

否则按照原先的编号从小到大的顺序，以英文逗号分割输出编号字符串

用例

用例一：

输入：

输出：

58,91

用例二：

输入：

输出：

34,45,97

python解法

解题思路：
这个问题类似于约瑟夫环的变形。题目要求从1到100的100个人围成一圈，每次按照给定的间隔 m 依次淘汰人，直到剩下的人数少于 m 为止，最后输出剩下的人的编号，并按从小到大排序。

解题步骤：

初始化人数：创建 people 列表，包含 1 到 100 的编号。
设置初始索引：用 idx = 0 表示当前淘汰的位置索引。
模拟淘汰过程：
每次按照 m 计算需要淘汰的索引 (idx + m - 1) % len(people)
pop() 移除相应索引处的人
直到 people 数量小于 m 时停止
排序并输出：将剩下的 people 按升序排序，并用 “,” 连接成字符串返回。

m = int(input())  # 读取输入的整数 m

def iterative_solution(m):
    # 判断 m 是否在有效范围内
    if m <= 1 or m >= 100:
        return "ERROR!"  # 输入无效时返回 "ERROR!"

    people = list(range(1, 101))  # 初始化 1~100 的列表
    idx = 0  # 初始化当前索引

    while len(people) >= m:  # 当剩余人数不少于 m 时，继续淘汰
        idx = (idx + m - 1) % len(people)  # 计算当前淘汰的位置
        people.pop(idx)  # 移除该索引位置的元素

    return ",".join(map(str, sorted(people)))  # 返回剩余人数，按升序排序并转换为字符串

print(iterative_solution(m))  # 输出结果

java解法

解题思路
这个问题本质上是一个变形的约瑟夫问题，要求从 1 到 100 个人中，每次按照 m 报数并淘汰，直到剩余人数少于 m。然后输出剩下的人的编号，按从小到大排序。

解题步骤
输入 m：

如果 m 不满足 1 < m < 100，直接返回 “ERROR!”。
初始化数据结构：

removed[100] 作为布尔数组，用于记录哪些人已被淘汰（true 表示已淘汰）。
count 记录当前报数到多少。
remaining 记录当前剩余人数，初始化为 100。
currentIndex 记录当前正在报数的人的索引，初始化为 0。
模拟报数淘汰过程：

遍历 removed 数组，跳过已淘汰的人，只对未淘汰的人进行报数。
每当 count == m 时，淘汰该人（设置 removed[currentIndex] = true），重置 count 并减少 remaining。
使用 currentIndex = (currentIndex + 1) % 100 来循环遍历整个数组。
筛选剩余人员并输出：

遍历 removed 数组，将未淘汰的人的编号加入 StringJoiner 并返回

import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();  // 读取输入的整数 m
        System.out.println(getResult(m));  // 调用函数并输出结果
    }

    public static String getResult(int m) {
        // 判断 m 是否在有效范围内
        if (m <= 1 || m >= 100) return "ERROR!";

        boolean[] removed = new boolean[100];  // 标记哪些人被淘汰
        int count = 0;  // 报数计数
        int remaining = 100;  // 剩余人数
        int currentIndex = 0;  // 当前报数的位置

        // 只要剩余人数不少于 m，就继续淘汰
        while (remaining >= m) {
            // 仅对未被淘汰的人进行报数
            if (!removed[currentIndex]) {
                count++;  // 计数器 +1

                // 当报数达到 m 时，该人被淘汰
                if (count == m) {
                    removed[currentIndex] = true;  // 标记该人被淘汰
                    count = 0;  // 重置计数器
                    remaining--;  // 剩余人数减少
                }
            }
            // 移动到下一个人（循环列表）
            currentIndex = (currentIndex + 1) % 100;
        }

        // 使用 StringJoiner 构造剩余未被淘汰的人的编号字符串
        StringJoiner sj = new StringJoiner(",");
        for (int i = 0; i < 100; i++) {
            if (!removed[i]) {
                sj.add(String.valueOf(i + 1));  // 添加未被淘汰的人编号（编号从1开始）
            }
        }

        return sj.toString();  // 返回最终结果字符串
    }
}

C++解法

解题思路
输入 m：

若 m 不满足 1 < m < 100，直接输出 “ERROR!” 并退出。
初始化 people 数组：

使用 vector 存储 1~100 的编号。
模拟报数淘汰过程：

设定 idx 作为当前要淘汰的索引，初始值 0。
循环淘汰：当 people 数量不少于 m 时：
计算下一轮被淘汰者的索引位置：idx = (idx + m - 1) % people.size();
使用 erase() 移除该索引处的人。
排序并输出结果：

sort(people.begin(), people.end()); 保障剩下的编号按升序排列。
逐个打印剩下的编号，并使用 “,” 进行分隔

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int m;
    cin >> m;  // 读取输入的整数 m

    // 判断 m 是否在有效范围内
    if (m <= 1 || m >= 100) {
        cout << "ERROR!" << endl;
        return 0;
    }

    vector<int> people(100);  // 存储 1~100 的人
    for (int i = 0; i < 100; ++i) {
        people[i] = i + 1;  // 初始化编号
    }

    int idx = 0;  // 当前淘汰位置索引

    // 只要剩余人数不少于 m，就继续淘汰
    while (people.size() >= m) {
        idx = (idx + m - 1) % people.size();  // 计算当前淘汰的人
        people.erase(people.begin() + idx);  // 移除该索引处的人
    }

    sort(people.begin(), people.end());  // 确保剩下的编号升序排列

    // 输出最终剩余的人的编号
    for (size_t i = 0; i < people.size(); ++i) {
        cout << people[i];
        if (i != people.size() - 1) cout << ",";  // 逗号分隔输出
    }

    return 0;
}

C解法

解题思路

更新中

JS解法

解题思路
读取输入 m：

若 m 不在有效范围 1 < m < 100，返回 “ERROR!”。
初始化 people 数组：

使用 Array.from({ length: 100 }, (_, i) => i + 1) 创建 1~100 的编号数组。
模拟报数淘汰过程：

设定 index 作为当前要淘汰的索引，初始值 0。
循环淘汰：当 people 数量不少于 m 时：
计算当前需要淘汰的索引 index = (index + m - 1) % people.length
使用 splice(index, 1) 移除该索引处的人。
返回剩余人员编号：

people.join() 将剩余编号以 , 分隔并返回

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

// 监听标准输入，读取用户输入的 m
rl.on("line", (line) => {
  const m = parseInt(line); // 解析输入的整数 m
  console.log(calculateSurvivors(m)); // 计算并输出剩余编号
});

// 计算最终剩余的人员编号
function calculateSurvivors(m) {
  // 检查输入 m 是否有效
  if (m <= 1 || m >= 100) {
    return "ERROR!";
  }

  // 初始化 1~100 的编号数组
  const people = Array.from({ length: 100 }, (_, i) => i + 1);
  let index = 0; // 当前淘汰索引

  // 只要剩余人数不少于 m，就继续淘汰
  while (people.length >= m) {
    index = (index + m - 1) % people.length; // 计算当前要淘汰的索引
    people.splice(index, 1); // 移除该索引处的人
  }

  return people.join(); // 返回剩余人员的编号，以 "," 连接
}