没有合适的资源?快使用搜索试试~ 我知道了~
数据结构课程设计报告
需积分: 7 4 下载量 52 浏览量
2009-06-09
13:40:16
上传
评论 1
收藏 292KB DOC 举报
温馨提示
试读
11页
Hanoi(汉诺)塔问题实现5层汉诺塔的调整过程;:Josephus问题建立一个文件,包括某人7个人的情况;
资源详情
资源评论
资源推荐
徐州师范大学数学科学学院
课 程 设 计 报 告
200 8
-
200 9
学年度 第 二 学期
课程名称: 数据结构
设计题目:Hanoi(汉诺)塔问题/ Josephus 问题
姓 名:
学 号:
教 师:
成 绩:
一 课程设计题
1.Hanoi(汉诺)塔问题
这是一个古典的数学问题,是一个用递归方法解题的典型例子。
问题是这样的:古代有一个梵塔,塔内有 3 个座 A、B、C,开始时 A 座上有
64 个盘子,盘子大小不等,大的在下,小的在上(如下图)。有一个老和尚想
把这 64 个盘子从 A 座移到 C 座,但每次只允许移动一个盘,且在移动过程中
在 3 个座上都始终保持大盘在下,小盘在上。在移动过程中可以利用 B 座,要
求编程序打印出移动的步骤。
功能:编程序显示 n(n<=9)层汉诺塔的调整过程。
要求:
1. 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;
2. 完成最低要求:实现 5 层汉诺塔的调整过程;
3. 进一步要求:直至实现 n=9 时的情况。有兴趣的同学可以自己扩充系统功
能。
2. Josephus 问题
功能:编号是 1,2,……,n 的 n 个人按照顺时针方向围坐一圈,每个人只有一
个密码(正整数)。一开始任选一个正整数作为报数上限值 m,从第一个人开
始顺时针方向自 1 开始顺序报数,报到 m 时停止报数。报 m 的人出列,将他的
密码作为新的 m 值,从他在顺时针方向的下一个人开始重新从 1 报数,如此下
去,直到所有人全部出列为止。令 n 最大值取 30。要求设计一个程序模拟此过
程,求出出列编号序列。
A B C
要求:
1. 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;
2. 完成最低要求:建立一个文件,包括某人 7 个人的情况;
3. 进一步要求:有兴趣的同学可以自己扩充系统功能。
测试数据:
m 的初值为 20,n=7 ,7 个人的密码依次为 3,1,7,2,4,7,4。
二 程序分析
1.Hanoi(汉诺)塔问题
将 n 个盘子从 A 座移到 C 座可以分解为下面 3 个步骤:
(1)将 A 座上 n-1 个盘子移到 B 座上(借助 C 座);
(2)将 A 座上剩下的一个盘子移到 C 座上;
(3)将 n-1 个盘子从 B 座移到 C 座上(借助 A 座)。
事实上,上面步骤包含两种操作:
(1)将多个盘子从一个座移到另一个座上,这是一个递归过程;
(2)将一个盘子从下座上移到另一个座上。
于是用两个函数分别实现上面两种操作,用 hanoi 函数实现第 1 种操作,用
move 函数实现第 2 种操作。
2. Josephus 问题
Josephus 问题就是说,n 个人围成一圈做游戏,游戏将决出一个胜利者。从第
s 个人起,顺时针计数,每数到第 m 个人时,该人就离开。接着又从下一个人
开始数数。数到第 m 个人时,该人就离开,如此不断反复进行,最后剩下的人
就是胜利者。
在这里,我们扩展为求 w 个胜利者。n,s,m 和 w 在应用程序里输入。…数数开
始时位置 s 和计数间隔 m,求获胜者作为操作。求获胜者需要操作代表一圈人
的数组,定义一个指针,包括数 m 个人,人离开,返回离开人编号等操作。
三 程序流程图
1.Hanoi(汉诺)塔问题
1.1 主程序流程图:
剩余10页未读,继续阅读
shuxuekexuexueyuan
- 粉丝: 0
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0