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

《《应用数据结构》课程设计报告书 曹贝.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、学号：23课程设计题目锁链学院管理学院专业信息管理与信息系统班级1203姓名曹贝指导教师江长斌2014年07月03日课程设计任务书学生姓名：曹贝专业班级：信管1203指导教师：江长斌工作单位：管理学院题目：锁链初始条件：（问题描述）一个国王因为听信谗言将一个无辜的数学家关进了监狱。虽然事后发现确属冤枉，但碍于面子，国王不肯认错。为了挽回，于是国王决定用Bytish锁链将其锁在墙上。这种锁链由n（10≤n≤1000）个固定在墙上的铁环和铁棒组成。由于环不是都套在棒上，要想把整副锁链取下是十分困难的。数学家必须自己通过不断取下和套上铁环最

2、终将所有铁环都取下才能获得自由。取下或套上铁环的规则是：Ø铁环从1、2、……、n依次编号。Ø一次只能把一个环取下或套上。Ø编号为1的环无论何时都能取下或套上。Ø如果编号为1、……、k-1（1≤k≤n）的环已经从棒上取下，并且k环套在棒上，则可以取下或套上编号为k+1的环。Ø写一个程序，读入锁链描述并计算从棒上取下所有环所需的最少步数。【基本要求】显然，可以运用递归的方法解决此问题。但是你能否找到一个非递归算法呢？要求完成的主要任务:（包括课程设计工作量及其技术要求、说明书撰写等具体要求）显然，通过枚举前i个环的解锁过程可以从中找出解题

3、的思路。当n=1时，直接移除即得解。当n=2时，显然不能先移出1环，再移除2环。因为根据约束条件，必须1环在棒上才能移除2环。因此移除的步骤应该是先2环，再1环。当n=3时，移除3环的条件是2环在，1环卸，于是可以先移除1环，然后移除3环，然后套上1环，然后移除2环和1环。当n≥4的情形请自行推导。问题分析：该锁链套卸环的过程与解九连环游戏的要求类似，结果分析得：1个环:   12个环:   23个环:   54个环:   105个环:   216个环:   427个环:   858个环:   170…可得到公式:n为环数步数=[2^

4、(n+1)-0.5(-1)^n-1.5]/3n为偶数时，步数=(2^(n+1)-1)/3n为奇数时，步数=(2^(n+1)-2)/3时间安排：序号设计内容所用时间1问题分析和任务定义0.5天2数据类型和系统设计0.5天3编码实现和静态检查3天4上机准备和上机调试2天5总结和整理设计报告1天合计7天指导教师签名：2014年06月23日系主任（或责任教师）签名：2014年07月03日锁链1.需求分析1.1输入与输出1.2标题（黑体小3号字）以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：（l）输入的形式和输入值的范围；（

5、2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2.概要设计2.1标题（黑体小3号字）2.2标题（黑体小3号字）说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。3.详细设计3.1标题（黑体小3号字）3.2标题（黑体小3号字）实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法（伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序）；画出函数的调

6、用关系图。1.调试分析4.1标题（黑体小3号字）4.2标题（黑体小3号字）内容包括：（l）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；（2）算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想；（3）经验和体会等。2.用户使用说明5.1标题（黑体小3号字）5.2标题（黑体小3号字）说明如何使用编写的程序，详细列出每一步的操作步骤。3.测试结果6.1标题（黑体小3号字）6.2标题（黑体小3号字）列出测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。4.附录（

7、源代码）带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。值得注意的是，报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写（当然也可以最后用实验报告纸誊清或打印）。本科生课程设计成绩评定表姓名曹贝性别女专业班级信息管理与信息系统1203课程设计题目：锁链课程设计答辩或质疑记录：成绩评定依据：评定项目评分成绩1．设计原创性达到80%（30分）2．程序执行结果实现指导书中的所有基本要求（20分）3．设计结果（软件程序）正确（10分）4．设计报告的规范化（10分）5.答辩（30分）总分（1

8、00分）备注：成绩等级：优（90分—100分）、良（80分—89分）、中（70分—79分）、及格（60分—69分）、60分以下为不及格。若第一项低于20分，或第一项与第五项之和低于35分，则课程设计成绩不能及格。最终评定