Solving Josephus Problem in Java

2025年5月7日 | 阅读7分钟

约瑟夫问题是一个与特定淘汰游戏相关的理论问题。它以犹太历史学家弗拉维乌斯·约瑟夫斯的名字命名，据说他创造了这种方法来逃避围攻期间的追捕。

问题陈述

n 个人围成一圈站立，编号从 1 到 n。
从给定的位置开始，每隔 k 个人被淘汰出局。
这个过程一直持续到只剩一个人为止。
任务是找出最后一个幸存者的位置。

示例 1

输入: n = 6, k = 4

输出 5

解释: 位置为 4、1、5、2 和 6 的人按顺序被杀死，位置为 3 的人幸存。

示例 2

输入: n = 10, k = 3

输出 4

解释: 位置为 3、6、9、2、5、8、1、7 和 10 的人按顺序被杀死，位置为 4 的人幸存。

方法：使用列表

约瑟夫问题可以通过使用列表来模拟淘汰过程来解决。人员存储在列表中，在每次迭代中，直到只剩一个人，都会移除计算出的索引处的人。

算法

步骤 1: 初始化一个包含从 1 到 n 的人员的列表，其中每个元素代表圈中的一个人。

步骤 2: 将起始索引设置为 0，表示圈中的第一个人。

步骤 3: 迭代直到列表大小大于 1:

使用以下公式计算要淘汰的人的索引
index = (index + k - 1) % current list size，其中 k 是步数。
从列表中移除索引处的人。

步骤 4: 每次淘汰后更新列表大小，并继续该过程，直到只剩一个人。

步骤 5: 从列表中返回最后剩下的人，这就是安全位置。

实施

文件名: JosephusProblemList.java

import java.util.ArrayList; 
import java.util.List; 
public class JosephusProblemList {
    // Method to solve the Josephus problem using a list
    public static int josephus(List<Integer> people, int k) {
        int index = 0;
        // Loop until only one person remains in the list
        while (people.size() > 1) {
            // Calculate the next index to be eliminated using (index + k - 1) % people.size()
            // (k - 1) because we need to skip k-1 people before elimination
            index = (index + k - 1) % people.size();
            // Remove the person at the calculated index from the list
            people.remove(index);
        }
        // Return the last remaining person (1-based index) from the list
        return people.get(0);
    }
    public static void main(String[] args) {
        // Default input: number of people in the circle
        int n = 5;  // Total number of people in the circle
        // Default input: step count for elimination
        int k = 2;  // Every 2nd person is eliminated
        // Initialize a list to hold people from 1 to n (1-based index)
        List<Integer> people = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            people.add(i);  // Add person i to the list
        }
        // Call the josephus method to find the safe position
        int safePosition = josephus(people, k);
        // Print the safe position (1-based index)
        System.out.println("The safe position is: " + safePosition);
    }
}  

输出

 
The safe position is: 3

时间复杂度: O(n²)

辅助空间复杂度: O(n)

使用迭代方法

解决约瑟夫问题的迭代方法通过迭代更新圈中每个人的位置来计算安全位置。它避免了递归，并使用单个循环直接计算结果，从而实现了线性的时间复杂度和恒定的空间使用。

算法

初始化安全位置为 0（0 基索引），假设只有一个人留下。
从 2 迭代到 n（总人数）
- 使用以下公式计算新的安全位置
- safePosition = (safePosition + k) % i，
- 其中 i 是当前人数。
在每次淘汰步骤后更新安全位置，基于步数 k。
继续该过程，直到除一人外所有人都被淘汰。
将安全位置转换为 1 基索引（加 1）并将其作为结果返回。

实施

文件名: JosephusProblemIterative.java

public class JosephusProblemIterative {
    // Method to solve the Josephus problem iteratively
    public static int josephus(int n, int k) {
        // Initialize the safe position when there is only 1 person (0-based index)
        int safePosition = 0;
        // Iterate from 2 to n to calculate the safe position for each circle size
        for (int i = 2; i <= n; i++) {
            // Update the safe position based on the step size and current number of people
            // (safePosition + k) % i adjusts the safe position after each elimination
            safePosition = (safePosition + k) % i;
        }
        // Convert the result from 0-based index to 1-based index and return
        // Adding 1 because the problem typically requires a 1-based index
        return safePosition + 1;
    }
    public static void main(String[] args) {
        // Default input: number of people in the circle
        int n = 5;  // Total number of people in the circle
        // Default input: step count for elimination
        int k = 2;  // Every 2nd person is eliminated
        // Call the josephus method to find the safe position (1-based index)
        int safePosition = josephus(n, k);
        // Print the final safe position (1-based index)
        System.out.println("The safe position is: " + safePosition);
    }
}   

输出

 
The safe position is: 3

