约瑟夫问题 算法实现

约瑟夫问题的一种描述是:

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

为简单起见,
每人密码即为其序列编号。

这是偶今天上数据结构课程设计的题目

偶在网上找到一些代码,都有问题
最后在其中一个代码基础上修改一下,编译成功

下面代码在gcc (GCC) 3.3.5 (Debian 1:3.3.5-13) 下编译成功
C语言实现。


#include
#include
#include
typedef struct node
{
int data;
struct node *next;
}LNode;

main()
{
LNode* Create(int);
LNode* GetNode(LNode *);
int Print(LNode *,int);
LNode *p;
int n,k,m;
do
{
printf (“Enter Total Number: “);
scanf (“%d”,&n);
}
while (n<=0); do { printf ("Enter Initial Password: "); scanf ("%d",&m); } while(m<=0); p=Create(n); Print(p,m); return 0; }; LNode* Create(int n) { LNode *head=NULL,*cul,*newl; int i=1; while(n+1!=i) { newl=(LNode *)malloc(sizeof(LNode)); if(head==NULL) { head=cul=newl; newl->data=i;
newl->next=head;

}
else
{
newl->data=i;
newl->next=cul->next;
cul->next=newl;
cul=newl;
}
i++;
}

return head;
}

LNode* GetNode(LNode *p)
{
LNode *q,*c;
c=p->next;
for(q=p;q->next!=p;q=q->next);
q->next=p->next;

free (p);
return (c);

}

Print(LNode *p,int m)
{
int i;
printf (“Out Sequence:\n”);
while (p->next!=p)
{

for (i=1;inext;
printf (“%d “,p->data);
p=GetNode(p);
}
m=p->data ;
printf(“%d\n”,p->data);
return 0;

}

3 Responses to “约瑟夫问题 算法实现”


Comments are currently closed.