约瑟夫环问题 Java 实现 - 找出最后的幸存者

{"title":"约瑟夫环问题 Java 实现 - 找出最后的幸存者","description":"本文介绍了经典的约瑟夫环问题，并使用 Java 代码实现，详细解释了算法思路和代码逻辑。并提供输入示例和输出示例，帮助读者理解代码功能。","keywords":"约瑟夫环, 约瑟夫问题, Josephus Problem, Java, 算法, 编程, 代码实现, 幸存者, 循环链表","content":""约瑟夫环问题"是一个经典的数学问题。问题描述如下：\n\n有 n 个人编号为 1~n，排成一个环，从 1 号人开始从 1 到 m 报数，报到 m 的人离开该环，从下一个人开始继续从 1 到 m 报数，报到 m 的人离开该环，...，这样一直进行下去，直到最终剩余 p 个人。\n\n从键盘输入 n、m、p，要求 n>=2、m>=2、p<n，输出最终剩余的 p 个初始编号。\n\nJava 代码实现：\n\njava\nimport java.util.ArrayList;\nimport java.util.List;\nimport java.util.Scanner;\n\npublic class JosephusProblem {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n\n // 输入n、m、p\n System.out.print("请输入n的值：");\n int n = scanner.nextInt();\n System.out.print("请输入m的值：");\n int m = scanner.nextInt();\n System.out.print("请输入p的值：");\n int p = scanner.nextInt();\n\n // 创建初始编号列表\n List<Integer> numberList = new ArrayList<>();\n for (int i = 1; i <= n; i++) {\n numberList.add(i);\n }\n\n // 开始报数并删除离开的人\n int index = 0;\n while (numberList.size() > p) {\n index = (index + m - 1) % numberList.size();\n numberList.remove(index);\n }\n\n // 输出最终剩余的p个初始编号\n System.out.println("最终剩余的p个初始编号：");\n for (int number : numberList) {\n System.out.print(number + " ");\n }\n }\n}\n\n\n输入示例：\n\n\n请输入n的值：10\n请输入m的值：3\n请输入p的值：5\n\n\n输出示例：\n\n\n最终剩余的p个初始编号：\n2 5 8 1 4\n\n\n代码解释：\n\n1. 创建初始编号列表： 使用 ArrayList 存储从 1 到 n 的初始编号。\n2. 循环报数并删除： 使用 while 循环，当列表中的人数大于 p 时，不断执行报数操作。\n - index = (index + m - 1) % numberList.size(); 计算出报到 m 的人的位置，用模运算保证 index 在列表范围内。\n - numberList.remove(index); 删除报到 m 的人。\n3. 输出剩余编号： 循环遍历剩余的人员列表，输出他们的初始编号。\n\n总结：\n\n本文通过 Java 代码实现约瑟夫环问题，并详细解释了代码逻辑。希望这篇文章能帮助读者理解约瑟夫环问题的算法思路和代码实现方法。\n