【面试干货】约瑟夫问题

本文主要是介绍【面试干货】约瑟夫问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

💖The Begin💖点点关注，收藏不迷路💖

约瑟夫问题 是一个经典的数学问题，描述如下：编号为1, 2, …, n的n个人按顺时针方向围坐一圈，从第1个人开始报数，报到3的人离开，然后再由下一个人重新报数，直到剩下最后一个人。

问题描述：

有 n 个人围成一圈，顺序排号。从第一个人开始报数（从 1 到 3 报数），凡报到 3 的人退出
圈子，问最后留下的是原来第几号的那位。

1、实现思想

约瑟夫环：约瑟夫环是一个数学问题，描述了一圈固定人数的人按照一定规则依次离开，直到只剩下最后一个人的过程。

模拟约瑟夫环的过程，通过标记数组来记录每个人是否还在圈内，并根据报数规则逐渐淘汰人，最终找到最后留下的人。

2、代码实现

package csdn;import java.util.Scanner; public class SequentialNumber { public static void main(String[] args) { // 主方法Scanner s = new Scanner(System.in); // 创建Scanner对象s，用于接收控制台输入System.out.print("请输入排成一圈的人数："); // 提示用户输入排成一圈的人数int n = s.nextInt(); // 从控制台读取输入的人数并存储在变量n中boolean[] arr = new boolean[n]; // 创建一个长度为n的boolean数组arr，用于标记人是否仍在圈内for(int i=0; i<arr.length; i++) { // 遍历数组arrarr[i] = true; // 初始化数组arr，所有人都在圈内，标记为true}int leftCount = n; // 记录剩余在圈内的人数int countNum = 0; // 报数变量，记录当前报的数int index = 0; // 数组下标，表示当前报数的人的位置while(leftCount > 1) { // 当剩余在圈内的人数大于1时循环if(arr[index] == true) { // 如果当前位置的人仍在圈内countNum ++; // 报数加一if(countNum == 3) { // 如果报数为3countNum = 0; // 重置报数arr[index] = false; // 将当前位置的人标记为false，表示离开圈子leftCount --; // 剩余在圈内的人数减一}}index ++; // 下标后移if(index == n) { // 如果下标超出数组长度index = 0; // 重置下标为0，实现循环}}for(int i=0; i<n; i++) { // 遍历数组arrif(arr[i] == true) { // 如果当前位置的人仍在圈内System.out.println("原排在第"+(i+1)+"位的人留下了。"); // 输出最后留在圈内的人的位置}}}
}

代码中使用了一个布尔类型的数组 arr 来表示每个人是否还在圈内，初始都在圈内，所以初始化为 true。接着进行循环报数并标记离开的人，直到剩下最后一个人。

在循环中，使用 index 变量来表示当前报数的人的位置，countNum 变量来记录当前报的数，leftCount 变量来记录剩余在圈内的人数。

当 countNum 累计到3时，将对应位置的人标记为离开圈子，然后 leftCount 减一，直到只剩下一个人为止。

最终输出留在圈内的最后一个人的位置。

💖The End💖点点关注，收藏不迷路💖

这篇关于【面试干货】约瑟夫问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---