报数游戏 - 华为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。

解题思路：

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

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