约瑟夫问题

首先看一看最原始的约瑟夫问题：

1   约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。

2  17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒.

3   有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号
开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。就这样，
直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编
号。

4     编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。编程打印出列顺序。


以上是典型的约瑟夫问题。约瑟夫问题的传统解法是利用循环链表加以解决，这就需要从1号元素开始模拟所有元素出列的情况，附上原始的解决方法：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
    int code;
    node * next;
};
int n,m,i,j;
int main(void)
{
    node * head,* tail,* no,* p2;
    no=new node;
    no->code=1;
    no->next=NULL;
    head=tail=no;
    scanf("%d%d",&n,&m);
    for (i=2;i<=n;i++)
    {
        no=new node;
        no->code=i;
        no->next=NULL;
        tail->next=no;
        tail=no;
    }
    tail->next=head;
    for (i=1;i<=n-1;i++)
    {
        j=1;
        while (j<=m-1)
        {
            no=no->next;
            j++;
        }
        printf("%d ",no->next->code);
        p2=no->next;
        no->next=no->next->next;
        delete p2;
    }
    printf("%d\n",no->code);
    system("pause");
    return 0;
}

对于4 ：

#include<stdio.h>
#include<stdlib.h>
/*********
作者： 北京交通大学
      循环链表的应用
********/
typedef struct LNode
{
        int num,code;
        struct LNode *next;
       
}LNode,*Linklist;
/*********
函数名：Josef
参数：整形n，代表人数  m代表初始的密码
返回值：无

**********/
void Josef(int n,int m)
{
     Linklist head,p,L,q;
     head = (Linklist)malloc(sizeof(LNode));
     p = head;
     int i,j,k,temp;
     int mima = m;//初始密码
     for(i=1;i<n;i++)//建立单循环链表 ,有头结点
     {
         L = (Linklist)malloc(sizeof(LNode));
         p->next = L;
         p = L;
     }
     L->next = head;//L指向队尾;
     //L = head;
     //p = head->n;
     p = head;
     for(i = 1;i<=n;i++)//为每一个节点输入密码和号数
     {
    
           printf("请为节点%d输入密码：",i);
           scanf("%d",&j);
           p->num = i;
           p->code= j;
           p = p->next;
          
     }
    

 
    int count = 0;    //count来寻找删除的节点的前一个节点
    p = L;            //从尾指针 开始查找，来防止初始密码为1时可能带来的指针溢出问题
    while(p->next!=p)
    {
         while(count<mima-1)
         {
              p = p->next;
              count++;
             
         }
         mima = p->next->code;
         printf("%d ",p->next->num);
         p->next = p->next->next;
         count = 0;
        
    }
    printf("%d",p->num);
   
     
}
main()
{
      int n,m;
      printf("请输入人数：");
      scanf("%d",&n);
      printf("请输入初始密码：");
      scanf("%d",&m);
      Josef(n,m);
      getchar();
     
}







以上时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

有的问题例如猴子选大王仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：

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

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
  k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。

现在我们把他们的编号做一下转换：
k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i;  (i>1)

有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1

由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：

#include <stdio.h>
int main()
{
  int n, m, i, s=0;
  printf ("N M = "); scanf("%d%d", &n, &m);
  for (i=2; i<=n; i++) s=(s+m)%i;
  printf ("The winner is %d\n", s+1);
}

这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。

在此基础上再看看POJ 2244这个问题：

问题描述：http://acm.pku.edu.cn/JudgeOnline/problem?id=2244

这个问题对约瑟夫问题有点变形： 已知最后的元素 为 2  ，n 从输入中给出，求出最小的m

其实这个用一种比较笨的办法就是 m 从1开始一个一个试，找到第一个（n ，m），使得最后出列的元素序号为2 的 m 即为解。

求最后出列元素的方法由上面给出，这里所作的优化就是求约瑟夫的优化，至于遍历求m的优化可以考虑打表。

这个题目还有一点要注意的就是 ： 它第一个打印的元素始终是1，从2开始为约瑟夫问题，这样可以把2看做是1，n看为n-1的约瑟夫问题。

一下是源代码：

#include<stdio.h>
#include<stdlib.h>
int josef(int n,int m)
{
int s = 0;
for(int i = 2;i<=n-1;i++)
  s = (s+m)%i;
return s+1+1;
}
int main()
{
    int n;
    int m;
    scanf("%d",&n);
    while(n)
    {
  for(m=1;;)
  {
   if(josef(n,m)==2)
    break;
   m++;
  }
  printf("%d\n",m);
  scanf("%d",&n);
 
    }
    return 0;
}