Question

试编写一个求解Josephus问题的函数

用整数序列1,2,3,...,n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。然后使用n=9,s=1,m=5,以及n=9,s=1,m=0或者n=9,s=1,m=10作为输入数据，验证程序的正确性。(用C语言)

Answer 1

#include <stdio.h>

#include <alloc.h>

struct circle

{

int number;

struct circle *next;

};

struct circle * creat_j(int n) /* 建立有n个结点的循环链表 */

{

int i;

struct circle *head,*new,*p;

new=(struct circle *)malloc(sizeof(struct circle));

new->number=1;

head=new; /* 生成链表的头指针 */

p=new;

for(i=2;i<=n;i++) /* 该循环生成链表的第2到第n个结点 */

{

new=(struct circle *)malloc(sizeof(struct circle));

new->number=i;

p->next=new;

p=new;

}

p->next=head; /* 建立循环链表 */

return(head); /* 返回头指针的值作为函数值 */

}

void josephus(struct circle head,int m) /* 利用循环链表解决Josephus问题的函数 */

{

struct circle *p,*q,*temp;

int i=1;

q=p=head;

while(p!=p->next) /* 当链表中多于一个结点时，就一直数下去 */

{

if(i==m) /* 数到m的结点从链表中删除 */

{

printf("%5d",p->number); /* 输出编号 */

q->next=p->next;

temp=p;

p=p->next; /* 下一个结点为下一论数数的起点 */

free(temp);

i=1;

}

else /* 继续向下数数 */

{

q=p;

p=p->next;

i++;

}

}

printf("%5d",p->number); /* 输出最后一个结点的编号 */

}

main()

{

int n,m;

struct circle *head;

printf("Enter n,m:");

scanf("%d,%d",&n,&m);

head=creat_j(n); /* 创建循环链表 */

josephus(head,m); /* 解决Josephus问题 */

}