2010计算机算法分析与设计任务书.doc

算法分析与设计任务书1 课程设计的目的《算法分析与设计》是信息与计算科学专业集中实践性环节之一，是学习完《算法分析与设计》课程后进行的一次全面的综合练习其目的是：（1）要达到理论与实际应用相结合，使学生能够学会常用的几种算法思想以及对算法进行分析，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能2）在实践中认识为什么要学习算法分析与设计，掌握算法的设计思想与程序设计语言之间的关系，是前面所学知识的综合和回顾2 课程设计的基本要求（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；（5）设计的题目要求达到一定工作量，并具有一定的深度和难度；（6）编写出课程设计说明书3 课程设计内容及安排（1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？（2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。

逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；（3）详细设计：定义相应的存储结构并写出各函数的伪代码算法在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体详细设计的结果是对数据结构和基本操作进行进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；（4）程序编码：把详细设计的结果进一步求精为程序设计语言程序同时加入一些注解和断言，使程序中逻辑概念清楚；（5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；（6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果算法的时间、空间复杂性分析；（7）撰写课程设计报告4 课程设计报告的内容设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整，内容及要求详见“课程设计报告规范”， 其中“3. 课程设计报告内容”中一般应包括以下内容：4.1 需求分析以无歧义陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入和输出结果，含有错误的输入和输出结果。

4.2 概要设计说明本程序中用到的所有抽象数据类型的定义、主控程序的流程以及各程序模块之间的层次（调用）关系4.3 详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、N–S 图或PAD 图进行描述，画出函数和过程的调用关系图4.4 调试分析内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；4.5 测试结果列出你的测试结果，包括输入和输出这里的测试数据应该完整和严格，最好多于需求分析中所列4.6 用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤5 课程设计考核方法及成绩评定课程设计结束时，要求学生写出课程设计报告（可不附源程序），可运行的软件系统（包括源程序）课程设计成绩分两部分，设计报告及软件系统占70％，集中上机占30％6 进度安排整体设计和详细设计 2天编写代码 2天调试和测试 2天课程设计报告书写 1天演示软件和答辩 另行安排7 课程设计题目7.1 棋盘覆盖【间题描述】在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。

在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖基本要求】（1）输入k以及特殊方格所在的行号dr和特殊方格的列号dc2）要求输出每一步用什么形态L型骨牌覆盖，覆盖后得到的棋盘图形3）如果输出的结果只是用矩阵表示则为良好，用图形表示则为优测试数据】【实现提示】使用分治策略，把棋盘划分成4个小棋盘，然后用一个L型骨牌覆盖将这4个小棋盘变为都具有特殊方格的棋盘7.2 Hanoi塔问题（*）【问题描述】设a，b，c是三个塔座开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为1,2,…,n，要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置在移动圆盘时应遵守以下移动规则：规则（1）每次只能移动一个圆盘；规则（2）任何时刻都部允许将较大的圆盘压在较小的圆盘之上；规则（3）在满足移动规则（1）和（2）的前提下，可将圆盘移至a，b，c中任一塔座上基本要求】（1）设计出Hannoi塔游戏，供用户玩；（2）提供正确的搬运方法实现说明】正确的搬运方法使用递归方法实现测试数据】7.3 矩阵连乘问题【问题描述】给定n个矩阵{},其中和是可乘的，i＝1,2,…,n-1。

考察这n个矩阵的连乘积，通过加括号方式，找出矩阵乘积所需的最少计算量的方法基本要求】输入每个矩阵的行和列，要求输出最少计算量的矩阵乘积方法，如实现说明】使用动态规划方法7.4 多边形游戏（*）【问题描述】多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形每个顶点被赋予一个整数值，每条边被赋予一个运算符“＋”或“*”所有边依次用整数从1到n编号游戏第1步，将一条边删除随后n-1步按以下方式操作：选择一条边E及由E连接着的2个顶点v1和v2；用一个新的顶点取代边E及用E连接着的2个顶点v1和v2，将由顶点v1和v2的整数值通过边E上的运算得到的结果赋予新顶点最后，所有边都被删除，游戏结束游戏的得分就是所剩顶点上的整数值基本要求】设计该游戏供用户玩；对于给定的多边形，给出最高得分计算实现说明】使用动态规划方法7.5 0-1背包问题【问题描述】给定n种物品和一背包物品i的重量是，其价值为，背包的容量为c问应如何选择装入背包种的物品，使得装入背包种物品的总价值最大基本要求】使用动态规划、回溯法以及分支界限三种方法实现测试数据】【实现提示】7.6 排序方法【问题描述】给定n个元素，要求对这n个元素进行排序。

基本要求】使用多种排序方法，越多越好；比较每种排序方法的时间复杂度和空间复杂度测试数据】【实现提示】7.7 哈夫曼编码译码器【问题描述】设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)基本要求】（1）输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码实现说明】（1）在构造哈夫曼树时，可以利用不同的线性表存放二叉树：用顺序表、单链表、循环单链表、双向链表、循环双链表；（2）在构造哈夫曼树时，可以利用优先队列存放二叉树：顺序队列、链队列（可以是单链表、双链表等，还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级；（3）二叉树本身也可以用静态数组模拟；（4）使用贪心算法7.8 迷宫问题（*）【问题描述】设计一个迷宫并给出正确走法如：1111111111110111000110011100其中0表示可以走，1表示不能走，每一步只能向上下左右移动。

基本要求】（1）给出迷宫的正确走法，包括没有解的情况；（2）要求界面友好测试数据】【实现提示】使用回溯的方法7.9 。