约瑟夫环 c语言 数据结构OJ题

标题

约瑟夫环

时间限制

2 S

内存限制

10000 Kb

问题描述

习题集P79。编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。

问题输入

输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，每组数据的第二行为n个整数，表示每个人持有的密码。

问题输出

用一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔

输入样例

7 20

3 1 7 2 4 8 4

输出样例

6 1 4 7 2 3 5

提示

使用不带头节点的循环链表

// 1.构造线性表 // 2.录入密码 // 3.约瑟夫环 // 4.打印线性表 #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; ElemType sequence; struct LNode *next; }LNode,*LinkList; //创建单链表存储结构 void CreateList(LinkList &L, int n); //创建并输入数据 void Josephus(LinkList L,int n,int m);//约瑟夫环的实现+打印出圈人 int main(){ int n,m; scanf("%d %d",&n,&m); LinkList L; CreateList(L, n); Josephus(L, n, m); return 0; } void CreateList(LinkList &L,int n){ //输入第一个密码 LinkList head = (LinkList)malloc(sizeof(LNode)); head->sequence = 1; head->next = NULL; scanf("%d", &head->data); L = head; LinkList p = head; int i = 2; for(i=2; i<=n; i++){ LinkList s = (LinkList)malloc(sizeof(LNode)); s->sequence = i; s->next = NULL; scanf("%d", &s->data); p->next = s; p = s; } p->next = L; }//创建并输入数据 void Josephus(LinkList L,int n,int m){ int cnt = 1; LinkList p = L, q = L; while(p->next!=p){ for(int i=1;i<m;i++){ q = p; p = p->next; }//i == m; m = p->data; printf("%d ",p->sequence);//输出出圈人的编号 q->next = p->next; free(p); p = q->next; //删除出圈人 } printf("%d",p->sequence);//输出最后一个出圈人的编号 free(p); }//约瑟夫环的实现+打印出圈人