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

1、算法分析与设计任务书1 课程设计的目的算法分析与设计是信息与计算科学专业集中实践性环节之一，是学习完算法分析与设计课程后进行的一次全面的综合练习。其目的是：（1）要达到理论与实际应用相结合，使学生能够学会常用的几种算法思想以及对算法进行分析，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。（2）在实践中认识为什么要学习算法分析与设计，掌握算法的设计思想与程序设计语言之间的关系，是前面所学知识的综合和回顾。2 课程设计的基本要求（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和

2、技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；（5）设计的题目要求达到一定工作量，并具有一定的深度和难度；（6）编写出课程设计说明书。3 课程设计内容及安排（1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？（2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每

3、个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；（3）详细设计：定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作进行进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；（4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；（5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数

4、据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；（6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；（7）撰写课程设计报告。4 课程设计报告的内容设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整，内容及要求详见“课程设计报告规范”， 其中“3. 课程设计报告内容”中一般应包括以下内容：4.1 需求分析以无歧义陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1)

5、输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入和输出结果，含有错误的输入和输出结果。4.2 概要设计说明本程序中用到的所有抽象数据类型的定义、主控程序的流程以及各程序模块之间的层次（调用）关系。4.3 详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、NS 图或PAD 图进行描述，画出函数和过程的调用关系图。4.4 调试分析内容包括：调试过程中遇到的问题是如何解

6、决的以及对设计与实现的回顾讨论和分析；4.5 测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。4.6 用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。5 课程设计考核方法及成绩评定课程设计结束时，要求学生写出课程设计报告（可不附源程序），可运行的软件系统（包括源程序）。课程设计成绩分两部分，设计报告及软件系统占70，集中上机占30。6 进度安排整体设计和详细设计 2天编写代码 2天调试和测试 2天课程设计报告书写 1天演示软件和答辩 另行安排7 课程设计题目7.1 棋盘覆盖【间题描述】在一个2k2k 个方格组成的棋盘中，恰有一个方

7、格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。【基本要求】（1）输入k以及特殊方格所在的行号dr和特殊方格的列号dc。（2）要求输出每一步用什么形态L型骨牌覆盖，覆盖后得到的棋盘图形。（3）如果输出的结果只是用矩阵表示则为良好，用图形表示则为优。【测试数据】【实现提示】使用分治策略，把棋盘划分成4个小棋盘，然后用一个L型骨牌覆盖将这4个小棋盘变为都具有特殊方格的棋盘。7.2 Hanoi塔问题（*）【问题描述】设a，b，c是三个塔座。开始时，在塔座a上

8、有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为1,2,n，要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则（1）每次只能移动一个圆盘；规则（2）任何时刻都部允许将较大的圆盘压在较小的圆盘之上；规则（3）在满足移动规则（1）和（2）的前提下，可将圆盘移至a，b，c中任一塔座上。【基本要求】（1）设计出Hannoi塔游戏，供用户玩；（2）提供正确的搬运方法。【实现说明】正确的搬运方法使用递归方法实现。【测试数据】7.3 矩阵连乘问题【问题描述】给定n个矩阵,其中和是可乘的，i1,2,n-1。考察这n个矩阵的连乘积，通过

9、加括号方式，找出矩阵乘积所需的最少计算量的方法。【基本要求】输入每个矩阵的行和列，要求输出最少计算量的矩阵乘积方法，如。【实现说明】使用动态规划方法。7.4 多边形游戏（*）【问题描述】多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：选择一条边E及由E连接着的2个顶点v1和v2；用一个新的顶点取代边E及用E连接着的2个顶点v1和v2，将由顶点v1和v2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏

