《应用数据结构》课程设计报告书 曹贝

  本文关键词：数据结构课程设计报告 通讯录的制作，由笔耕文化传播整理发布。

学

号：

0121203490323

课 程 设 计

题 学 专 班 姓

目 院 业 级 名

锁链 管理学院 信息管理与信息系统

1203
曹贝 江长斌

指导教师

2014<

br />
年

07

月

03

日

课程设计任务书
学生姓名： 指导教师： 题 目：锁链 曹贝
江长斌

专业班级： 工作单位：

信管 1203 管理学院

初始条件： （问题描述）
一个国王因为听信谗言将一个无辜的数学家关进了监狱。虽然事后发现确属冤枉， 但碍于面子，国王不肯认错。为了挽回，于是国王决定用 Bytish 锁链将其锁在墙上。 这种锁链由 n （10≤n≤1000） 个固定在墙上的铁环和铁棒组成。 由于环不是都套在棒上， 要想把整副锁链取下是十分困难的。数学家必须自己通过不断取下和套上铁环最终将所 有铁环都取下才能获得自由。取下或套上铁环的规则是： ? 铁环从 1、2、……、n 依次编号。 ? 一次只能把一个环取下或套上。 ? 编号为 1 的环无论何时都能取下或套上。 ? 如果编号为 1、……、k-1（1≤k≤n）的环已经从棒上取下，并且 k 环套在棒上， 则可以取下或套上编号为 k+1 的环。 ? 写一个程序，读入锁链描述并计算从棒上取下所有环所需的最少步数。 【基本要求】 显然，可以运用递归的方法解决此问题。但是你能否找到一个非递归算法呢？

要求完成的主要任务: （包括课程设计工作量及其技术要求、 说明书撰写等具体要求）
显然，通过枚举前 i 个环的解锁过程可以从中找出解题的思路。 当 n=1 时，直接移除即得解。 当 n=2 时，显然不能先移出 1 环，再移除 2 环。因为根据约束条件，必须 1 环在棒 上才能移除 2 环。因此移除的步骤应该是先 2 环，再 1 环。 当 n=3 时，移除 3 环的条件是 2 环在，1 环卸，于是可以先移除 1 环，，然后移除 3 环，然后套上 1 环，然后移除 2 环和 1 环。 当 n≥4 的情形请自行推导。 问题分析： 该锁链套卸环的过程与解九连环游戏的要求类似，结果分析得： 1 个环: 1 2 个环: 2 3 个环: 5 4 个环: 10 5 个环: 21 6 个环: 42 7 个环: 85 8 个环: 170

… 可得到公式: n 为环数 步数=[2^(n+1)-0.5*(-1)^n-1.5]/3 n 为偶数时，步数=(2^(n+1)-1)/3 n 为奇数时，步数=(2^(n+1)-2)/3

时间安排：
序号 1 2 3 4 5 设计内容 问题分析和任务定义 数据类型和系统设计 编码实现和静态检查 上机准备和上机调试 总结和整理设计报告 合 计 所用时间 0.5 天 0.5 天 3天 2天 1天 7天

指导教师签名： 系主任（或责任教师）签名：

2014 年 06 月 23 日 2014 年 07 月 03 日

武汉理工大学《应用数据结构》课程设计说明书

锁链
1. 需求分析
1.1 输入与输出 1.2 标题（黑体小 3 号字）
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定： （l）输入的形式和输入值的范围； （2）输出的形式； （3）程序所能达到的功能； （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2. 概要设计
2.1 标题（黑体小 3 号字） 2.2 标题（黑体小 3 号字）
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的 层次（调用）关系。

3. 详细设计
3.1 标题（黑体小 3 号字） 3.2 标题（黑体小 3 号字）
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和 其他模块也都需要写出伪码算法（伪码算法达到的详细程度建议为：按照伪码算法可以在 计算机键盘直接输入高级程序设计语言程序）；画出函数的调用关系图。

1

武汉理工大学《应用数据结构》课程设计说明书

4. 调试分析
4.1 标题（黑体小 3 号字） 4.2 标题（黑体小 3 号字）
内容包括： （l）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析； （2） 算法的时空分析 （包括基本操作和其他算法的时间复杂度和空间复杂度的分析） 和改进设想； （3）经验和体会等。

