数据结构实习大作业
第一次大作业：
实习报告
题目：约瑟夫（Joseph）问题——编号为 1，2，…，n 的 n 个人按顺时针方向围坐一
圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个
人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报到 m 的人出列，将他的密
码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所
有人全部出列为止。设计一个程序求出出列顺序。
班级： 自动化
AG61 姓名： 王哲
学号： 2008210934 完成日期： 2009.3.28
选择难度系数：4 （ 做了选作内容 ） 编译运行环境：VC++6.0
Email：wangzhe08@mails.tsinghua.edu.cn / wangzhe860723@sina.com
一、需求分析
1.本程序中，每个人按编号并按顺时针形成一个圈，报数上限值，人数和密码的输入
限定为正整数，由于每人持有一个密码，输入密码数应与人数保持一致。输入上限值，人
数的形式为一个以“回车符”为结束标志的正整数，而输入密码时，每个密码之间用“，”或
“空格符”或“回车符”隔开，并以“回车符”结束。输出是按照出列顺序的个人的编号，同样为
正整数。
2.程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由
用户根据“提示信息”通过键盘输入数据，相应的运算结果显示在其后，在运算结果之前同
样有提示的命令信息。
3.程序执行的命令包括：
1） 输入初始报数上限值 m
2） 输入人数 n
3） 输入每个人的密码
4） 链式结构输出出列顺序
5） 顺序结构输出出列顺序
4.测试数据：
m 的初值为 20；
n=7, 7 个人的密码依次为：3，1，7，2，4，8，4，首先 m 值为 6（正确的出列顺序应
为 6，1，4，7，2，3，5）。
自动化系 第 1 页
