约瑟夫问题(数学解法及数组模拟)

古城微笑少年丶 2022-05-28 03:38 106阅读 0赞

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 以上来自百度百科

约瑟夫问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

约瑟夫问题其实并不难，但求解的方法多种多样；题目的变化形式也很多。接下来我们来对约瑟夫问题进行讨论。

**1.**模拟解法 优点 : 思维简单 。 缺点：时间复杂度高达O(m\*n) 当n和m的值较大时，无法短时间内得到答案。

为了叙述的方便 我们将n个人编号为：1- n ，用一个数组vis来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人数 cnt 代表当前报了数的人数 用t来枚举每一个位置(当t>n时 t=1将人首尾相连) 那么我们不难得出核心代码如下：

bool vis[1000]; //标记当前位置的人的存活状态
    int t = 0; //模拟位置
    int s = 0; //死亡人数
    int cnt = 0; //计数器
    do{
        ++t;
        if(t > n) t = 1;
        if(!vis[t]) cnt++; //如果这里有人,计数器+1
        if(cnt == m) //如果此时已经等于m,这这个人死去
        {
            cnt = 0; //计数器清零
            s++; //死亡人数+1
            vis[t] = 1 //标记这个位置的人已经死去
            cout<<t<<" "; //输出这个位置的编号
        }
    }while(s != n);

接下来我们来看另一种更为高效快速的解法 **数学解法**

我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最初的编号是多少？ 我们只需要将最后求得的解加1就能得到原来的编号。

**我们先给出****递推公式：**

*f*(*N*,*M*)=(*f*(*N*−1,*M*)\+*M*)%*N*

f(N,M)=(f(N−1,M)+M)%N

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

接下来 我们开始进行解释

事实上，每次报到m-1的人出列以后，剩余的n-1个人又会组成新的约瑟夫环。

我们现在假设有11个人

依次编号为 1、2、3、4、5、6、7、8、9、10、11

假设每次报到3的人死去

刚开始时，第一个人开始报数，第一轮死去的人是3号。

编号为4的人又从1开始报数，这时编号为4的人是这个队伍的头，则第二轮死去的人是6号。

编号为7的人又从1开始报数，这时编号为7的人是这个队伍的头，则第三轮死去的人是9号。

......

第九轮时，编号为2的人开始重新报数，这时我们认为编号为2的人是这个队伍的头，这一轮死去的人是8号。

现在还剩下编号为2和7的两个人，编号为2的人从1开始报数，不幸的是这一轮他死去了

最后7号玩家活了下来

*  *f*(1,3)：只有1个人了，他就是幸存者，他的下标位置是0
 *  *f*(2,3) = (*f*(1,3)+3)%2 = 3%2 = 1 ，还有2个人的时候，幸存者的下标位置为1
 *  *f*(3,3) = (*f*(2,3)+3)%3 = 4%3 = 1，还有3个人的时候，幸存者的下标位置为1
 *  *f*(4,3) = (*f*(3,3)+3)%4 = 4%4 = 0，还有4个人的时候，幸存者的下标位置为0
 *  ……
 *  *f*(11,3) = 6

是不是觉得很神奇呢？你还在质疑这个公式的正确性吗？

我们来看这个公式如何得到的呢？

**1.**假设我们已经知道在第一轮还剩11个人时，幸存者的下标位置是6。那么下一轮剩10个人的时候，幸存者的下标位置是多少呢？

聪明的你是否已经想到了呢？没错，下一轮这个幸存者的下标位置变为了3，其实，在第一轮编号为3的人死去了以后，因为下一轮是从下标位置为4号的人开始报数，那么其实第一轮在3号死去了以后，相当于每个人的位置都往前移动了3位。

**2.**假设我们已经知道在还剩10个人的时候，幸存者的下标位置为3。那么上一轮11个人的时候，幸存者的编号是多少呢？

其实这个问题可以看成是上一个问题的逆过程，相当于大家都往后移动了3位，所以*f*(11,3)=*f*(10,3)+3，但是一直累加的话，人数可能会超过总人数，所以最后模上当前人数的个数，每死去一个人，下一个人成为第一个报数的人，就相当于把环向前移动了M位。若已知N-1个人时，幸存者的下标位置为*f*(*N*−1,*M*)，则剩下N个人的时候，就是往后移动M位，(因为有可能人数越界，超过的部分会被接到头上（**因为是一个环**），所以还要模上N)，则可以得到递推公式f(N,M) = (f(N−1,M)+M)%n

理解这个递推公式的关键在于关注幸存者的下标位置是怎么变化的。每死去一个人，其实就是把这个环向前移动了M位。然后逆过来，就可以得到这个递推式。

由此 我们给出代码:

int ring(int n,int m)
    {
        int p = 0; //幸存者在最后一轮的编号是0
        for(int i = 2; i <= n; i++)
        {
            p = (p+m)%i; //i代表当前人数
        }
        return p+1; //最后的下标+1就是最开始的编号
    }