Josephus约瑟夫问题及其变种

蔚落 2022-08-14 01:54 256阅读 0赞

**问题由来：**

在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第*k*个人。接着，再越过k-1个人，并杀掉第*k*个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

**一般形式：**

N个人围成一个圈，编号为1到N，**从1号开始报数**，报数为M的人出局；其他人继续围成圈，从出局人的下一个开始重新报数，报到M的人又出局。直到剩下最后一个人。

可以用数组或者链表来模拟这个报数的过程，如下是数组实现的C++代码：

const int maxn = 10000;
    void ArrayJose() {
    	bool jose[maxn] = {0};   //设置一个数组来模拟N个人
    	int m_count = 0; //记录当前报的数
    	int i = 0;  //记录当前遍历的是数组的第几个元素
    	int out_count = 0; //记录当前出局的人数
    	int n, m;
    	cin >> n >> m;
    	do 
    	{
    		++i;
    		if (i > n)    //所有人报数完后从头开始报数
    			i = 1;
    		if (!jose[i])  //若数组元素为0，即这个人没出局
    			m_count++;
    		if (m_count == m) {  //报数为m的人出局
    			m_count = 0;      //重新开始报数
    			cout << i << " "; //输出出局人编号
    			jose[i] = 1;      //将这个人所在位置标记为出局：1
    			out_count++;      //出局人数加1
    		}
    	} while (out_count != n);
    }

以下是C++的循环单链表方式：

struct Node;
    typedef struct Node *PtrToNode;
    typedef PtrToNode List;
    typedef PtrToNode Position;
    
    struct Node {
            int element;
            Position next;
    };
    
    List MakeCircleList(int n) {
        List jose = NULL;
        int i = 0;
        Position node, rear;
        for (i = 1; i <= n; i++) {
            node = (struct Node *)malloc(sizeof(struct Node));
            if (node == NULL) {
                cout << "malloc failed." << endl;
                return NULL;
            }
            node->element = i;
            if (jose == NULL) {
                jose = node;
            }
            else {
                rear->next = node;
            }
            rear = node;
        }
        rear->next = jose;
        return jose;
    }
    
    void CircleListJose(int n, int m, List jose) {
        int m_count = 0, out_count = 0;
        int i;
        Position q, p = jose;
        q = p;
        while (p->next != p) {
            for (i = 1; i < m; ++i) {
                q = p;
                p = p->next;
            }
            Position start = p->next;
            cout << p->element << " ";
            q->next = p->next;
            free(p);
            p = start;
        }
        cout << p->element << endl;
    }

以上的两种方式的思想都是一样的：要模拟所有人报数并出局的整个过程。这种思想的复杂度比较大，为 **O(mn)**。通过数学方式可以提高算法的效率。可以将 问题描述改为： n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

注意这里的方法没有将每次报数人的编号计算出来，而是仅仅求出了胜利者的编号，下面算法的**复杂度为O(n)**。

当第一个人出列后（这个人的编号一定是（m - 1）% n，剩下的n - 1 个人重新构成了一个新的约瑟夫环（这个环以k = m % n开始报数）：

k，k+1，k+2，……，n-2，n-1，0，1，……，k-2。

将这n-1个人依次重新编号为0，1，2，……，n-1：

k ---> 0，

k+1 ---> 1，

k+2 ----> 2，

……

k-2 ---> n - 2

即转换映射为 x ---> (n + x - k - 1) % n == (x - k - 1) % n，反向的转换关系为： x <--- (x + k + 1 - n) % n == (x + k + 1) % n

这些人**继续从0号开始报数**，那么，如果这n-1个人子问题的最后胜利者编号为f(n)。如果设n个人时胜利者编号为f(n - 1)的话，那么可以得到递推关系式：

f(n) = (f(n - 1) + k + 1) % n; 将 k = （m - 1）% n 代入， f(n) = ( f(n - 1) + (m - 1) % n + 1) % n = ( f(n - 1) + m) % n

也就是说，如果求得了n-1个人的胜利者根据递推关系式就可以求得n个人的胜利者，那么n-1个人的胜利者就通过求n-2个人的胜利者来求，因此这是递归过程。

