约瑟夫问题求解

 约瑟夫问题是古代经典的趣味数学问题。该问题说的是：把若干人排成一圈，从某个位置数起，每数到第M个就杀掉，最后剩下的是事先指定的几个人。这个问题很可能起源于古罗马军队中对士兵 “逢十取一”的惩罚制度。在公元4世纪的一部著作里，一位以Hegesippus为笔名的作者告诉我们，约瑟夫（Josephus）就是利用这种方式挽救自己性命的：当罗马人Vespasian攻陷Jotapat之后，约瑟夫和另外四十个犹太人躲到一个山洞里避难。让约瑟夫讨厌的是，除了他自己和一名特殊的朋友外，其余39人都决心自杀以便不落入罗马人之手。尽管约瑟夫不愿意这样做，但他不敢公然提出反对；口头上只好同意。但是，他提出了自杀行动必须按顺序进行，并建议：所有人排成一圈，随意从某一位置开始数，每数到三的人拉出圈子杀掉，最后剩下的一位自杀。他把自己和朋友分别安排在第16和31个位置，成功地避开了死神。

现在在提法一般是M个人围成一圈,从某个位置开始按1.2.3...报数报到N的就出圈,问最后出圈的是谁,再或是列出出圈的人的顺序.

这个问题我在一次笔试之前还不知道,那次也没有做出来.现在总结了一下,主要有三种方法,一是用链表,此法思路最简单;二是用指针;三是用递归,这个方法相对难一点.

一,用链表

先定义一个个数据结构,包含一个ID和一个指向下一个的NEXT指针.
#include
#include
#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef struct Cnode
  {  int ID;
     struct Cnode *next;
   }CNode;
