您所在位置：主题：[讨论]我设计的Josephus环问题的C程序,看看有什么问题.
wuliaolll
[专家分：90] 发布于 2007-03-28 21:55:00
Josephus环问题
设编号为1、2、…N的n个人围坐一圈，约定编号为K（1≤K≤N）的人从1开始报数，数到M的那个人出列，它的下一位又从1开始报数，数到M的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
#include <stdio.h>
#include <malloc.h>
#define N 10
#define M 3
#define K 4
typedef struct node
{int number;
struct node *next;}
lnode
main()
{int i,j,quit[N],k=0;
lnode *head,*r,*s,*p;
head=null;
r=null;
for(i=1;i<=n;i++)
{s=(lnode*)malloc(size of (lnode));
s->number=i;
if(head==null)
head=s;
else
r->next=s;
r=s;}
if(r!=null)
r->next=head;
p=head;
for(i=1;i<K;i++)
p=p->next;
while(k!=N)
{
for(j=1;j<M;j++)
p=p->next;
quit[i++]=p->next->number;
k++;
Delete(p);}
for(i=0;i<N;i++)
pritf("the NO.d% is d%\n",i+1,a[i]);
}
Delete(lnode *p)
{lnode *r;
if(p->next!=null)
{r=p->next;
p->next=r->next;
free(r)}
}
高手帮我看看,总是说我的主函数说明语法错误,我看了很长时间,就是看不出.
算法是:
由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。
为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：int quit[n];n为一个根据实际问题定义的一个足够大的整数。
设编号为1、2、…N的n个人围坐一圈，约定编号为K（1≤K≤N）的人从1开始报数，数到M的那个人出列，它的下一位又从1开始报数，数到M的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
#include <stdio.h>
#include <malloc.h>
#define N 10
#define M 3
#define K 4
typedef struct node
{int number;
struct node *next;}
lnode
main()
{int i,j,quit[N],k=0;
lnode *head,*r,*s,*p;
head=null;
r=null;
for(i=1;i<=n;i++)
{s=(lnode*)malloc(size of (lnode));
s->number=i;
if(head==null)
head=s;
else
r->next=s;
r=s;}
if(r!=null)
r->next=head;
p=head;
for(i=1;i<K;i++)
p=p->next;
while(k!=N)
{
for(j=1;j<M;j++)
p=p->next;
quit[i++]=p->next->number;
k++;
Delete(p);}
for(i=0;i<N;i++)
pritf("the NO.d% is d%\n",i+1,a[i]);
}
Delete(lnode *p)
{lnode *r;
if(p->next!=null)
{r=p->next;
p->next=r->next;
free(r)}
}
高手帮我看看,总是说我的主函数说明语法错误,我看了很长时间,就是看不出.
算法是:
由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。
为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：int quit[n];n为一个根据实际问题定义的一个足够大的整数。