10、的得分就是所剩顶点上的整数值。【基本要求】设计该游戏供用户玩；对于给定的多边形，给出最高得分计算。【实现说明】使用动态规划方法。7.5 0-1背包问题【问题描述】给定n种物品和一背包。物品i的重量是，其价值为，背包的容量为c。问应如何选择装入背包种的物品，使得装入背包种物品的总价值最大。【基本要求】使用动态规划、回溯法以及分支界限三种方法实现。【测试数据】【实现提示】7.6 排序方法【问题描述】给定n个元素，要求对这n个元素进行排序。【基本要求】使用多种排序方法，越多越好；比较每种排序方法的时间复杂度和空间复杂度。【测试数据】【实现提示】7.7 哈夫曼编码译码器【问题描述】设计一个哈夫曼编码/

11、译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。【基本要求】（1）输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码。【实现说明】（1）在构造哈夫曼树时，可以利用不同的线性表存放二叉树：用顺序表、单链表、循环单链表、双向链表、循环双链表；（2）在构造哈夫曼树时，可以利用优先队列存放二叉树：顺序队列、链队列（可以是单链表、双链表等，

12、还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级；（3）二叉树本身也可以用静态数组模拟；（4）使用贪心算法7.8 迷宫问题（*）【问题描述】设计一个迷宫并给出正确走法。如：001111111111111100011111111111101100001111111100011100000111111011111110001111000000001001111000000011100其中0表示可以走，1表示不能走，每一步只能向上下左右移动。【基本要求】（1）给出迷宫的正确走法，包括没有解的情况；（2）要求界面友好。【测试数据】【实现提示】使用回溯的方法。7.9 继续邮资问题【问题描述

13、】假设某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。【基本要求】 输入任意的m和n都能设计出最佳的方案，并给出连续邮资区间。【实现说明】【测试数据】7.10 图的m着色问题【问题描述】给定一个地图，要求给出该地图的最少着色方案【基本要求】（1）把地图以及最少着色的方案显示出来则为良好。（2）有友好的界面则为优【实现说明】7.11 猜数字游戏（*）【问题描述】孩子想1个由4种颜色组成的序列（4种颜色不一定完全不同）。每种颜色只能是6种颜色之一。方便起见

14、，我们用数字1到6表示6种颜色。计算机必须根据孩子的回答找出孩子所想的颜色序列。计算机在屏幕上显示一个序列，孩子用键盘回答以下两个问题：猜对的颜色中位置不对的有几个？猜对的颜色中位置对的有几个？【基本要求】编程使至多6次问答后猜出序列，如果办不到，至多10次问答后猜出序列。【实现说明】【测试数据】 如孩子想的是4655计算机猜想 颜色对位置错的数目 颜色和位置都对的数目1234 1 05156 2 16165 1 15625 1 25653 1 24655 0 47.12 大整数计算器【问题描述】设计一个计算器实现两个任意长得整数的加、减、乘、除。【基本要求】设计一个实现任意长的整数进行四则运

15、算的演示程序，要求输入任意长的整数进行四则运算，都能得到精确的结果。【实现说明】7.13 查找搜索技术【问题描述】给定任意的数组，对于给定的数，查找是否在数组中，如果在，则返回给定数在数组的位置，不在则返回不在信息。【基本要求】（1）使用多种搜索方法，越多越好，其中二分搜索技术、线性时间选择是必须的；（2）比较每种排序方法的时间复杂度和空间复杂度。【实现说明】7.14 Tom,Jerry和奶酪（*）【问题描述】猫Tom和鼠Jerry同住在一矩阵地窖中。猫要吃鼠，鼠要吃奶酪。地窖中有2种地砖：有洞砖与无洞砖。一个洞足以让鼠钻入，但猫不能。以菜单形式完成以下任务：随机地生成一个地窖，并给猫、鼠和奶

