约瑟夫问题-Josephus--及实例说明

类似约瑟夫的问题又称为约瑟夫环。又称“丢手绢问题”。

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

　　约瑟夫问题是个有名的问题，比如6个人围一个圈，从第一个人开始123123的报数，最后一个报完了循环到第一个继续报数，报到数字3的人就退出游戏。这样退出的顺序就是： 3    6    4    2    5，最后剩下1一个人。

解决问题：

　　就像题中描述的一样直接翻译成代码是(拯救约瑟夫的代码):

 #include<iostream>
 using namespace std;
 const int maxn = 1e6 + ;
 main()
 {
     bool a[maxn] = {};
     int n, m, i, f = , t = , s = ;
     cin >> n >> m;
     do
     {
         ++t;//逐个枚举圈中的所有位置
         if(t > n)
             t = ;//数组模拟环状，最后一个与第一个相连
         if(!a[t])
             s++;//第t个位置上有人则报数
         if(s == m)//当前报的数是m
         {
             s = ;//计数器清零
             cout << t << " ";//输出被杀人编号
             a[t] = ;//此处人已死，设置为空
             f++;//死亡人数+1
         }
     }
     while(f != n - m + );//直到死亡得剩下他们两个人为止
     cout << "\n死亡人数:" << f << " " << endl;
 //最后就剩下16和31没有被杀
 }

　　考虑到时间复杂度的问题，我们有下面一种改良的做法（约瑟夫递推算法）：　　　　

　　为了讨论方便，先把问题稍微改变一下，并不影响原意：

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

 题解：我们知道第一个人（编号一定是（m-1）) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k = m mod n的人开始报0继续计数）。

这样我们就可以写出递推公式:

　　f[1]=0;

