SDUT 链表9-------7-9 sdut-C语言实验-约瑟夫问题

7-9 sdut-C语言实验-约瑟夫问题

分数 20

全屏浏览

切换布局

作者 马新娟

单位 山东理工大学

n个人想玩残酷的死亡游戏，游戏规则如下：

n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。

请输出最后一个人的编号。

输入格式:

输入n和m值。

输出格式:

输出胜利者的编号。

输入样例:

5 3

输出样例:

4

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include<stdio.h>
#include<stdlib.h>
struct node
{int data;struct node *next;
};
int main()
{struct node *head,*tail,*p,*q;int n,m;scanf("%d %d",&n,&m);head=(struct node*)malloc(sizeof(struct node));head->next=NULL;tail=head;//建立链表for(int i=1; i<=n; i++){p=(struct node*)malloc(sizeof(struct node));p->data=i;p->next=NULL;tail->next=p;tail=p;}//对链表中的每一个赋值head=head->next;//对于循环链表要注意head是有数值的，不能和之前一样赋值为NULLp->next=head;//将最后的指向headtail=head;while(tail->next!=head){tail=tail->next;}//寻找head之前的，方便删除链表中的元素p=head;while(p->next!=p){int t=m-1;//要注意是从1开始喊，而使用while时0时才停止，因此要-1while(t--){tail=tail->next;p=p->next;}//进行喊数tail->next=p->next;p=p->next;//删除链表元素过程}printf("%d",p->data);
}