约瑟夫环

[xbox1994]

题目：

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

import java.util.Scanner;

public class Test {
static int n; //从屏幕输入固定的人数n;
static int[] people; //人的数组;

public static void main(String[] args) {
    System.out.println("请输入人数n：");
    Scanner input = new Scanner(System.in);
    n = input.nextInt();
    people = new int[n];
    //开始非3的数设置报数
    selectNoThreeToSet();
    //打印结果
    printResult();
}

//开始非3的数设置报数
private static void selectNoThreeToSet() {
    int notThreeCount = n, num = 1;      //不是3的个数，用来作为一个跳出循环的条件，当notThreeCount=1时，跳出循环，代表只剩一个了
    for (int i = 0; ; i++) {
        if (i == n)                //检索不是只遍历一次数组，需要循环遍历，当下标i自加到数组最后时，需要从0开始自加 ,多次遍历
        {
            i = 0;
        }
        if (people[i] != 3) {     //只有不为3的进行赋值
            if (num > 3)          //报号的数，循环123，如果大于3即4，重新从1开始
            {
                num = 1;
            }
            people[i] = num;
            if (num == 3)      //当只有报数为3时notThreeCount自减
            {
                notThreeCount--;
            }
            num++;              //如果一个同学报数成功，下一个需要加1（这里不考虑循环回1）
        }
        if (notThreeCount == 1) {
            break;
        }
    }
}

//打印结果
private static void printResult() {
    int t = 0;
    for (int i = 0; i < n; i++) {
        System.out.print(people[i] + "\t");
        if (people[i] != 3) {
            t = i;
        }
    }
    System.out.printf("\n最后剩下的数为原来第%d号的同学\n", t + 1);
}

}

public class Test {
public static int findSurvivor(int n, int m) {
List people = new ArrayList<>();
for (int i = 1; i <= n; i++) {
people.add(i); // 初始化列表，包含1到n的人
}

    while (people.size() > 1) {
        for (int j = 0; j < m - 1; j++) {
            people.add(people.remove(0));  // 移除第0个元素并添加到列表末尾
        }
        people.remove(0);  // 移除第0个元素，即报数到m的人
    }

    return people.get(0);  // 返回最后剩下的那个人的原始编号
}

public static void main(String[] args) {
    int n = 10;  // 人数
    int m = 3;   // 报数上限
    System.out.println("最后剩下的是原来第 " + findSurvivor(n, m) + " 号的人");
}

}