时间复杂度: O(n) 循环从 2 到 n 运行，内部执行常数时间操作。

辅助空间复杂度: O(1) 该算法只使用几个整数变量（safePosition、i），需要恒定的空间。

约瑟夫问题：线性时间和恒定空间

约瑟夫问题：线性时间和恒定空间，通过迭代计算安全位置，使用公式 (safePosition + k) % i 随步数更新位置。这种方法无需递归，即可实现 O(n) 的时间复杂度和 O(1) 的辅助空间。

算法

步骤 1: 初始化安全位置为 0，假设只有一个人留下（0 基索引）。

步骤 2: 从 2 迭代到 n（圈中的总人数）

使用以下公式计算新的安全位置：safePosition=(safePosition+k)%i

其中 i 是当前圈的大小。

步骤 3: 每次迭代后更新安全位置，以考虑被淘汰的人。

步骤 4: 继续直到循环达到 n，以找到所有 n 个人的安全位置。

步骤 5: 通过加 1 将安全位置转换为 1 基索引，并将其作为最终结果返回。

实施

文件名: JosephusProblemConstantSpace.java

public class JosephusProblemConstantSpace {
    // Method to solve the Josephus problem in linear time and constant space
    public static int josephus(int n, int k) {
        // Initialize the safe position when there is only 1 person (0-based index)
        int safePosition = 0;
        // Loop from 2 to n to calculate the safe position for n people
        for (int i = 2; i <= n; i++) {
            // Update the safe position for the current number of people
            // (safePosition + k) % i gives the new safe position after eliminating a person
            safePosition = (safePosition + k) % i;
        }
        return safePosition + 1;
    }
    public static void main(String[] args) {
        // Default input: number of people in the circle
        int n = 5;  // Total number of people in the circle
        // Default input: step count for elimination
        int k = 2;  // Every 2nd person is eliminated
        // Call the josephus method to find the safe position
        int safePosition = josephus(n, k);
        // Print the safe position (1-based index) as the output
        System.out.println("The safe position is: " + safePosition);
    }
}   

输出

 
The safe position is: 3

时间复杂度：O(n)

辅助空间复杂度: O(1)

约瑟夫问题：递归

约瑟夫问题：递归通过逐一减少圈中的人数来解决问题，计算 n-1 个人的安全位置，并根据淘汰步数 k 调整结果。递归公式为 josephus(n - 1, k) + k) % n，它在每次淘汰后找到新的安全位置。

算法

步骤 1: 如果只有一个人（n = 1），则返回 0（安全位置是第一个人）。

步骤 2: 调用函数 josephus(n - 1, k) 来查找 n - 1 个人的安全位置。

步骤 3: 使用公式 (josephus(n - 1, k) + k) % n 在一个人被淘汰后调整位置。

步骤 4: 返回 n 个人的安全位置。

步骤 5: 将结果从 0 基索引转换为 1 基索引（加 1），并打印安全位置。

实施

文件名: JosephusProblemRecursion.java

public class JosephusProblemRecursion {
    // Recursive method to solve the Josephus problem
    public static int josephus(int n, int k) {
        if (n == 1) {
            return 0;
        }
        // Recursive case: Calculate the safe position for (n-1) people
        // Adjust the result using (josephus(n-1, k) + k) % n
        // This step finds the new safe position after eliminating one person
        return (josephus(n - 1, k) + k) % n;
    }
    public static void main(String[] args) {
        // Default input: number of people in the circle
        int n = 5;  // Total number of people in the circle
        // Default input: step count for elimination
        int k = 2;  // Every 2nd person is eliminated
        // Call the josephus method to find the safe position (0-based index)
        int safePosition = josephus(n, k);
        // Print the final safe position (1-based index)
        System.out.println("The safe position is: " + (safePosition + 1));
    }
}   

输出

 
The safe position is: 3

时间复杂度：O(n)

辅助空间复杂度: O(n)

下一个主题Java 中的素数和

← 上一个下一个 →

Solving Josephus Problem in Java

问题陈述

方法：使用列表

算法

实施

使用迭代方法

算法

实施

约瑟夫问题：线性时间和恒定空间

算法

实施

约瑟夫问题：递归

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Solving Josephus Problem in Java

问题陈述

方法：使用列表

算法

实施

使用迭代方法

算法

实施

约瑟夫问题：线性时间和恒定空间

算法

实施

约瑟夫问题：递归

算法

实施

相关帖子

Java 中查找二叉搜索树中的中序后继

How to build a Web Application Using Java

Java Map 泛型

Reader read(CharBuffer) Method in Java with Examples

Java double keyword

Java 中 IntSummaryStatistics getCount() 方法及示例

PermGen space Java

Java Program to Tile a Page Content in a PDF

Java 中的 DAO 类

Java 中的命令模式

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器