报数游戏 - 华为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!")returnnums = [str(i) for i in range(1, 101)]  # 初始化编号列表index = 0now = 1while len(nums) >= M:if now == M:nums.pop(index)	# 删除当前编号now = 0	# 重置计数else:# 如果当前位置是最后一个元素，回到第一个位置（循环列表效果）index = (index + 1) % len(nums)now += 1print(",".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;
}