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

约瑟夫问题

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 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

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就是最开始的编号
}