约 瑟 夫 环 一.需求分析 1.约瑟夫环(Joseph)问题的一种描述是:编号为1,2……,n的n个人 按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一 个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺 序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m 值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直 至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示"提 示信息"之后,有用户在键盘上输入演示程序中规定的运算命令,相应 的输入数据和运算结果显示在其后。 3.程序执行的命令包括: 1)输入初始密码和人数 2)输入所有人的密码 3)显示输入的所有人的 编号及相应的密码 4)输出出列密码及编号 5)结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3,1,7,2,4,8,4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据,后面两组为边缘数据 二、概要设计 为实现上述功能,应以有序单向循环链表表示约瑟夫环。为此,需 要有一个抽象数据类型。该抽象数据类型的定义为: AD
2022-12-24 18:15:18
319KB
文档资料
1