《经典问题约瑟夫环讲解》由会员分享，可在线阅读，更多相关《经典问题约瑟夫环讲解（6页珍藏版）》请在金锄头文库上搜索。
1、1需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围； 输入的值为数字(2) 输出的形式；输出的形式为一串数字如：6，1, 4, 7, 2, 3, 5(3) 程序所能达到的功能；编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。 一开始任选一个正整数作为报数上限值 m,从第一个人开始按顺时针方向自1开 始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的 m值， 从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及
2、其输出结果。输入错误时一般不会显示结果。总体归纳为：1.约瑟夫环(Joseph问题的一种描述是：编号为1, 2, , n的n个人按顺时针方 向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上 限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。 报m的人出列，将他的密码作为新的 m值，从他在顺时针方向上的下一个人开 始重新从1报数，如此下去，直至所有人全部出列为止。2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算 结果显示在其后。3程序执行的命令包括：1输入初始密码
3、和人数2)输入所有人的密码3)显示输入的所有人的编号及相 应的密码4)输出出列密码及编号5)结束4测试数据m=20, n=7, 7个人的密码依次为3，1，7, 2, 4，8, 4m=7,n=20,20个人的密码依次为 3，1，7，2，4，8, 4(2)组数据为错误数据测程序的健壮性。2 概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。ADT LinearList数据元素：D=ai| ai D0, i=1,2,，n n 0 DO为某一数据对象 关系:S= | ai, ai+1 D0，i=1,2, ,n-1该程序只有主程序。基本操作：LinkLi
4、st EvaluList(int n);对单向循环链表进行尾插入赋值int size(LinkList L);求链表的节点个数Status Scan List(Li nkList L); 遍历单向循环链表Status Joseph(L in kList & L,i nt m); 约瑟夫环的实现此抽象数据类型中的一些常量如下：#defi ne TRUE 13 详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程 序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码 算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用 关系图。in
5、t main()coutvv请在第一行输入报数上限 m和人数n空格隔开mn; /输入报数上限和人数 xnode *clist; q=(x node *)malloc(sizeof(x no de); / 初始化 clist=q; coutvv请在第二行依次输入密码空格隔开e ndl;for(i=1;i value;p=(x node *)malloc(sizeof(x no de);p-label=i;p-data=value;p- next=NULL;q-n ext=p;q=p;if(i=n)q-n ext=clist- n ext;p=clist;for(i=1;i=n ;i+)for(j
6、=1;jn ext;q=p-n ext;m=q-data;if(i=n)coutlabele ndl;break;coutlabeln ext=q-n ext;delete q;4. 调试分析当程序大体完成时，却又在调试过程中发现出列次序总是错误的，才想到第一次 指向时应该让变化的指针指向尾节点，这样可以减少当密码为1时程序的设计量考虑到时间问题，密码采用对剩余节点取余来减少遍历次数这个程序可以变得很复杂，也可以变得很简单，关键是对算法的掌握。5. 用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。第一行输入报数上限m和人数n空格隔开在第二行依次输入密码空格隔开6 测试结果列出你
7、的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多 于需求分析中所列。7.附录带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单#i ncludeiostream#i ncludecstdio#i ncludecstdlibusing n amespace std;#defi ne TRUE 1;typedef struct xno deint label;int data;struct xnode *n ext;xno de;int m,n,i,value,j; /定义出现的变量 xnode *p,*q;int main()coutvv请在第一行输入报数上限 m和人
8、数n空格隔开mn; /输入报数上限和人数xnode *clist;q=(x node *)malloc(sizeof(x no de); / 初始化 clist=q;coutvv请在第二行依次输入密码空格隔开e ndl;for(i=1;i value;p=(x node *)malloc(sizeof(x no de);p-label=i;p-data=value;p- next=NULL;q-n ext=p;q=p；if(i=n)q-n ext=clist- n ext;p=clist;for(i=1;i=n ;i+)for(j=1;jn ext;q=p-n ext; m=q-data;if(i=n)coutlabelve ndl;break; coutlabelvn ext=q-n ext; delete q;system(pause);return TRUE;
