报数游戏 - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

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

输入描述

输入一个整数参数M。

输出描述

如果输入参数M小于等于1或者大于等于100，输出"ERROR!"；否则按照原先的编号从小到大的顺序，以逗号分割输出编号字符串。

示例1

输入：
3

输出：
58,91

说明：
输入M为3，最后剩下两个人

示例2

输入：
4

输出：
34,45,97

说明：
输入M为4，最后剩下三个人

题解

该问题属于循环链表问题，可以通过约瑟夫环（Josephus Problem）的思路来解决。这类问题的关键在于模拟一个按固定规则报数和删除的过程。通过循环报数，每次删除报到特定数字的人，并在下次从紧邻剩下的人重新开始报数，直到剩下的人数少于M。

解题思路：

输入校验：首先检查输入的整数参数 M 是否在有效范围（1 < M < 100）内。如果无效则输出 "ERROR!"。
初始化队列：使用一个列表或者链表来保存1到100的编号。这个队列将模拟人围成一圈的情况。
循环删除元素：从编号为1开始报数，每当报到数字 M 时，移除该人（即从队列中删除该元素），并从下一个人重新开始报数。
处理循环：为了模拟围成一圈的过程，当到达列表末尾时，需要从头继续开始报数。
输出结果：当剩下的人数少于 M 时，按照编号升序输出剩下的编号，以逗号分隔。

Java

java">import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        if (M <= 1 || M >= 100) {
            System.out.println("ERROR!");
            return;
        }

        List<String> nums = new LinkedList<>();
        for (int i = 1; i <= 100; i++) {
            nums.add(String.valueOf(i));
        }

        Iterator<String> it = nums.iterator();
        for (int now = 1; nums.size() >= M; now++) {
            if (!it.hasNext()) it = nums.iterator(); // 回到开头
            it.next(); // 遍历下一个

            if (now == M) {
                // 注意： Iterator 的 remove() 方法只能在调用 next() 之后使用
                it.remove();
                now = 0;
            }
        }

        System.out.println(String.join(",", nums));	// 输出剩余元素
    }
}

Python

python">def main():
    M = int(input())
    if M <= 1 or M >= 100:
        print("ERROR!")
        return

    nums = [str(i) for i in range(1, 101)]  # 初始化编号列表

    index = 0
    now = 1
    while len(nums) >= M:
        if now == M:
            nums.pop(index)	# 删除当前编号
            now = 0	# 重置计数
        else:
            # 如果当前位置是最后一个元素，回到第一个位置（循环列表效果）
            index = (index + 1) % len(nums)
        now += 1

    print(",".join(nums))	# 输出剩余编号


if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int M;
    cin >> M;
    if (M <= 1 || M >= 100) {
        cout << "ERROR!" << endl;
        return 0;
    }

    list<int> nums;
    for (int i = 1; i <= 100; i++) nums.push_back(i);

    int now = 1;
    for (auto it = nums.begin(); nums.size() >= M; now++) {
        if (it == nums.end()) it = nums.begin();   // 回到链表开头

        if (now == M) {
            // 注意这里 it = 不要漏写
            it  = nums.erase(it);   // 删除当前元素并更新迭代器
            now = 0;                // 重置计数
        } else {
            it++;
        }
    }

    for (auto it = nums.begin(); it != nums.end();) {
        cout << *it;
        if (++it != nums.end()) cout << ",";
    }
    cout << endl;

    return 0;
}