约瑟夫环--使用顺序表解决、使用公式法解决

淩亂°似流年 2021-08-13 18:33 461阅读 0赞

### 约瑟夫环问题 ###

N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

### 使用顺序表求解 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]

package pers.zhang.linearList;
    
    /** * @author zhang * @date 2020/1/13 - 18:55 * * 使用顺序表求解约瑟夫环问题 */
    public class Josephus { 
        //创建约瑟夫环并求解，参数指定环长度、起始位置、计数
        public Josephus(int number, int start, int distance)
        { 
            SeqList<String> list = new SeqList<String>(number);
            //采用顺序表存储约瑟夫环的元素，元素类型是字符串，构造方法参数指定顺序表容量
            for (int i = 0; i < number; i++)
                list.append((char)('A' + i) + "");//添加字符串对象
            System.out.print("约瑟夫环(" + number + "," + start + "," + distance + ")，");
            System.out.println(list.toString()); //输出顺序表的描述字符串
    
            int i = start;//计数起始位置
            while (list.length() > 1)//多于一个对象时循环
            { 
                i = (i + distance - 1) % list.length();//计数按循环规律变化，顺序表可看作是环形结构
                System.out.print("删除" + list.remove(i).toString() + "，");  //删除指定位置对象
                System.out.println(list.toString());
            }
            System.out.println("被赦免者是" + list.get(0).toString());
        }
    
        public static void main(String args[])
        { 
            new Josephus(5,0,2);
        }
    }

测试结果：

约瑟夫环(5,0,2)，(A, B, C, D, E) 
    删除B，(A, C, D, E) 
    删除D，(A, C, E) 
    删除A，(C, E) 
    删除E，(C) 
    被赦免者是C

### 公式法 ###

递推公式：  
![在这里插入图片描述][20200113190629931.png]

*  f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号f(N−1,M)
 *  f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

推倒过程：

1.  第一个被删除的数位(m - 1) % n
2.  第二轮开始的数字为k，那么这n-1个数构成的约瑟夫环为k, k + 1, k + 2, …, k - 3, k - 2 （k-1已经退出）

现在做一个简单映射  
p(x) = (x - k) % n  
k —> 0  
k + 1 —> 1  
k + 2 —> 2  
…  
k - 2 —> n - 2  
这是一个n-1个人的约瑟夫环，如果能从n-1个人的问题的解退出n个人问题的解，从而得到一个递推公式，那么问题就解决了。

假如我们已经知道了n-1个人时，最后胜利者的编号为x，利用映射关系逆推，就可以得出n个人时，胜利者的编号为(x+k)%n。其中k=m%n。  
代入:

(x + k) % n <=>
    (x + (m % n)) % n <=> 
    (x % n + (m % n) % n) % n <=> 
    (x % n + m % n) % n <=>
    (x + m) % n

1.  第二个被删除的数为(m - 1) % n - 1
2.  假设第三轮的开始数字为o，那这n-2个数构成的约瑟夫环为o,o+1,o+2,…,o-3,o-2。继续做映射   
    p(x) = (y - o) % (n - 2)  
    o —> 0  
    o + 1 —> 1  
    o + 2 —> 2  
    …  
    o - 2 —> n - 3  
    这是一个n-2个人的问题。假设最后胜利者为y，那么n-1个人时，胜利者为(y+o)%(n-1)，其中o等于m%(n-1)。代入可得(y+m)%(n-1)

这是一个n-2个人的问题。假设最后胜利者为y，那么n-1个人时，胜利者为(y+o)%(n-1)，其中o等于m%(n-1)。代入可得(y+m)%(n-1)

f ( 1 ) = 0  
f ( i ) = ( f \[ i - 1 \] + m ) % i ; ( i > 1 )

**代码实现：**

public static int getJosephus(int n,int m)
        { 
           int p = 0;
           for(int i = 2;i <= n;i++)
           { 
               p = (p + m) % i;
           }
           return p + 1;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/6989397a874c48f591a3e182ea80956a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]: /images/20210813/cd24cd257ba14be3bb559d273094a017.png
[20200113190629931.png]: /images/20210813/4a3b54abc0ce45e4a0dd351263ae682e.png