报数游戏问题

一、题目描述

100个人围成一圈，每个人有一个编码，编号从1开始到100。

他们从1开始依次报数，报到为M的人自动退出圈圈，然后下一个人接着从1开始报数，直到剩余的人数小于M。

请问最后剩余的人在原先的编号为多少？

二、输入输出描述

输入描述

• 整数M。

输出描述

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

三、示例

四、解题思路

1. 核心思想

使用链表 + 迭代器模拟循环报数淘汰过程，遍历节点时动态删除被淘汰的人，直到剩余人数＜M，最后排序输出结果。

2. 问题本质分析

这是一个循环报数删除问题（约瑟夫环）：

• 对象：1~100 连续编号
• 规则：循环报数，报到 M 淘汰
• 停止条件：剩余人数 < M
• 输出：剩余编号从小到大
• 本质：循环遍历 + 动态删除 + 结果排序

3. 核心逻辑

1. 输入校验：M 必须是 2~99，否则报错
2. 链表存储：用 LinkedList 存 1~100，方便删除
3. 迭代器遍历：支持循环遍历 + 中途删除节点
4. 报数淘汰：每报数到 M，删除当前人，计数器归零
5. 停止条件：链表大小＜M 时停止淘汰
6. 排序输出：剩余编号升序，逗号拼接

4. 步骤拆解

1. 输入与校验

   • 读取 M
   • 不在 2~99 直接输出 ERROR

2. 初始化数据

   • 生成 1~100 编号，存入 LinkedList

3. 循环淘汰

   • 迭代器遍历，逐个报数
   • 报到 M 就删除，计数器归零
   • 直到人数＜M 停止

4. 结果处理

   • 剩余编号升序排序
   • 拼接成逗号分隔格式
   • 输出字符串

五、代码实现

import java.util.*; 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; } // 初始化 1~100 编号 LinkedList<Integer> list = new LinkedList<>(); for (int i = 1; i <= 100; i++) { list.add(i); } int count = 0; // 当前报数 // 剩余人数 >= M 就继续淘汰 while (list.size() >= M) { ListIterator<Integer> it = list.listIterator(); while (it.hasNext() && list.size() >= M) { it.next(); count++; // 报到 M 就删除 if (count == M) { it.remove(); count = 0; // 下一个从 1 开始 } } } // 排序（题目要求按编号从小到大输出） Collections.sort(list); // 输出格式拼接 StringBuilder sb = new StringBuilder(); for (int num : list) { sb.append(num).append(","); } if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } System.out.println(sb); } }