5. 用户使用说明
5.1 标题（黑体小 3 号字） 5.2 标题（黑体小 3 号字）
说明如何使用编写的程序，详细列出每一步的操作步骤。

6. 测试结果
6.1 标题（黑体小 3 号字） 6.2 标题（黑体小 3 号字）
列出测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分 析中所列。

7. 附录（源代码）
带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。值得注意的 是，报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成， 而不是最后补写（当然也可以最后用实验报告纸誊清或打印）。

2

本科生课程设计成绩评定表
姓 名

曹贝
信息管理与信息系统 1203

性 别

女

专业班级

课程设计题目：锁链 课程设计答辩或质疑记录：

成绩评定依据：

评

定

项

目

评分成绩

1．设计原创性达到 80%（30 分） 2．程序执行结果实现指导书中的所有基本要求（20 分） 3．设计结果（软件程序）正确（10 分） 4．设计报告的规范化（10 分） 5. 答辩（30 分） 总分（100 分）
备注：成绩等级：优（90 分—100 分） 、良（80 分—89 分） 、中（70 分—79 分） 、及格（60 分—69 分） 、 60 分以下为不及格。若第一项低于 20 分，或第一项与第五项之和低于 35 分，则课程设计成绩不能及格。

最终评定成绩（以优、良、中、及格、不及格评定）

指导教师签字： 2014 年 07 月 03 日



更多相关文档:

数据结构课程设计报告

林碧英 设计周数: 1 周 日期:2011 年 6 月 25 日 程序设计报告 一、课程设计的目的与要求 1. 目的: 应用数据结构和算法来设计相应的程序,培养学生问题求解模...

数据结构课程设计——学生成绩管理系统报告书

课程设计报告书设计名称: 题目: 数据结构(C++版) 学生成绩管理系统 XXX 计算机科学与技术 计科本 XXX 班 XXXXXX XXX 7 月 12 日 学生姓名: 专班学业: 别:...

数据结构课程设计

数据结构课程 设计报告题 目:文章中单词查找 专 业: 软件工程 学校 集美大学 专业 软件工程 姓名 殷梓健 学号 201521122028 性别 帅哥 起止时间: 2016.07.06-...

数据结构课程设计

数据结构课程 设计报告题 目:文章中单词查找 专 业: 软件工程 起止时间: 2015.07.06-2015.07.10 集美大学计算机工程学院软件工程教研室制 2015 年 7 月 09...

数据结构(C语言版)课程设计报告表达式求值

《数据结构 课程设计》表达... 13页 8财富值 《...(报告正文部分) : (要求:正文部分一律用小四号字,...时间的课程设计,本人对计算机的应用、数据结构的作用...

数据结构课程设计报告 通讯录的制作

数据结构课程设计报告 通讯录的制作_计算机软件及应用_IT/计算机_专业资料。山东...《数据结构》是一门重要的专业基础课,是计算机理论和应用的核心基础课程。 数据...

数据结构课程设计报告书模板--修改

数据结构课程设计报告书模板--修改_理学_高等教育_教育专区。隔热大连...参考文献 [1] 赵波、霍利等编著. 《数据结构实用教程》(C 语言版)清华大学...

数据结构课程设计报告

《数据结构》是一门重要的专业 基础课,是计算机理论和应用的核心基础课程。 数据结构课程设计,要求学生在数据结构的逻辑特性和物理表示、数据结构的选择 和应用、...

My算法与数据结构课程设计报告

***图的基本操作及应用***\n"; * * * * * 1 无向图的基本操作及应用...{ cout<<"\n ***《数据结构课程设计》***\n"; cout<<" cout<<" cout...

数据结构约瑟夫环课程设计报告书

《数据结构》 》 课程设计报告书 设计题目: 专班姓业: 级: 名: 约瑟夫环 指导教师: 完成日期: 目一、 二、 三、 四、 五、 六、 七、 八、 九、 十...

更多相关标签:

  本文关键词：数据结构课程设计报告 通讯录的制作，由笔耕文化传播整理发布。