UC知道C语言 约瑟夫环问题
来源：百度知道 编辑：UC知道 时间：2024/05/10 13:51:14
约瑟夫(josephus)环是这样的：假设有n个小孩围坐成一个圆圈，并从1开始依次给每个小孩编上号码。老师指定从第s位小孩起从1开始报数，当数到m时，对应的小孩出列，依次重复，问最后留下的小孩是第几个小孩？例如：总共有6个小孩，围成一圈，从第一个小孩开始，每次数2个小孩，则游戏情况如下：
小孩序号：1，2，3，4，5，6
离开小孩序号依次为：2，4，6，3，1
最后获胜小孩序号：5
每组输入是三个整数n，s，m。(1 <= n <= 30, 1 <= s <= n，1 <= m <= 10) ；
对于每组输入，请输出最后留下小孩的序号
Sample Input
6 1 2
Sample Output
5
小孩序号：1，2，3，4，5，6
离开小孩序号依次为：2，4，6，3，1
最后获胜小孩序号：5
每组输入是三个整数n，s，m。(1 <= n <= 30, 1 <= s <= n，1 <= m <= 10) ；
对于每组输入，请输出最后留下小孩的序号
Sample Input
6 1 2
Sample Output
5
#include<stdio.h>
#include<malloc.h>
#define Namelength 10
typedef struct CLNode{
char*name;
int ID;
int pastword;
struct CLNode *next;
}child,*ptrchild;
ptrchild CreateCList(int n)
{int i;
ptrchild p,head,rear;
printf("please input the children information:");
rear=head=(ptrchild)malloc(sizeof(child));
rear->next=head;
for(i=0;i<n;i++)
{getchar();
p=(ptrchild)malloc(sizeof(child));
p->ID=i+1;
p->name=(char*)malloc(Namelength*sizeof(char));
gets(p->name);
scanf("%d",&(p->pastword));
rear->next=p;
rear=p;
}
rear->next=head;
return head;
}
Joshpus(ptrchild head,int m)
{ptrchild p,q;int i=0;
p=head;
while(head->next!=head)
{while(i<m)
{q=p;
p=p->next;
if(p==head){q=head;p=p->next;}
i++;
}