　　f=(f+m) mod i; (i>1）

代码展示:

 #include <iostream>
 #include <cstdio>
 using namespace std;
 //一圈一圈的循环的来回的转，最后剩一个人
 int main() {
     int n, m, f = ;
     cin >> n >> m;
     for (int i = ; i <= n; i++) f = (f + m) % i;
     cout << f +  << endl;
     //输出最后活着的一个人.
     return ;
 }

猴子选王

　　题意：一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

解题思路<肯定比百度上面丰富>：

①、单向循环链表实现：

 #include <stdio.h>
 #include <malloc.h>
 #define LEN sizeof(struct monkey)//定义structmonkey这个类型的长度
 struct monkey
 {
     int num;
     struct monkey *next;
 };
 struct monkey *create(int m)
 {
     struct monkey *head, *p1, *p2;
     int i;
     p1 = p2 = (struct monkey*)malloc(LEN);
     head = p1;
     head->num = ;
     for(i=, p1->num = ; i < m; i++)
     {
         p1 = (struct monkey*)malloc(LEN);
         p1->num = i + ;
         p2->next = p1;
         p2 = p1;
     }
     p2->next = head;
     return head;
 }
 struct monkey *findout(struct monkey *start, int n)
 {
     int i;
     struct monkey *p;
     i = n;
     p = start;
     for(i = ; i < n - ; i++)
         p = p->next;
     return p;
 }
 struct monkey *letout(struct monkey *last)
 {
     struct monkey *out, *next;
     out = last->next;
     last->next = out->next;
     next = out->next;
     free(out);
     return next;
 }
 int main()
 {
     int m, n, i, king;
     struct monkey *p1, *p2;
     printf("请输入猴子的个数m:\n");
     scanf("%d", &m);
     printf("每次数猴子的个数n:\n");
     scanf("%d", &n);
     if(n == )
     {
         king=m;
     }
     else
     {
         p1 = p2 = create(m);
         for(i = ;i < m; i++)
         {
             p2 = findout(p1, n);
             p1 = p2;
             p2 = letout(p1);
             p1 = p2;
         }
         king = p2->num;
         free(p2);
     }
     printf("猴王的编号是：%d\n", king);
     return ;
 }

单向链表的尾节点的下一个练到头节点上，这样实现循环，然后就判断删除即可。

②、数组模仿链表--有点并查集的思想：

 #include<stdio.h>
 #include<malloc.h>
 int main()
 {
     int *monkey, i, node, n, m;
     scanf("%d%d",&n, &m);
     monkey = (int*)malloc(sizeof(int)*(n+));
     for(i=;i<=n;i++)//初始化圈
     {
         monkey[i] = i + ;//i表示编号为i的猴, monkey[i]的值表示编号为i的猴的下一个猴的编号
     }
     monkey[n] = ;//编号为n的下一个猴的编号是1
     node = ;
     printf ("The murdered monkey are:\n");
     while(node != monkey[node])//当这个圈中只剩下一个猴的时候跳出循环.
     {
         for(i = ; i < m - ; i++)    //找出念m的那只猴
         {
             node = monkey[node];
         }
         printf("%d ", monkey[node]);//输出退出的猴编号
         monkey[node] = monkey[monkey[node]];//修改退出的前一个猴的monkey[node]为退出的后一个猴的编号
         node = monkey[node];//这句话中的node是退出的猴的后一个猴
     }
     printf("\nThe king is:\n%d\n", node);//输出最终大王的的编号
     return ;
 }

创建数组的时候下标从1开始填数，1上面填2,2上面填3，...，最后n上面填1，这样达到循环的效果，然后以monkey[i] = i;为条件进行猴子的出队操作。

③、数组实现：

 //猴子选大王问题（约瑟夫环问题）
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 /*
  *
  * 屏蔽的代码部分为测试使用.
  * 为使删除的过程更加明确.
  *
  */
 int fre (char mok[],int k)
 {
     int i;

     /*printf("\n猴子编号：\n");
     for(i = 0; mok[i] != '\0'; i++)
         printf("%d\t", mok[i]);//输出为踢出之前的编号，测试用
     */

     for(i = k; mok[i] != '\0'; i++)
     {
         mok[i] = mok[i+];
     }//一个循环，将k以后的元素前移

     /*putchar('\n');
     for(i = 0; mok[i] != '\0'; i++)
         printf("%d\t", mok[i]);//输出踢出之后的编号，测试用
     printf("\n按回车继续下一轮:\n");
     system ("pause");    //暂停，测试使用。
     */

     return ;
 }
 int main()
 {
     char mok[];
     int i;
     int n, s, b;//n表示猴子总数；s表示步进；b表示元素个数及大王编号
     int j, k;//j,k都是计数器
     mok[] = ;//初始化mok[0],让后面编号更简单的进行
     printf("请输入猴子的总数：\n");
     scanf("%d", &n);//输入猴子的总数
     for(i = ; i < n; i++)
     {
         mok[i] = i + ;
     }//对猴子进行编号
     mok[n] = '\0';//用0来表示数组的结尾
     printf("请输入循环单位：\n");
     scanf("%d", &s);//单位长度
     b = n;//统计猴子的个数
     for(j = , k = ;;j++,k++)
     {
         if(b == )
         {
             b = mok[];
             break;
         }//如果元素只剩下一个，那么退出循环
         if(j == s)
         {
             //printf("\n它出列了：%d\n", mok[k]); //测试用
             fre(mok, k);//用于元素前移的函数
             b--;
             j = ;
         }//将猴子从数组中踢出，并重置计数器J。

         //--------------------------------------当删除的是最后一个数字时另行考虑.

         if (mok[k] == '\0')
             j--;

         //---------------------------------------

         if(mok[k+] == '\0')
             k=-;//重置计数器k，因为后面有k++所以k要在重置基础上-1.
     }//判断是否为数组最后元素，重置计数器k。
     printf("\n最终大王是他：%d\n", b);
     return ;
 }

只是使用一个数组，然后单独定义下标和计数器解决问题。

④、约瑟夫数学算法：

 #include <stdio.h>
 #include <conio.h>
 int main(void)
 {
     int n, i = , m, p;
     scanf("%d%d", &n, &m);//n总人数，m步长
     while(++i <= n)
     {
         p = i * m;
         while(p > n)
             p = p - n + (p - n - ) / (m - );
         printf("%d ", p);
     }
     getch();
     return ;
 }

寻找m和n之间的关系，初学者可以不掌握这种算法。

⑤、约瑟夫递推算法：

 #include <bits/stdc++.h>
 using namespace std;
 int king(int M,int N)
 {
     int k=;
     for(int i = ;i <= M; i++)
         k = (k + N) % i;
     return ++k;
 }
 int main()
 {
     int n, m;
     while (scanf("%d%d",&n, &m) && n && m)
     {
         cout << king(n, m) << endl;
     }
     return ;
 }

寻找删除的时候的规律，利用递推关系写出递推式，很轻松的解决问题。

⑥、双向链表实现：

 #include <stdio.h>
 #include <malloc.h>
 #include <stdlib.h>
 struct node {
     int data;
     struct node *prior, *next;
 };
 struct node *creat (int n, struct node *h) {
     h = NULL;
     struct node *s, *q;
     for (int i = ; i <= n; ++i) {
         s =  (struct node *)malloc(sizeof (struct node));
         s->data = i;
         s->next = NULL;
         if (h == NULL) {
             h = s;
             s->prior = h;
             s->next = h;
         } else {
             s->next = q->next;
             q->next = s;
             s->prior = q;
             h->prior = s;
         }
         q = s;
     }
     return h;
 }
 struct node *work (struct node *head, int m) {
     struct node *p, *q;
     p = head;
     while (p->next != p) {
         for (int i = ;i < m; ++i) {
             q = p;
             p = p->next;
         }
         q->next = p->next;
         p->next->prior = q;
         printf ("%4d ", p->data);
         free (p);
         p = q->next;
     }
     return p;
 }
 int main () {
     int m, n;    //n代表一共有n只猴子, m表示循环次数.
     scanf ("%d%d", &n, &m);
     struct node *head;
     head = creat(n, head);
     printf ("被删除的节点是:\n");
     printf ("\n新大王是:%4d\n", work(head, m)->data);
     return ;
 }

主要是练习双向链表的结构而已，原理和单向循环链表类似。

⑦、其实还有队列也可以实现，不过利用队列实现和方法③的思想就相似了，有想法的初学者小码友可以自己去操作一下。

　　先总结这些，再有灵感再往上面加.欢迎批评。