Joseph ring实习报告.doc

约瑟夫环问题模拟一、 需求分析1、 本演示程序模拟约瑟夫环问题：编号为1，2，n得n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。2、 演示程序以用户和计算机对话的方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。运算结果显示在其后。3、 程序需要输入的信息与命令包括：1） 初始人数 n ；2） n 个人的密码；3） 初始的 m 值；4、 测试数据1） n：7密码：3、1、7、2、4、8、4 m：62） n：1密码：4 m：33） n：4密码：4、2、3、1 m：124） n：3密码：1、2、3 m：2二、 概要设计为了实现上述程序功能，应以单向循环链表模拟问题过程。每个结点代表一个玩家。1、 有序表抽象数据类型定义：ADT list数据对象：D = a i | a i LNode, i = 1,2,n, n = 0数据关系：R = | a i-1, a i D, i = 2,n基本操作：Init(&L)操作结果：构造一个空的单向循环链表。Insert(&L, n, s)初始条件：链表L已存在，玩家编号n，玩家密码s。操作结果：插入一个玩家结点。Del(&L, m, e)初始条件：链表L已存在，m值有效。操作结果：删除链表中第m个结点，并有e返回这个结点。ADT list2、 本程序包含两个模块：a) 主程序模块：int main()初始化;接受命令;处理命令;退出;return 0;b) 循环单向链表单元模块 实现单向循环链表抽象数据类型；模块之间的调用关系如下：主程序模块 单向循环链表单元模块三、 详细设计int main() /主函数main的实现 int n, m, s, i; List l; if (Init(l) /初始化链表，执行成功后接受命令 printf(how many players? : ); scanf(%d, &n); for (i = 1; i = 1; i-) /处理命令，模拟人员的退出结点的删除 if (Del(l, m, e) printf(the number %d player come outn, Num); m = (m - 1 + Sec) % (i - 1); if (m = 0) m = i - 1; /for /if else printf(ERROR!); return 0;typedef struct Lnode /链表结点类型定义 int intNum; int intSec; struct Lnode *next;Lnode, *Linklist;typedef struct /循环单向链表类型定义 Linklist head; Linklist tail;List;bool Init(List &l) /链表初始化 l.head = l.tail = NULL; return true;bool Insert(List &l, int N, int S) /在链表末尾插入玩家号为N，玩家密码为S的结点 Linklist p = (Linklist)malloc(sizeof(Lnode); if (!p) return false; p -intNum = N; p -intSec = S; if (!l.head) l.head = p; else l.tail -next = p; p -next = l.head; l.tail = p; return true;bool Del(List &l, int m, Lnode &e) /删除链表中第m个结点，并用e返回 Linklist p = l.tail; if (!p | m 1) return false; int cnt = 1; while (cnt next; cnt+; if (l.head = l.tail) p -next = NULL; e = *p; free(p); return true; Linklist q = p -next; if (q = l.tail) l.tail = p; if (m = 1) l.head = q -next; p -next = q -next; q -next = NULL; e = *q; free(q); return true;四、 调试分析1、 由于程序时模拟约瑟夫环过程的，只是单纯的对问题的抽象解决，在数据范围不是很大的情况下程序可以比较迅速的完成问题的模拟，但是在大数据范围下，本程序模拟的方法是不适用的，需要更优化的算法。2、 算法的时空分析1） 由于只用到了循环单链表，所以空间的负责度是根据输入要求玩家个数决定的，即空间复杂度是O(n)，n为玩家个数，也是结点个数。2） 算法是模拟约瑟夫环玩家出列的过程，即不断的循环计数然后出列，故和初始的m值以及玩家手里的密码intSec值有关系。所以它的循环次数是m+intSec(i)。3、 本实习作业采用数据抽象程序设计方法，将程序划分为两个层次结构：主控制模块、链表模块，使得设计思路清晰，实现时调试顺利，各模块具有好的重用性，确实得到了一次良好的程序设计训练。五、 用户手册1、 本程序的运行环境为wind