CNode *joseph;/*定义一个全局变量  */
int Create_clist(CNode *clist,int n)
{  CNode *p,*q;
int i;
clist=NULL;
   for(i=n;i>=1;i--)
     { p=(CNode *)malloc(sizeof(CNode));
       if(p==NULL)
          return OVERFLOW; /*存储分配失败  */
       p->ID=i;
       p->next=clist;
       clist=p;
       if(i==n)
          q=p;/*用q指向链表的最后一个结点  */
      }
q->next=clist; /*把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表  */
joseph=clist;  /*把创建好的循环链表头指针赋给全局变量  */
return OK;
}              /*end  */
int Josephus(CNode *clist,int m,int n,int k)
{  int i;
CNode *p,*q;
if(m>n) return ERROR;/*起始位置错  */
     if(!Create_clist(clist,n))
     return ERROR;        /*循环链表创建失败  */
   p=joseph;              /*p指向创建好的循环链表  */
   for(i=1;i#include
#include
#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef struct Cnode
  {  int ID;
     struct Cnode *next;
   }CNode;
CNode *joseph;/*定义一个全局变量  */
int Create_clist(CNode *clist,int n)
{  CNode *p,*q;
int i;
clist=NULL;
   for(i=n;i>=1;i--)
     { p=(CNode *)malloc(sizeof(CNode));
       if(p==NULL)
          return OVERFLOW; /*存储分配失败  */
       p->ID=i;
       p->next=clist;
       clist=p;
       if(i==n)
          q=p;/*用q指向链表的最后一个结点  */
      }
q->next=clist; /*把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表  */
joseph=clist;  /*把创建好的循环链表头指针赋给全局变量  */
return OK;
}              /*end  */
int Josephus(CNode *clist,int m,int n,int k)
{  int i;
CNode *p,*q;
if(m>n) return ERROR;/*起始位置错  */
     if(!Create_clist(clist,n))
     return ERROR;        /*循环链表创建失败  */
   p=joseph;              /*p指向创建好的循环链表  */
   for(i=1;i        p=p->next;          /*p指向m位置的结点  */
   while(p)
      { for(i=1;i         p=p->next;     /* 找出第k个结点q  */
       q=p->next;
       printf("%d ",q->data);/*输出应出列的结点  */
       if(p->next==p)
           p=NULL;        /*删除最后一个结点  */
         else { p->next=q->next;/*删除第K个节点*/
                p=p->next;
                free(q);/*这句很重要*/
               }
       }  /* end while  */
      clist=NULL;
} /* end */
void main( )
{ int m,n,k,i;
  CNode *clist;
  clist=NULL;/*初始化clist  */
printf("\n请输入围坐在圆桌周围的人数n：");
scanf("%d",&n);
printf("\n请输入第一次开始报数人的位置m：");
scanf("%d",&m);
printf("\n你希望报数到第几个数的人出列?");
scanf("%d",&k);
Create_clist(clist,n);/*创建一个有n个结点的循环链表clist  */
printf("\n出列的顺序如下：\n");
Joseph(clist,m,n,k);
getch();
}/*main  */
next;          /*p指向m位置的结点  */
   while(p)
      { for(i=1;inext;     /* 找出第k个结点q  */
       q=p->next;
       printf("%d ",q->data);/*输出应出列的结点  */
       if(p->next==p)
           p=NULL;        /*删除最后一个结点  */
         else { p->next=q->next;/*删除第K个节点*/
                p=p->next;
                free(q);/*这句很重要*/
               }
       }  /* end while  */
      clist=NULL;
} /* end */
void main( )
{ int m,n,k,i;
  CNode *clist;
  clist=NULL;/*初始化clist  */
printf("\n请输入围坐在圆桌周围的人数n：");
scanf("%d",&n);
printf("\n请输入第一次开始报数人的位置m：");
scanf("%d",&m);
printf("\n你希望报数到第几个数的人出列?");
scanf("%d",&k);
Create_clist(clist,n);/*创建一个有n个结点的循环链表clist  */
printf("\n出列的顺序如下：\n");
Joseph(clist,m,n,k);
getch();
}/*main  */

二,用指针
#include "stdio.h"
void main()
{       int i = 0;                      //循环变量
       int k = 0;                            //报数的计数器
       int quit_num = 0;        //退出的人数
       int n;                           //总人数
       int m;                          //报数的最大数
       int num[100];              //保存所有人的编号
       int *p = num;                     //初始化指针,使其指向num数组
       printf("Please input number of person: n = ");
       scanf("%d", &n);
       printf("Please input the counter m = ");
       scanf("%d", &m);

       /*给所有的人编号为1到n */
       for (i = 0 ; i < n ; i ++ )
       {
              *(p + i) = i + 1;
       }
       i = 0;
       /*当未退出人数大于1时 执行循环*/
       while(quit_num < n - 1)
       {
              if(*(p+i) != 0) k++;             //已经出圈的人不参与报数
       //报数为m时
      if( k == m )
              {
                     *(p + i) = 0;                 //退出圈子时将此人的编号置为0
                     quit_num ++;
                     k = 0;                          //重新报数
              }
              i ++;
              if (i == n)  i = 0;                //一圈报完后，再从头循环
       }
       while (*p == 0) p ++;                //查找留在圈中的人
       printf("The last one’s number is : %d\n" , *p);
}

三,递归
#include "stdio.h"
int N,M,counter;
int a[50],b[50;]
void joseph(int s,int n)
{
     static int qnum= 1;    /*定义一静态便量，用於记录已被压缩出来的元素个数*/
     int i,j;
      if(n == 1)       /*当还有一个元素时，递归返回*/
     return;
     for(i=0;i< counter;i++)  /*寻找将被压缩元素*/
     {
            if(s++>n)   /*当a[m]被读取后，下一次又从a[1]开始*/
            s=1;
     }

     b[qnum++] =  a[s];/*标记被压缩成员的编号并将其序号放入数组b中*/

/*/压缩剩余的数据*/
 for(i=s;i< n;++i)
{
     a[i] = a[i+1];
}
 
joseph(s,n-1);  /*对剩余元素继续压缩(递归调用)*/

}
int main( )
{
     int i;
     printf("\n请输入围坐在圆桌周围的人数N：");
  scanf("%d",&N);
  printf("\n请输入第一次开始报数人的位置M：");
  scanf("%d",&M);
  printf("\n你希望报数到第几个数的人出列?");
  scanf("%d",&counter);
    for(i=1;i＜=N;i++)   //初始化数据
      {
  a[i] = i;
      }
joseph(M,N);
printf("出列的顺序是:\n");
 for(i=1;i＜=N;i++)  /*输出*/
{
      printf("%d   ",b[i]);
}
getchar();
return 0;
}