Question

约瑟夫环问题解答。求高手帮忙~~~要求C语言编程

1．约瑟夫环问题 [问题描述] 设有n个人围坐一圈，现从第s个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列。如此下去，直到所有人都出列为止。试设计确定他们出列次序序列的程序。[基本要求] 选择单向循环链表作为存储结构模拟整个过程，并依次输出出列的各人的编号。[实现提示] 此题中循环链表可不设头结点，而且必须注意空表和“非空表”的界限。如：n=8，m=4时，若从第一个人开始报数，设每个人的编号依次为1，2，3，…开始报数，则得到的出列次序为4 8 5 2 1 3 7 6，如下图所示，内层数字表示人的编号，每个编号外层的数字代表人出列的序号。

Answer 1

循环链表实现约瑟夫环

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int num;
struct node *next;
}NODE;
//创建一个没有头结点的链表
NODE *createlinklist(int n)
{
system("color 5");
NODE *head,*p,*q;
int i=1;
int x;
head=p=(struct node*)malloc(sizeof(struct node));
printf("请输入第1个元素的值：");
scanf("%d",&x);
p->num=x;//没有头结点的链表
for(i=2;i<=n;i++)
{
int y;
q=(struct node*)malloc(sizeof(struct node));
if(q==0) return(0);
p->next=q;
p=q;
printf("请输入第%d个元素的值：",i);
scanf("%d",&y);
p->num=y;
}
p->next=head;//使链表尾指向链表头 形成循环链表
return head;
}
//输出这个链表
void printlinklist(NODE *p,int n)
{
system("color 1f");
int i;
NODE *q = p;
if(NULL == q->next)
{
printf("链表为空！");
return;
}
printf("所有元素的信息列表:\n");
for(i=1;i<=n;i++)
{
if(NULL == q)
{
printf("the list is NULL!");
return;
}
printf("%d ",p->num);
p=p->next;
}
printf("\n");
}
//开始从第一个人开始玩起
void yuesefu(NODE *p,int n,int m)
{
system("color 2f");
int i,j;
NODE *q;
for(i=1;i<n;i++)
{
for(j=1;j<m-1;j++)
{ p=p->next;
}
q=p->next;
p->next = q->next;
printf("%d ",q->num);
free(q);
p=p->next;//每次删除结点之后，指针P向后移一个，表示从出列的人的后一个人开始玩起；
}
printf("\n最后剩余的是第%d号.\n",p->num);
p->next=NULL;
}
//主函数
void main()
{
NODE *head;
int n,m;
system("color 9f");
printf("请输入元素的个数N:\n");
scanf("%d",&n);
printf("请输入间隔数K:\n");
scanf("%d",&m);
head=createlinklist(n);
printlinklist(head,n);
printf("依次被选出的是:\n");
yuesefu(head,n,m);
}