算法设计 约瑟夫环问题

Question

有n个人编号为1~n，排成一个环，从1号人开始从1到m报数，报到m的人离开该环，从下一个人开始继续从1到m报数，报到m的人离开该环，这样一直进行下去，直到最终剩余p个人。输出最终剩余的p个初始编号。

Answer 1

import java.util.ArrayList;
import java.util.List;

public class Circle {
    public static void main(String[] args) {
        int n = 5, m = 3, p = 2; // n为人数，m为报数的数字，p为最终剩余的人数
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        while (list.size() > p) {
            int index = (int) (Math.random() * list.size()); // 随机选择一个下标
            int num = list.get(index); // 取出该下标对应的编号
            if (num % m == 0) { // 如果该编号能被m整除，则将其从列表中删除
                list.remove(index);
            } else { // 否则将该编号加1后重新插入列表中
                int nextNum = num + 1;
                if (nextNum % m == 0) {
                    nextNum++;
                }
                list.set(index, nextNum);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (list.contains(i)) { // 如果该编号在列表中，则输出该编号
                System.out.print(i + " ");
            }
        }
    }
}