约瑟夫环问题 Java 实现

约瑟夫环问题是一个经典的算法问题，描述了 n 个人围成一个环，从第 1 个人开始报数，报到 m 的人离开环形，从下一个人继续报数，直到最后剩下 p 个人。本篇文章将介绍如何使用 Java 语言实现约瑟夫环问题，并找出最终剩余的 p 个初始编号。

问题描述

有 n 个人编号为 1~n，排成一个环，从 1 号人开始从 1 到 m 报数，报到 m 的人离开该环，从下一个人开始继续从 1 到 m 报数，报到 m 的人离开该环，...，这样一直进行下去，直到最终剩余 p 个人。从键盘输入 n、m、p，要求 n>=2、m>=2、p

Java 实现

import java.util.ArrayList; 
import java.util.List; 
import java.util.Scanner; 
public class JosephusProblem {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入n的值：");
int n = scanner.nextInt();
System.out.print("请输入m的值：");
int m = scanner.nextInt();
System.out.print("请输入p的值：");
int p = scanner.nextInt();
    List<Integer> people = new ArrayList<>(); 
    for (int i = 1; i <= n; i++) { 
        people.add(i); 
    } 
    
    int index = 0; 
    while (people.size() > p) { 
        index = (index + m - 1) % people.size(); 
        people.remove(index); 
    } 
    
    System.out.println("最终剩余的" + p + "个初始编号为："); 
    for (int i = 0; i < p; i++) { 
        System.out.print(people.get(i) + " "); 
    } 
} 

}

代码解析

在上述代码中，我们首先从键盘输入 n、m、p 的值。然后创建一个 List 来存储初始编号。接下来，使用一个循环从 1 到 n 依次添加初始编号到 List 中。

然后，我们使用一个循环来模拟报数并移除相应的人员。在每一次循环中，我们计算出下一个要离开的人员的索引，然后从 List 中移除该人员。这里使用了取模运算符来处理环形队列。

最后，我们输出剩余的 p 个初始编号。

总结

本文介绍了如何使用 Java 语言解决经典的约瑟夫环问题。代码简洁易懂，可以帮助您理解约瑟夫环问题的原理和实现方法。