原创

约瑟夫环问题分析以及代码实现(两种方式)


约瑟夫环问题


问题描述:让小朋友们围成一个大圈。然后,随机指定一个数 m,让编号为 0 的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续 0...m-1 报数 .... 这样下去 .... 直到剩下最后一个小朋友,可以不用表演。

 

这类问题可以看作是一个典型的约瑟夫环问题。

 

分析:例如有10个小朋友,随机指定数为3

                     0,1,2,3,4,5,6,7,8,9

第一次:       0,1,2,3,4,5,6,7,8,9       (下标为2的人出局,从下标为3的人开始重新计数)

第二次:       0,1,3,4,5,6,7,8,9

第三次:       0,1,3,4,6,7,8,9

第四次:       0,1,3,4,6,7,9

第五次:       0,3,4,6,7,9

第六次:       0,3,4,7,9

第七次:       3,4,7,9

第八次:       3,4,9     

第九次:       3,9

目前圈中只剩下一人,下标为3的小朋友,最终获得胜利。

 

如果有9个小朋友的情况呢?

                    0,1,2,3,4,5,6,7,8

第一次:       0,1,2,3,4,5,6,7,8      (下标为2的人出局,从下标为3的人开始重新计数)

第二次:       0,1,3,4,5,6,7,8

第三次:       0,1,3,4,6,7,8

第四次:       0,1,3,4,6,7

第五次:       0,1,4,6,7

第六次:       0,1,4,6

第七次:       0,1,6

第八次:       0,6

下标为0的小朋友获得最终胜利。

如果有8个小朋友呢?

                      0,1,2,3,4,5,6,7

第一次:        0,1,2,3,4,5,6,7

第二次:        0,1,3,4,5,6,7

第三次:        0,1,3,4,6,7

第四次:        1,3,4,6,7

第五次:        1,3,6,7

第六次:        3,6,7

第七次:        3,6

下标为6的小朋友获得胜利。

分析:

可以看出,当删除一个人后,最终的下标会相应的往前移动m位。当人数n=10时,最终的下标index = 3; 当人数n=9时,下标index会往前移动m=3为,也就是0。当人数n=8时,下标继续往前移动3位,但因为是环,所以最终下标在人数n=9的情况下往前移动三位,也就是index = 6。

同理,当人数为n-1时,index = F(n-1,m),人数为n时,index = F(n-1,m) 往后移动m位 ,也就是index = F(n-1, m) + m ,但因为是环的情况,所以我们需要对inde进行取模操作。

我们可以得出公式  F( n, m) = (F(n-1, m) + m) % n

在此,我们可以利用递归进行处理,递归结束条件为 n==1,return 0  (当仅有一个小朋友的时候,直接返回它对应的下标0),递归结束。


代码如下

方法一:

public int count1(int n,int m){
        if(n==0){
            return -1;
        }
        if(n==1){
            return 0;
        }
        
        return (count1(n-1,m)+m)%n;
    }

 

方法二:

public int count2(int n,int m){
        if(n==0){
            return -1;
        }
        
        int index = 0;
        for(int i=2;i<=n;i++){
            index = (index+m)%i;
        }
        
        return index;
    }

Java