约瑟夫斯问题.doc

实验一：约瑟夫斯问题实验报告 问题描述 1） 问题描述 约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。 2）基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3）测试数据 m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。 需求分析 1．该程序所能实现的功能：将n个数字按照某一特定序列输出，直至全部输出为止。 2．输入的形式及输入值范围 ：依次输入人数n、每个人的密码及报数上限m值。 3．输出的形式：按照报数上限m及每个人的密码依次输出每个人的编号。 4．测试数据要求：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。 概要设计 主程序流程 获取每个人的密码，选定m的初值，调用函数，按照特定要求完成输出操作。 2.核心模块的算法伪码 主程序： void main(void) { int m; people *s; s=GetData(); cout请输入m的初值：endl; cinm; DealData(s,m); } 预编译代码：#includeiostream.h 详细设计 1.实现每个操作的伪码，重点语句加注释 (1)建立“人”的结构体 struct people { int data; int num; people *next; }; （2）获取每个人的相关数据 people *GetData() { int n; people *p1,*p2,*head; head=NULL; cout请输入人数：; cinn; cout请依次输入每个人的密码：endl; for(int i=0;in;i++) { p1=new (people); cinp1-data; p1-num=i+1; if(head==NULL) { head=p2=p1; //建立首结点 } else { p2-next=p1; //中间结点 p2=p1; } } if(head!=NULL) p2-next=head; return(head); //循环链表 } 2.函数调用关系图 Main() void DealData(people *s,int m) people *GetData() 五、调试分析 1. 设计与调试过程中遇到的问题分析、体会. 在调试过程中遇到了死循环的情况，自己反复看了很久也未能查找到错误，直到请同学帮忙看，才终于发现原来是一个在循环条件中，写丢了一个条件。后来回想，觉得当初自己检查的时候不够仔细，大概也有些主观思想——认为不可能出错——掺杂其中，导致有此结果。以后写程序要更认真才行。 2. 主要算法的时间 主程序：循环算法。 六、使用说明 打开此程序，点击运行，按照屏幕输出显示依次输入所需数据即可—— 首先输入参与的人数；然后依次输入每个人手中的密码；最后输入m的初值，即可得到输出结果。 七、测试结果 八、附录 源程序 #includeiostream.h struct people { int data; int num; people *next; }; people *GetData() { int n; people *p1,*p2,*head; head=NULL; cout请输入人数：; cinn; cout请依次输入每个人的密码：endl; for(int i=0;in;i++) { p1=new (people); cinp1-data; p1-num=i+1; if(head==NULL) { head=p2=p1; //建立首结点 } else { p2-next=p1; //中间结点 p2=p1; } } if(head!=NULL) p2-next=head; return(head); //循环链表 } void DealData(people *s,int m) { people *p1,*p2,*q; p