16、酪安排一个位置。如：ffffffffffffffffppppppppppppCffhfffffffffffpffpppjhppppppppffpffffffpfffffffppppppppppTppffffffffffffffff其中c表示猫，j表示鼠，h表示洞，f表示不能通行（2） 鼠先行，猫后行。两者皆满足以下规定：1）必须上、下、左或右移动2）鼠必须走1步（穿过p或h）3）猫必须走1或2步（穿过p）（3） 当鼠吃到奶酪或猫抓到鼠时，游戏结束。【基本要求】【实现说明】7.15 布线问题【问题描述】印刷电路板将布线区域划分成nm个方格阵列，精确的电路布线问题要求确定连接方格a的中点到方格b的

17、中点的最短布线方案。在布线时，电路只能沿着直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。【基本要求】（1）解决题目的问题（2）提供友好的界面【实现说明】使用分支限界法。7.16 魔方工具包 （*）【问题描述】一个魔方是一个由333个小立方体组成的立方体。最初立方体的6个面分别涂上不同颜色，我们称之为“最初魔方”。魔方的每一面上的33个小立方体组成它的一层。魔方所能见到的每一层（6个面）都能旋转90，180，270或360度。所有层的旋转轴都垂直于面且通过其中心。旋转的结果是另一个魔方，它的所有面的颜色都改变了。现在我们用字符来代替颜色：U=上，D

18、=下，F=前，B=后，L=左，R=右。任何一个序列的旋转都能表示成U,R,F,B,L,D中一些字符组成的字符串，其中每个字符表示它所指定的面顺时针旋转90度。【基本要求】（1）编程完成以下3个任务（菜单形式），你可以假设任何输入的字串长度都=35。你的算法能处理非法输入的情况，如：输入 输出L LLL LLLLL LLLLLLL “”(空串LLLLL LLLRRRFFFFRLB LLLBHELLO “error”（2）判断输入的2个字串的旋转结果是否相同。如输入一 输入二 输出RU UR noRRFFRRFFRRFFRRFF FFRRFFRR yesRRFFRRFFRRFFRRFF RRFFR

19、RFF no（3）求出输入字符串至少须使用几次才能将魔方转回到“最初魔方”（一定大于0）输入 输出L 4DD 2BULB 36RUF 80BLUFF 180【实现说明】7.17 图的建立与输出 【问题描述】建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。【基本要求】给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果【实现说明】 无7.18 图的建立与输出 【问题描述】建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶

20、点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。【基本要求】给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果。【实现说明】 无7.19 以队列实现的仿真技术预测理发馆的经营状况（*）【问题描述】理发馆一天的工作过程如下：理发馆有N把理发椅，可同时为N位顾客进行理发。理发师分三个等级（一级、二级、三级），对应不同的服务收费。当顾客进门时，需选择某级别理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候。一旦该级别的理发师有顾客理发完离去，排在队头的顾客便可开始理发。若理发馆每天连续营业T分钟，求一天内顾客在理发馆内的平均逗留时间；顾客排队等候理发的队列长

21、度平均值；营业时间到点后仍需完成服务的收尾工作时间；统计每天的营业额；统计每天不同级别理发师的创收。【基本要求】模拟理发馆一天的工作过程：必须采用事件驱动的离散模型（参考教科书3.5节离散事件模拟p65）；每个顾客到达和下一顾客到达时间的间隔应是随机的；理发师编号、理发师级别和每天的营业时间由用户输入；某顾客挑选某一个级别的理发师而不得时，选第一个队列排队等待 ；每个顾客进门时将生成三个随机数:durtime:进门顾客理发所需服务时间（简称：理发时间）；intertime:下一顾客将到达的时间间隔（简称：间隔时间）；select:服务选项 。服务收费：应包含服务时间和理发师级别两个因素。除了输出统计的数据外，还需要显示理发馆的状态，可以采用文本方式（横向显示每张椅编号、理发师级别。纵向表示等待该理发师理发的排队长度）。【实现说明】 用户输入每位理发师编号、级别号和营业的时间，结合随机数进行测试。7.20 防抄袭管理系统（*）【问题描述】对于给定的文档，如word文档，txt文档等，找出文档的相似度。【基本要求】要求找出给定的两个