解决JOSEPH问题的代码 - 彦宏的博客

作者在 2008-03-22 21:51:44 发布以下内容

设有n个人围坐在圆桌周围，现从某个位置m（1≤m≤n）上的人开始报数，报数到k的人就站出来。下一个人，即原来的第k+1个位置上的人，又从1开始报数，再报数到k的人站出来。依此重复下去，直到全部的人都站出来为止。试设计一个程序求出出列序列。

这是一个使用循环链表的经典问题。因为要不断地出列，采用链表的存储形式能更好地模拟出列的情况。

#include<stdio.h>
typedef struct Cnode
{
int data;
struct Cnode *next;
}*list,node;
struct Cnode *q;
struct Cnode *p;
list Create_clist(struct Cnode *l,struct Cnode *p,struct Cnode *q,int n)
{
int m;
m=1;
while(m==1)
{
l=(list)malloc(sizeof(node));
l->data=m;
l->next=l;
p=l;
q=l;
m++;
}

while(m>1&&m<=n)
{
  l=(list)malloc(sizeof(node));
  l->data=m;
  l->next=q;
  p->next=l;
  p=p->next;
  m++;

}
return q;

}
int Joseph(struct Cnode *q,int m,int n,int k)
{
int i,j,o;
struct Cnode *s;
struct Cnode *y;
i=1;

s=q;
y=q;
while(i<m)
{
++i;
s=s->next;

}
j=1;

while(j<=n)
{

  i=1;
  o=1;
  while(i<k)
   {
    s=s->next;
    i++;
   }
  y=s;
  while(o<=(n-j))
  {
   o++;
   y=y->next;

}

  printf("%d ",s->data);
  s=s->next;
  y->next=s;

j++;

}

return (1);
}
void main()
{
int m,n,k;
struct Cnode *l;

printf("please input the number of people :\n");
scanf("%d",&n);
printf("first in :\n");
scanf("%d",&m);
printf("the number of out in circle :\n");
scanf("%d",&k);
Create_clist(l,p,q,n);
printf("the number of out in turn is :\n");
q=Create_clist(l,p,q,n);
Joseph(q,m,n,k);

}