解f(1) = 0; f(i) = (f(i - 1) + m) % i;(i > 1) 。这里的f(i)表示的是胜利者的编号。

代码实现如下：

int main(void)  
    {  
        int n, m,i, f[20]={0};  
        scanf("%d %d",&n,&m);  
        for(i=2;i<=n;i++)  
        {  
            f[i]=(f[i-1]+m)%i;  
            printf("%d个人报数，报到%d的出列，最后的胜者下标为%d\n", i,m,f[i]);  
        }  
        printf("The winner is %d\n", f[n]+1);  
        system("pause");  
    }

优化后代码：

int main(void)  
    {  
        int n, m,i, s=0;  
        scanf("%d %d",&n,&m);  
        for(i=2;i<=n;i++)  
        {  
            s=(s+m)%i;  
        }  
        printf("The winner is %d\n", s + 1);  
    }

\-----------------------------------------------------------------------分割线-----------------------------------------------------------------------------------

注意以下使用的变量含义与上述没必要联系。

一道ACM的约瑟夫变形题：

Description

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.  
  
Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

Sample Input

3
    4
    0

Sample Output

5
    30

一共2k个人，前k个人为好人，后k个人为坏人，要求选择m，使得所有坏人被杀前不能误杀好人。

设第0轮仇杀人编号为0，即f\[0\] = 0，第i轮抽杀人的编号为f\[i\] = (f\[i - 1\] + m - 1) % (2k - (i - 1));(i > 0)。

设置一个大小为14的int数组，用来存仇杀递推数组，因为抽杀的递推公式计算时需要前一次的数据。然后读入一个k，初始化抽杀数字为m = k + 1，因为之前的数字第一次抽杀好人，不符合规定，直接略过。用m抽杀一轮，如果f\[i\] < k，说明好人被杀，直接m++重新抽杀。如果k轮仇杀都没有杀死好人，则这个m就是符合要求的，输出m。

#include <iostream>  
        using namespace std;  
        int main()  
        {  
            int k = 0,joseph[14] = {0}, ans[14] = {0};  
            while (cin >> k) {  
                if (k == 0) break;  
                if (ans[k]) {              //如果读入的k对应的m已经计算出来，就直接打印
                    cout << ans[k] << endl;  
                    continue;  
                }  
                int n = 2 * k, m = k + 1;  
                for (int i=1; i<=k; i++) {  
                    joseph[i] = (joseph[i-1] + m - 1) % (n - i + 1);  //递推关系，第i轮杀死的人
                    if (joseph[i] < k) {  //如果第i轮杀死的人是好人则m直接加1，重新开始计算
                        i=0;  
                        m++;  
                    }  
                }  
                ans[k] = m;            //记录符合要求的m并输出
                cout << m << endl;  
            }  
            return 0;  
        }

或者对于0到14之间的k，将符合要求的所有m都计算出来，存入数组，然后输入一个k就从数组中找到对应的结果即可：

int main()  
    {  
        int k;  
        int ans[20];
        int Joseph[20]={0};
        for(k=1;k<14;k++)  
        {  
            int m=1;  
            memset(ans,0,sizeof(Joseph));  
            for(int i=1;i<=k;i++)  
            {  
                Joseph[i]=(Joseph[i-1]+m-1)%(2*k-i+1); //递推公式  
                if(Joseph[i] < k)  
                {  
                    i=0;  
                    m++;  
                }  
            }  
            ans[k]=m;  
        }  
      while(scanf("%d",&k)&&k!=0)  
       {  
           printf("%d\n",ans[k]);  
       }  
       return 0;  
    }

\--------------------------------------------------------------分割线-------------------------------------------------------------

另一种变形题是：n个人围成圈，每个人持有一个正数密码，依次报数，报数为m的人出局；将m的值设置为出局人的密码，从出局人的下一个人重新报数，报到该密码的人出局，依次循环；直到剩下最后一人。

该问题目前没有好的解法，只能用开始介绍的循环单链表进行遍历，只是每次出局时m的值要重新设置，单路表节点使用如下的结构体：

struct Node {
                int element;   //人员编号
                int key;  //密码
                struct Node *next;
    };