约瑟夫环程序设计报告书

附件 4 课程设计报告书 数 据 结 构 课程设计报告 约瑟夫 Joseph 环 组别第七组 组长 组成员 成绩 指导教师 计算机科学与技术系计算机科学与技术系 20142014 年年 6 6 月月 1111 日日 摘要摘要 约瑟夫环问题是典型的线性表的应用实例 其开发主要包括后台数据库的建 立和维护以及前端应用程序的开发两个方面 对于前者要求建立起数据一致性 和完整性强 数据安全性好的库 而对于后者则要求应用程序功能完备 易使 用等特点 经过分析 我们使用 MICROSOFT 公司的 Microsoft Visual C 6 0 开发工具 利用其提供的各种面向对象的开发工具 尤其是数据窗口这一能方便而简洁操 作数据库的智能化对象 首先在短时间内建立系统原型 然后 对初始原型系 统进行需求迭代 不断修正和改进 直到形成用户满意的可行系统 关键词 关键词 单循环链表 c 语言 约瑟夫环 序言序言 数据结构是研究数据元素之间的逻辑关系的一门课程 以及数据元素及其关 系在计算机中的存储表示和对这些数据所施加的运算 该课程设计的目的是通 过课程设计的综合训练 培养分析和编程等实际动手能力 系统掌握数据结构 这门课程的主要内容 本次课程设计的内容是用单循环链表模拟约瑟夫环问题 循环链表是一种首 尾相接链表 其特点是无须增加存储容量 仅对表的链接方式稍作改变 使表 处理更加灵活 约瑟夫环问题就是用单循环链表处理的一个实际应用 通过这 个设计实例 了解单链表和单循环链表的相同与不同之处 进一步加深对链表 结构类型及链表操作的理解 通过该课程设计 能运用所学知识 能上机解决一些实际问题 了解并初步 掌握设计 实现较大程序的完整过程 包括系统分析 编码设计 系统集成 以及调试分析 熟练掌握数据结构的选择 设计 实现以及操作方法 为进一 步的应用开发打好基础 章节安排章节安排 摘要 序言摘要 序言 1 1 一 问题描述一 问题描述 1 1 课程设计目的 课程设计目的 4 4 2 2 课程设计任务 课程设计任务 4 4 二 设计过程二 设计过程 1 1 设计思想 数据结构 设计思想 数据结构 4 4 2 2 设计表示 函数说明 设计表示 函数说明 5 5 3 3 详细设计 主要算法 详细设计 主要算法 6 6 4 4 用户手册 使用说明 用户手册 使用说明 6 6 三 测试报告三 测试报告 1 1 测试用例 测试用例 6 6 2 2 测试结果 测试结果 6 6 3 3 分析探讨 分析探讨 7 7 四 总结四 总结 10 10 五 附录 源程序 五 附录 源程序 10 10 六 参考文献六 参考文献 16 16 章节安排 章节安排 一 问题描述一 问题描述 1 1 课程设计目的 课程设计目的 1 掌握单向循环链表的建立 2 掌握单向循环链表的操作 2 2 课程设计任务 课程设计任务 编号是 1 2 n 的 n 个人按照顺时针方向围坐一圈 每个人只有一个密码 正整数 一开始任选一个正整数作为报数上限值 m 从第一个仍开始顺时针方 向自 1 开始顺序报数 报到 m 时停止报数 报 m 的人出列 将他的密码作为新的 m 值 从他在顺时针方向的下一个人开始重新从 1 报数 如此下去 直到所有人全 部出列为止 请设计一个程序求出出列顺序 1 利用单向循环链表存储结构模拟此过程 按照出列的顺序输出各个人的编号 2 输入数据 建立输入函数处理输入的数据 输入 m 的初值 n 输入每个人的密码 建立单向循环链表 3 输出形式 建立一个输出函数 将正确的出列顺序输出 二 设计过程二 设计过程 1 1 设计思想 数据结构 设计思想 数据结构 首先 设计实现 瑟夫环问题的存储结构 由于约瑟夫环本身具有循环性质 考 虑 采 用循环链表 为了统一对表中任意节点的操作 循环链表不带头结点 循环链表的结点定义为如下结构类型 structstruct LnodeLnode 定义链表定义链表 intint number number intint password password structstruct LnodeLnode next next Lnode p q head Lnode p q head 其次 建立一个不带头结点的循环链表并由头指针 first 指示 最后 设计 约瑟夫环问题的算法 2 2 设计表示 函数说明 设计表示 函数说明 1 循环链表抽象数据类型定义 struct Lnode 定义链表 int number int password struct Lnode next Lnode p q head 2 本程序包含一下几个模块 1 创建单链表 for i 1 inext q p q 3 形成循环链表 p next head 形成循环链表 4 主函数模块 int main 3 3 详细设计 主要算法 详细设计 主要算法 4 4 用户手册 使用说明 用户手册 使用说明 正确的执行完程序后 进去程序显示屏 首先按任意键继续 然后输入初始正确的执行完程序后 进去程序显示屏 首先按任意键继续 然后输入初始 密码 紧接着输入测试人的数量密码 紧接着输入测试人的数量 n n 其次依次输入测试人的密码 最后输入报 其次依次输入测试人的密码 最后输入报 数上限值数上限值 m m 完成后将进行结果的输出 完成后将进行结果的输出 三 测试报告三 测试报告 1 1 测试用例 测试用例 测试数据 m 的初值为 20 n 7 7 个人的密码依次为 3 1 7 2 4 7 4 首先 m 6 则正确的输出是什么 2 2 测试结果 测试结果 3 3 分析与探讨 分析与探讨 无论是用链表实现还是用数组实无论是用链表实现还是用数组实 现都有一个共同点 要模拟整个游戏过程 不仅程序写起来比较烦 而且时现都有一个共同点 要模拟整个游戏过程 不仅程序写起来比较烦 而且时 间复杂度高达间复杂度高达 O nm O nm 当 当 n n m m 非常大非常大 例如上百万 上千万例如上百万 上千万 的时候 几乎是的时候 几乎是 没有没有 办法在短时间内出结果的 我们注意到原问题仅仅是要求出最后的胜利者的办法在短时间内出结果的 我们注意到原问题仅仅是要求出最后的胜利者的 序号 而不是要读者模拟整个过程 因此如果要追求效率 就要打破常规 序号 而不是要读者模拟整个过程 因此如果要追求效率 就要打破常规 实施一点数学实施一点数学 策略 策略 为了讨论方便 先把问题稍微改变一下 并不影响原意 为了讨论方便 先把问题稍微改变一下 并不影响原意 问题描述 问题描述 n n 个人 编号个人 编号 0 n 1 0 n 1 从 从 0 0 开始报数 报到开始报数 报到 m 1m 1 的退出的退出 剩下的人继续从 剩下的人继续从 0 0 开始报数 求胜利者的编号 开始报数 求胜利者的编号 我们知道第一个人我们知道第一个人 编号一定是编号一定是 m 1 n m 1 n 出列之后 剩下的出列之后 剩下的 n 1n 1 个人组个人组 成了一个新的约瑟夫环 以编号为成了一个新的约瑟夫环 以编号为 k m nk m n 的人开始 的人开始 k k k 1k 1 k 2k 2 n 2 n 2 n 1 n 1 0 0 1 1 2 2 k 2k 2 并且从并且从 k k 开始报开始报 0 0 现在我们把他们的编号做一下转换 现在我们把他们的编号做一下转换 k k 0 0 k 1k 1 1 1 k 2k 2 2 2 k 3k 3 n 3n 3 k 2k 2 n 2n 2 序列序列 1 1 0 0 1 1 2 2 3 3 n 2 n 2 n 1n 1 序列序列 2 2 0 0 1 1 2 2 3 3 k 2 k 2 k k n 2 n 2 n 1n 1 序列序列 3 3 k k k 1 k 1 k 2 k 2 k 3 k 3 n 2 n 2 n 1 n 1 1 1 2 2 3 3 k 2 k 2 序列序列 4 4 0 0 1 1 2 2 3 3 5 5 6 6 7 7 8 8 n 3 n 3 n 2n 2 变换后就完完全全成为了变换后就完完全全成为了 n 1 n 1 个人报数的子问题 假如我们知道这个个人报数的子问题 假如我们知道这个 子问题的解 例如子问题的解 例如 x x 是最终的胜利者 那么根据上面这个表把这个是最终的胜利者 那么根据上面这个表把这个 x x 变回去变回去 不刚好就是不刚好就是 n n 个人情况的解吗 变回去的公式很简单 相信大家都可以个人情况的解吗 变回去的公式很简单 相信大家都可以 推出来 推出来 k m n k m n x x x kx k x x m nm n 而而 x x m nm n 可能大于可能大于 n n x x x x m n nm n n x m n x m n 得到得到 x x m nx x m n 如何知道如何知道 n 1 n 1 个人报数的问题的解 对 只要知道个人报数的问题的解 对 只要知道 n 2 n 2 个人的解就行个人的解就行 了 了 n 2 n 2 个人的解呢 当然是先求个人的解呢 当然是先求 n 3 n 3 的情况的情况 这显然就是一个倒推这显然就是一个倒推 问题 好了 思路出来了 下面写递推公式 问题 好了 思路出来了 下面写递推公式 令令 f f 表示表示 i i 个人玩游戏报个人玩游戏报 m m 退出最后胜利者的编号 最后的结果自然是退出最后胜利者的编号 最后的结果自然是 f n f n 递推公式递推公式 f 1 0 f 1 0 f i f i 1 m i f i f i 1 m i i 1 i 1 有了这个公式 我们要做的就是从有了这个公式 我们要做的就是从 1 n1 n 顺序算出顺序算出 f f 的数值 最后结果是的数值 最后结果是 f n f n 我们输出 我们输出 f n f n 由于是逐级递推 不需要保存每个 程序也是异常简单 由于是逐级递推 不需要保存每个 程序也是异常简单 注意编号是注意编号是 0 0 n 1 n 1 include include intint main void main void intint n n m m i i s 0 s 0 printfprintf N N M M scanf d d scanf d d forfor i 2 i 2 i n i1 1 k 2k 2 2 2 n n n k n k 1 1 n k 1 n k 1 k 1k 1 n 1 n 1 由上面一组式子可以推出 若知道新产生的由上面一组式子可以推出 若知道新产生的 n 1n 1 个数中某个数个数中某个数 x x 那么 那么 很显然可以推出很显然可以推出 x x 在原数列里的位置 即在原数列里的位置 即 x x x kx k n n 由此 我们可以得由此 我们可以得 到一个递推公式到一个递推公式 f 1 1f 1 1 f n f n 1 k nf n f n 1 k n n 1n 1 如果你认为上式可以推出约瑟夫环问题的解 很不幸 你错了 上面的如果你认为上式可以推出约瑟夫环问题的解 很不幸 你错了 上面的 递推公式中 在某种情况下 递推公式中 在某种情况下 f n 1 kf n 1 k 会整除会整除 n n 如 如 n 2n 2 k 3k 3 这时我们修 这时我们修 要对上式进行修正 要对上式进行修正 f n f n 1 k n if f n 0 f n n f n f n 1 k n if f n 0 f n n 问题得解 问题得解 程序代码如下 程序代码如下 include include intint main main intint n k s 1 n k s 1 scanf d d scanf d d for intfor int i 2 i n i 1 i 2 i n i 1 s s k i s s k i if s 0 s i if s 0 s i printf ans d n s printf ans d n s returnreturn 0 0 当然 我们还可以用递归方法解决此问题 当然 我们还可以用递归方法解决此问题 include include intint main main intint jos intjos int n intn int k k intint n k s n k s scanf d d scanf d d s jos n k s jos n k printf ans d n s printf ans d n s returnreturn 0 0 intint jos intjos int n intn int k k intint x x if n 1 x 1 if n 1 x 1 elseelse x jos n 1 k k n if x 0 x n x jos n 1 k k n if x 0 x n returnreturn x x 四 总结四 总结 我的这次数据结构课程设计的题目是我的这次数据结构课程设计的题目是 约瑟夫环约瑟夫环 通过对该题通过对该题 目的设计目的设计 我加深了对数据结构及存储结构的理解我加深了对数据结构及存储结构的理解 进一步地理解和进一步地理解和 掌握了课本中所学的各种数据结构 尤其是对单循环链表上基本运掌握了课本中所学的各种数据结构 尤其是对单循环链表上基本运 算的实现算的实现 学会了如何把学到的知识用于解决实际问题学会了如何把学到的知识用于解决实际问题 锻炼了自己锻炼了自己 动手的能力 动手的能力 通过这次数据结构课程设计 我感受最深的就是对通过这次数据结构课程设计 我感受最深的就是对 于循环链表的使用 可以说对循环链表有了比以前更进一步的认识 于循环链表的使用 可以说对循环链表有了比以前更进一步的认识 以前只是一知半解的 如果只给个题目自己根本不能把程序完整地以前只是一知半解的 如果只给个题目自己根本不能把程序完整地 编写出来 所以这次课程设计最大的收获就在于对循环链表有了一编写出来 所以这次课程设计最大的收获就在于对循环链表有了一 定的理解 包括其中的一系列操作 如建立一个循环链表 删除链定的理解 包括其中的一系列操作 如建立一个循环链表 删除链 表中的一个结点 增加一个结点等 表中的一个结点 增加一个结点等 在调试程序的时候我也有所在调试程序的时候我也有所 体会 虽然约瑟夫环问题不是很难 但调试的时候还是会出现很多体会 虽然约瑟夫环问题不是很难 但调试的时候还是会出现很多 错误 因此我们不能认为容易就不认真对待 在以后的学习中 要错误 因此我们不能认为容易就不认真对待 在以后的学习中 要 能不断发现问题 提出问题 解决问题 从不足之处出发 在不断能不断发现问题 提出问题 解决问题 从不足之处出发 在不断 学习中提高自己 学习中提高自己 两周的课程设计很短暂 但其间的内容是很充两周的课程设计很短暂 但其间的内容是很充 实的 在其中我学习到了很多平时书本中无法学到的东西 积累了实的 在其中我学习到了很多平时书本中无法学到的东西 积累了 经验 锻炼了自己分析问题 解决问题的能力 并学会了如何将所经验 锻炼了自己分析问题 解决问题的能力 并学会了如何将所 学的各课知识融会 组织起来进行学习 总而言之这两周中我学到学的各课知识融会 组织起来进行学习 总而言之这两周中我学到 很多 受益匪浅 很多 受益匪浅 五 附录 源程序 五 附录 源程序 include include include include string h struct Lnode 定义链表 int number int password struct Lnode next Lnode p q head int main void system color 0a system title 邦德的荣耀 printf n printf n printf n printf n printf n printf n printf n int n n 个人 int i int m 初始报数上限值 int j k s u char ch char mima 100 007 char input 100 printf 约瑟夫环程序设计 n n printf 007 倾情奉献 n n printf 邦德的荣耀 邦德的 荣耀 n n printf 密码为 007 n system pause for k 0 s 3 k 2 k s printf 请输入密码 n gets input if strcmp mima input 0 比较字符串 mima 和 input 的 大小 此时相等 printf 密码正确 n break else printf 密码错误 你还有 d 次机会 n s 1 while s 1 return 0 for u 0 u 套上 for 循环以判断是否继续进行 printf 输入测试人的数量 n 输入测试人的数量 scanf d loop if n 0 检验 n 是否满足要求 如不满足重新输入 n 值 printf n n 是错的 n n pri