qingsongzdq 2019-06-28
约瑟夫(Joseph)问题的一种描述是:编号为 1,2,⋯ ⋯ n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值 m,从第一个人开始按顺时针方向自 1 开始顺序报数,报到 m 时停止报数。报 m 的人出列,将他的密码作为新的 m 值,从他在顺时针方 向上的下一个人开始重新从 1 报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。
利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。
n=7, 7 个人的密码依次为:3,1,7,2,4,8,4,首先 m 值为 6(正 确的出列顺序应为 6,1,4,7,2,3,5),输出的密码为 8,3,2,4,1, 7,4.
程序运行后,首先要求用户指定初始报数上限值,然后读取各人的密 码。可设 n<=30。此题所用的循环链表中不需要“头节点”,请注意空表和非空表的界限。
#include<stdio.h> #include<stdlib.h> #define LEN sizeof(struct Student) #define N 7 struct Student //用链表建立学生数据类型 { int number; int password; struct Student *next; }; struct Student *creat(void) //输入具体学生信息,约定0,0结束 { struct Student *head; struct Student *p1,*p2; int n=0; p1=p2=(struct Student *)malloc(LEN); scanf("%d,%d",&p1->number,&p1->password); head=NULL; while(p1->number!=0) { n=n+1; if(n==1)head=p1; else p2->next=p1; p2=p1; p1=(struct Student *)malloc(LEN); scanf("%d,%d",&p1->number,&p1->password); } p2->next=head; return(head); } void Joseph(struct Student *head,int count) //游戏环节,按照约瑟夫环规则运行,并输出结果 { int m; struct Student *p; p=head; for(m=1;m<count-1;m++) p=p->next; printf("%d,%d\n",(p->next)->number,(p->next)->password); count=p->next->password; p->next=p->next->next; do{ for(m=1;m<count;m++) p=p->next; printf("%d,%d\n",(p->next)->number,(p->next)->password); count=p->next->password; p->next=p->next->next; }while(p!=p->next); printf("%d,%d\n",p->number,p->password); } void main() //主函数,输入学生信息和上限值 { struct Student *Head; int num; printf("请输入个人的序号和密码:\n"); Head=creat(); printf("请指定初始报数上限值:\n"); scanf("%d",&num); Joseph(Head,num); }