从“约瑟夫问题”谈起
约瑟夫问题是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想自杀。为避免与其他39个决定自杀的犹太人发生冲突，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行，直到仅余15个人为止。问怎样的​排法，才能使每次投入大海的都是非教徒。
【例1】约瑟夫问题。
N个人围成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，…M”报数，报到M的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人，该人就是优胜者。输入N和M，输出出圈顺序。
例如，N=6、M=5，出圈的顺序是：5，4，6，2，3，1。
（1）编程思路。
为输出出圈顺序，采用一个数组来进行模拟。
定义int circle[N+1]，并按circle[i]=i+1的方式赋予各元素初值。该值代表两个含义：1）值为0，代表编号i+1的人不再圈中；2）值非0，代表圈中第i个位置的人编号为i+1。
定义变量i代表报数位置的流动，i的初值为0，代表编号为1的人的位置，i的变化方式为：
i=(i+1)%(n)， 即0-->1-->2……->n-1  ->0-->1……。
i流动到了位置i后，该位置的人若已出圈（circle[i]==0），显然无法报数，得跳过该位置；
若该位置的人在圈中，则报数（定义一个表示报数的变量p，初值为0，每次报数p++）。
当报数到m（即p==m）时，位置i的人出圈，记录出圈人数cnt++，同时p置为0。当出圈人数等于N时循环结束。
（2）源程序。
#include <stdio.h>
int main()
{
      int n,m,i,p,cnt;
      int circle[50];
      while (scanf("%d%d",&n,&m) && n!=0)
      {
          for (i=0;i<n;i++)
              circle[i]=i+1;
          i=0;      // 报数指示
          p=0;    // 报数计数器
          cnt=0;    // 出队人数
          while (cnt<n)
          {
                if (circle[i]!=0) p++;
                if (p==m)
                {
                      printf("%d ",circle[i]);
                      cnt++;
                      circle[i]=0;
                      p=0;
                  }
                  i=(i+1)%(n);
令数组全部的值为0
            }
            printf("\n");
      }
      return 0;
}
下面我们从例1的基础上进行扩展讨论。
例如，运行例1的程序时，输入41  3，则输出为：
3  6  9  12  15  18  21  24  27  30  33  36  39  1  5  10  14  19  23  28  32  37  41  7  13  20  26  34  40  8  17  29  38  11  25  2  22  4  35  16  31
为这个输出结果进行的模拟是需要耗时的。实际上，在大多数问题中，我们不关心中间的结果，只关心某个最终结果。例如，在Josephus 的故事中，Josephus 和他的朋友不想自杀，Josephus 需要关心的是最后一个和倒数第2个出圈的编号是多少，至于中间过程（39个犹太人谁先自杀，谁后自杀）对Josephus 来说无意义。因此，Josephus 需要的是快速确定最后一个和倒数第2个出圈的编号，然后站到对应位置即可。而无需耗时模拟整个过程。
【例2】猴子选大王。
一堆猴子都有编号，编号是1，2，3 ...m，这猴子(m个)按照1~m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。已知猴子数m和报数间隔n（设1<=n<=m<=50），问编号为多少的猴子当大王？
（1）编程思路1。
将例1的源程序略作修改，增加一个变量last记录最后获胜者编号，不输出中间过程。显然，  if (cnt==n) last=circle[i];
（2）源程序1。
#include <stdio.h>
int main()
{
    int n,m,i,p,cnt,last;
    int circle[50];
    while (scanf("%d%d",&n,&m) && n!=0)
    {
        for (i=0;i<n;i++)
            circle[i]=i+1;
        i=0;      // 报数指示
        p=0;      // 报数计数器
        cnt=0;    // 出队人数
        while (cnt<n)
        {
              if (circle[i]!=0) p++;
              if (p==m)
              {
                  cnt++;
                  if (cnt==n) last=circle[i];
                  circle[i]=0;
                  p=0;
              }
              i=(i+1)%(n);
      }
      printf("%d\n",last);
    }
    return 0;
}
（3）编程思路2。
源程序1中采用数组模拟，由于猴子在圈中还是出圈是通过数组元素circle[i]的值非0还是0来判断，位置并未真正删除，因此当n和m很大时，程序的执行效率很低。例如，仅求最后一个出圈的元素，循环就得执行m*n次（p从1报到m，每次报数流动i得走完整一圈，其中n-1个已出圈，圈中仅一个元素）。
为提高运行效率，可以考虑采用循环链表来进行模拟，这样每次出圈就将链表中的相应元素删除。循环链表只剩最后一个元素时，输出胜者编号。
（4）源程序2。
#include <stdio.h>
struct Jose
{
      int code; // 编号
      Jose *next;
};
int main()
{
      Jose *head,*p1,*p2;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。