Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2311950
  • 博文数量: 318
  • 博客积分: 8752
  • 博客等级: 中将
  • 技术积分: 4944
  • 用 户 组: 普通用户
  • 注册时间: 2006-05-23 07:56
文章分类

全部博文(318)

文章存档

2019年(1)

2017年(2)

2016年(12)

2015年(2)

2014年(1)

2013年(17)

2012年(22)

2011年(9)

2010年(37)

2009年(33)

2008年(44)

2007年(43)

2006年(95)

分类: C/C++

2007-05-18 10:19:01

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

现在在提法一般是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);

       /*给所有的人编号为1n */
       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;
}

阅读(1389) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~