约瑟夫环问题解决答案.doc

《约瑟夫环问题解决答案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、约瑟夫环a)问题描述：Joseph问题的一种描述是：编号为1、2、……、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。b)基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。c)测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先报m的人为6（正确的出列顺序应为6，1，4，7，2，3，

2、5）。实现提示：程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n<=30。*/#include"stdio.h"#include"malloc.h"typedefintDatatype;//定义单链表结点typedefstructnode{Datatypecode;Datatypenum;structnode*next;}Linklist;Linklist*creatsclist(intx)//***{Linklist*p,*q,*H;inti,code;i=1;///*printf("请输入第%d人的密码：",i);scanf("%d",&code);printf("

3、n");*/H=(Linklist*)malloc(sizeof(structnode));H->next=NULL;//i++;p=H;while(i<=x){//printf("请输入第%d人的密码：",i);scanf("%d",&code);printf("");q=(Linklist*)malloc(sizeof(structnode));q->code=code;q->num=i;q->next=NULL;p->next=q;p=q;i++;}q->next=H->next;//尾结点链接到头结点的下一结点returnH;}voidprintlist(Linklist*H,in

4、tx){Linklist*p;inti=1;p=H->next;if(p!=NULL)while(i<=x){printf("%d,%dt",p->num,p->code);p=p->next;i++;}printf("");}voidJoseph(Linklist*H){Linklist*p,*q,*v;intm,k;k=0;p=H->next;q=H;//printf("请输入报数上限值：");scanf("%d",&m);printf("");while(p!=q)//{k++;//if(k==m){printf("%dt",p->num);m=p->code;k=1;i

5、f(H->next==p)H->next=p->next;//该处易出问题q->next=p->next;//v=p;p=q->next;free(v);}q=p;//p=p->next;}printf("%dt",p->num);printf("");}voidmain(){Linklist*H;intx;printf("请输入总人数：");scanf("%d",&x);printf("");H=creatsclist(x);printf("输出每个人的编号,密码：");printlist(H,x);printf("约瑟夫环问题结果输出：");Joseph(H);}