分类: C/C++
2007-05-18 10:19:01
约瑟夫问题是古代经典的趣味数学问题。该问题说的是:把若干人排成一圈,从某个位置数起,每数到第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
while(p)
{ for(i=1;i
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 */
while(p)
{ for(i=1;i
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;
}