高校问答打球手指戳伤后变形了:急！求解C语言关于约瑟夫环的程序？
来源：百度文库 编辑：高校问答 时间：2024/05/04 05:24:43
约瑟夫环问题的一种描述是：编号为1.2.3…….n的n个人按顺时针方向围坐一圈
，每人手持一个密码（正整数），开始任意选一个整数作为报数上限值，从第一
个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密
码作为新的m值，从他顺时针下一个人开始重新从1开始报数，如此下去直到所有
的人全部都出列为止。试设计程序实现。
要求：利用循环链表存储结构模拟此过程，按照出列的顺序打印各人的编号。
测试数据：m的值初始为20：密码3 ，1，7，2，4，8，4。
正确的结果：6，1，4，7，2，3，5。
提示：程序运行后首先要求用户指定初始报数上限。然后读取各人的密码。设
n<30。
typedef struct node
{
int num,code;
struct node *next;
}lnode;
void main()
{
int i,j,key,n; /*i,j为记数器,key为输入的密码,n为人的总个数*/
lnode *p,*s,*head;
head=(lnode *)malloc(sizeof(lnode)); /*为头结点分配空间*/
p=head;
printf("Please enter the num of the person:"); /*输入人的总个数*/
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("Person %d",i);
printf(" code: ");
scanf("%d",&key); /*输入各个人的密码*/
s=p;
p=(lnode *)malloc(sizeof(lnode)); /*创建新的结点*/
s->next=p;
p->num=i;
p->code=key;
}
p->next=head->next;
p=head;
head=head->next;
free(p);
p=head;
do
{
printf("\nPerson%d Code:%d",p->num,p->code); /*输出链表*/
p=p->next;
}while(p!=head);
printf("\nPlease enter your first key:"); /*输入第一个数*/
scanf("%d",&key);
do
{
j=1; /*j为记数数*/
p=head;
while(j<key)
{
s=p;
p=p->next;
j++;
}
i=p->num;
key=p->code;
printf("\nThe out of the num:");
printf("Person%d",i);
s->next=p->next;
head=p->next; /*重新定义head,下次循环的开始结点*/
free(p);
n--; /*每循环一次人是减1*/
}while(n>0);
getch();
}
＃i nclude <iostream.h>
＃i nclude <string.h>
＃i nclude <stdio.h>
typedef struct LNode{
int data,code;
struct LNode *next;
}LNode,*LinkList;
void main()
{
int m,n,i;
printf("输入初始报数上限值m:");
scanf("%d",&m);
printf("输入人数n:");
scanf("%d",&n);
printf("输入各人密码:");
LinkList p,head,q;
head=new LNode;
head->data=1;
scanf("%d",&head->code);
p=head;
//初始化单向循环链表
for(i=2;i<=n;i++)
{
struct LNode *s=new LNode;
s->data=i;
scanf("%d",&s->code);
p->next=s;
p=p->next;
}
p->next=head;
printf("出列顺序为:");
//处理出列顺序
while(n!=1)
{
for(i=1;i<m;i++)
{
p=p->next;
}
q=p->next;
p->next=q->next;
m=q->code;
printf("%d",q->data);
delete q;
n--;
}
printf("%d",p->data);
}