约瑟夫问题)n 个人围成一个圆圈,首先第1个人从1开始一个人一个人顺时针报数, 报到第m个人,令其出列。然后再从下一个人开始,从1顺时针报数,报到第m个人,再令其出列,…,如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。请用环形链表实现约瑟夫问题。
【输入】n(2<=n<=60) m(1<=m)
【输出】最后的胜利者编号(编号范围是1至n)
例如:
【输入】
8 3
【输出】
7
一共8个测试用例通过了7个,还有一个没通过,请看看哪里出了问题?代码如下
#include<stdio.h>
#include <stdlib.h>
typedef struct number{
int value;
struct number *next;
}num;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
//创建包含n个人的链表
num *head=NULL;
for(int i=1;i<n+1;i++){
num *p=(num*)malloc(sizeof(num));
p->value=i;
p->next=NULL;
num *last=head;
if (head==NULL)
head=p;
else{
while (last!=NULL&&last->next!=NULL) {
last=last->next;
}
last->next=p;
}
}
//将链表的末尾与头节点连接在一起。
num *p=head;
if (head==NULL) {
head->next=head;
}
else{
while (p!=NULL&&p->next!=NULL) {
p=p->next;
}
p->next=head;
}
//循环删除输入的第m个元素
num *point=head;
int i=1;
while(point->next!=point){
if (i==m-1) {
num *p1=point->next;
point->next=p1->next;
free(p1);
i=0;
}
point=point->next;
i++;
}
printf("%d",point->value);
}