约瑟夫问题

发表于   |   分类于   |     |   本文总阅读量 次

最近面试遇到的一个算法：标号1-n的n个人首尾相接，1到3报数，报到3的退出，求最后一个人的标号。

思路：
1.把所有人先放入数组中，多出一个下标为0，所以size为n+1
2.当报到m的人，且dead不等于n-1时，此人退出游戏，这时候把数组中这个值置为0，报数从新开始
3.如果这个人报数等于m，并且已经死了n-1个人，说明当前这个人就是最后的一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class demo{
    public static void  main(String arg[])
    {   
        int arr[] = new int[101];//报数从1开始所以数组大小为n+1
        int n=100, m=3;
        int i;
        int dead = 0;   //表示已经死了多少人
        int num = 0;    //num模拟报数
        for (i = 1;i<= n; i++) {
            //开始时每个人都可以报数，为了能得到最后一个人的编号，我们让初始值为i下标
            arr[i] = i;
        }
        for (i = 1;; i++){
            if (i > n) {
                //如果大于总人数，我们就从头开始
                i = i%n;                 
            }
            if (arr[i] > 0){
                //如果当前这个人没有死，就报数
                num++;
            }
            if (m == num && dead != n-1){
                //如果当前这个人报的数等于m 并且没有已经死亡n-1个人
                num = 0;
                arr[i] = 0;
                dead++;
            } else if(m == num && dead == n-1){
                //如果这个人报数等于m，并且已经死了n-1个人，说明当前这个人就是最后的一个活着的了。
                System.out.print(arr[i]+"");
                break;
            }
        }
    }
}

热评文章