华为OD机试真题---报数游戏

题目描述

有100个人围成一圈，每个人有一个唯一的编号，从1到100。他们从1开始依次报数，当报到某个数m（m也是正整数，且通常小于或等于n）时，该人自动退出圈子，然后下一个人接着从1开始报数，直到剩余的人数小于m。请问最后剩余的人在原先的编号为多少？

输入描述

输入：一个整数m，表示报数的阈值。

输出描述

输出：如果输入参数小于等于1或大于等于100.输出’ERROR‘,否则按照原先的编号从大到小顺序，以英文逗号分割输出编号字符串

代码示例


import java.util.LinkedList;
import java.util.Scanner;public class JosephusProblem {/*** 解决约瑟夫环问题* 从1到100编号的人围成一圈，从1开始依次报数，当报到m时，该人退出圈子，* 下一个人接着从1开始报数，直到剩余的人数小于m。** @param m 报数的阈值* @return 最后剩余的人的编号，按从大到小排序*/public static String solveJosephusProblem(int m) {if (m <= 1 || m >= 100) {return "ERROR";}LinkedList<Integer> people = new LinkedList<>();for (int i = 1; i <= 100; i++) {people.add(i); // 初始化编号为1到100的人}int current = 0; // 当前报数的人的索引while (people.size() >= m) {// 移除报数到m的人current = (current + m - 1) % people.size();people.remove(current);}// 将剩余的人按从大到小排序StringBuilder result = new StringBuilder();for (int i = people.size() - 1; i >= 0; i--) {result.append(people.get(i));if (i > 0) {result.append(",");}}return result.toString();}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();scanner.close();String result = solveJosephusProblem(m);System.out.println(result);}
}

代码说明：

输入处理：读取一个整数m作为报数的阈值。
有效性检查：如果m小于等于1或大于等于100，则输出’ERROR’并结束程序。
链表初始化：创建一个链表people，包含从1到100的整数，表示围成一圈的人。
报数游戏模拟：
- 使用一个索引index来跟踪当前报数到哪个人。
- 在每次循环中，计算下一个要淘汰的人的索引（使用取模运算来处理循环报数）。
- 从链表中移除该人。
输出结果：当链表中只剩下一个人时，输出其编号。

注意事项：

根据题目要求，n的值是固定的（例如100），因此不需要作为输入。
输入参数m的有效范围是(1, 100)，不包括1和100本身。
输出应该是最后剩余的人的编号，而不是按某种顺序输出所有人（因为过程中只有一个人会最终留下来）。

代码解释

1、解决约瑟夫环问题 (solveJosephusProblem 方法):

初始化一个 LinkedList 来存储编号为 1 到 100 的人。
使用一个变量 current 来记录当前报数人的索引。
在循环中，每次移动 m 步，移除当前报数到 m 的人。
当剩余人数小于 m 时，停止循环。
将剩余的人按从大到小排序，并用英文逗号分隔。

2、主函数 (main 方法):

读取输入的 m 值。
调用 solveJosephusProblem 方法解决问题。
根据结果输出相应的答案。
这样就可以正确地解决约瑟夫环问题，并按照要求输出结果。

您是对的，我之前的解释有误。让我重新解析一下当输入 m=80 时的运行过程。

代码运行示例

输入处理：
- 程序从控制台读取一个整数 m，这里 m=80。
- 检查 m 是否在有效范围内（即 1 < m < 100）。由于 m=80 在这个范围内，所以不会返回 "ERROR"。
初始化：
- 创建一个 LinkedList<Integer> 名为 people，用于存储从 1 到 100 的整数，代表 100 个人的编号。
- 初始化 current 变量为 0，表示当前报数的人的索引（但注意，这里的索引用于访问列表，而报数是从 1 开始的）。
循环移除：
- 当 people 列表中的人数大于等于 m 时，执行循环。
- 在每次循环中，计算要移除的人的索引：current = (current + m - 1) % people.size();。
  - 这里的计算方式确保了每次从当前索引开始，数到第 m 个人（考虑到索引从 0 开始，而报数从 1 开始，所以加了 m-1）。
  - 使用 % people.size() 是为了防止索引越界。
- 从 people 列表中移除计算出的索引位置的人。但这里并不是移除 80 个人，而是移除当前索引指向的那个人，其编号恰好是数到 m 时的那个人的编号（在初始情况下，可能是编号为 80 的人，但随着循环的进行，编号会变化）。
循环结束条件：
- 当 people 列表中的人数少于 m 时，循环结束。
结果处理：
- 创建一个 StringBuilder 名为 result，用于构建最终的结果字符串。
- 将 people 列表中剩余的人按编号从大到小添加到 result 中（尽管在这个特定问题中，由于每次移除的是当前数到 m 的那个人，所以剩余的人的顺序可能并不是严格按照从大到小或从小到大的，但在这个例子中，由于 m 较大，循环很快结束，所以留下的人基本上是按照初始顺序的）。不过，代码中的排序逻辑实际上是多余的，因为在这个问题中并不需要排序。
输出：
- 将 result 转换为字符串并输出。