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

算法分析与设计任务书算法分析与设计任务书 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和特殊方格的列号dc 2 要求输出每一步用什么形态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 考察 12 n A AA i A 1i A 这n个矩阵的连乘积 通过加括号方式 找出矩阵乘积所需的最少计 12 n A AA 算量的方法 基本要求 输入每个矩阵的行和列 要求输出最少计算量的矩阵乘积方法 如 1234 A A A A 实现说明 使用动态规划方法 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 i w i v 问应如何选择装入背包种的物品 使得装入背包种物品的总价值最大 基本要求 使用动态规划 回溯法以及分支界限三种方法实现 测试数据 实现提示 7 6 排序方法排序方法 问题描述 给定n个元素 要求对这n个元素进行排序 基本要求 使用多种排序方法 越多越好 比较每种排序方法的时间复杂度和空间复杂度 测试数据 实现提示 7 7 哈夫曼编码译码器哈夫曼编码译码器 问题描述 设计一个哈夫曼编码 译码系统 对一个文本文件中的字符进行哈夫曼编码 生成编码文件 压缩文件 后缀名 cod 反过来 可将一个压缩文件译码还原为一个 文本文件 txt 基本要求 1 输入一个待压缩的英文文本文件 统计文本文件中各字符的个数作为 权值 生成哈夫曼树 2 将文本文件利用哈夫曼树进行编码 生成压缩文件 后缀名cod 3 输入一个待解压的压缩文件名称 并利用相应的哈夫曼树将编码序列 译码 实现说明 1 在构造哈夫曼树时 可以利用不同的线性表存放二叉树 用顺序表 单链表 循环单链表 双向链表 循环双链表 2 在构造哈夫曼树时 可以利用优先队列存放二叉树 顺序队列 链队 列 可以是单链表 双链表等 还可以用静态结构去实现 可以分别在入队 列或出队列时实现优先级 3 二叉树本身也可以用静态数组模拟 4 使用贪心算法 7 8 迷宫问题 迷宫问题 问题描述 设计一个迷宫并给出正确走法 如 001111111111111 100011111111111 101100001111111 100011100000111 111011111110001 111000000001001 111000000011100 其中0表示可以走 1表示不能走 每一步只能向上下左右移动 基本要求 1 给出迷宫的正确走法 包括没有解的情况 2 要求界面友好 测试数据 实现提示 使用回溯的方法 7 9 继续邮资问题继续邮资问题 问题描述 假设某国家发行了n种不同面值的邮票 并且规定每张信封上最多只允许贴 m张邮票 连续邮资问题要求对于给定的n和m的值 给出邮票面值的最佳设计 在1张信封上贴出从邮资1开始 增量为1的最大连续邮资区间 基本要求 输入任意的m和n都能设计出最佳的方案 并给出连续邮资区间 实现说明 测试数据 7 10 图的图的 m 着色问题着色问题 问题描述 给定一个地图 要求给出该地图的最少着色方案 基本要求 1 把地图以及最少着色的方案显示出来则为良好 2 有友好的界面则为优 实现说明 7 11 猜数字游戏 猜数字游戏 问题描述 孩子想1个由4种颜色组成的序列 4种颜色不一定完全不同 每种颜色只 能是6种颜色之一 方便起见 我们用数字1到6表示6种颜色 计算机必须根据孩子的回答找出孩子所想的颜色序列 计算机在屏幕上显 示一个序列 孩子用键盘回答以下两个问题 猜对的颜色中位置不对的有几个 猜对的颜色中位置对的有几个 基本要求 编程使至多6次问答后猜出序列 如果办不到 至多10次问答后猜出序列 实现说明 测试数据 如孩子想的是4655 计算机猜想 颜色对位置错的数目 颜色和位置都对的数目 1234 1 0 5156 2 1 6165 1 1 5625 1 2 5653 1 2 4655 0 4 7 12 大整数计算器大整数计算器 问题描述 设计一个计算器实现两个任意长得整数的加 减 乘 除 基本要求 设计一个实现任意长的整数进行四则运算的演示程序 要求输入任意长的 整数进行四则运算 都能得到精确的结果 实现说明 7 13 查找搜索技术查找搜索技术 问题描述 给定任意的数组 对于给定的数 查找是否在数组中 如果在 则返回给 定数在数组的位置 不在则返回不在信息 基本要求 1 使用多种搜索方法 越多越好 其中二分搜索技术 线性时间选择是 必须的 2 比较每种排序方法的时间复杂度和空间复杂度 实现说明 7 14 Tom Jerry 和奶酪 和奶酪 问题描述 猫Tom和鼠Jerry同住在一矩阵地窖中 猫要吃鼠 鼠要吃奶酪 地窖中有2 种地砖 有洞砖与无洞砖 一个洞足以让鼠钻入 但猫不能 以菜单形式完成以下任务 随机地生成一个地窖 并给猫 鼠和奶酪安排一个位置 如 fffffffffffffff fppppppppppppCf fhfffffffffffpf fpppjhppppppppf fpffffffpffffff fppppppppppTppf fffffffffffffff 其中c表示猫 j表示鼠 h表示洞 f表示不能通行 2 鼠先行 猫后行 两者皆满足以下规定 1 必须上 下 左或右移动 2 鼠必须走1步 穿过p或h 3 猫必须走1或2步 穿过p 3 当鼠吃到奶酪或猫抓到鼠时 游戏结束 基本要求 实现说明 7 15 布线问题布线问题 问题描述 印刷电路板将布线区域划分成n m个方格阵列 精确的电路布线问题要求 确定连接方格a的中点到方格b的中点的最短布线方案 在布线时 电路只能沿 着直线或直角布线 为了避免线路相交 已布了线的方格做了封锁标记 其他 线路不允许穿过被封锁的方格 基本要求 1 解决题目的问题 2 提供友好的界面 实现说明 使用分支限界法 7 16 魔方工具包魔方工具包 问题描述 一个魔方是一个由3 3 3个小立方体组成的立方体 最初立方体的6个面 分别涂上不同颜色 我们称之为 最初魔方 魔方的每一面上的3 3个小立 方体组成它的一层 魔方所能见到的每一层 6个面 都能旋转90 180 270或360度 所有层 的旋转轴都垂直于面且通过其中心 旋转的结果是另一个魔方 它的所有面的 颜色都改变了 现在我们用字符来代替颜色 U 上 D 下 F 前 B 后 L 左 R 右 任 何一个序列的旋转都能表示成 U R F B L D 中一些字符组成的字符串 其中每 个字符表示它所指定的面顺时针旋转90度 基本要求 1 编程完成以下3个任务 菜单形式 你可以假设任何输入的字串长 度都 35 你的算法能处理非法输入的情况 如 输入 输出 L L LL LL LLL LLL LLLL 空串 LLLLL L LLRRRFFFFRLB LLLB HELLO error 2 判断输入的2个字串的旋转结果是否相同 如 输入一 输入二 输出 RU UR no RRFFRRFFRRFFRRFF FFRRFFRR yes RRFFRRFFRRFFRRFF RRFFRRFF no 3 求出输入字符串至少须使用几次才能将魔方转回到 最初魔方 一 定大于0 输入 输出 L 4 DD 2 BULB 36 RUF 80 BLUFF 180 实现说明 7 17 图的建立与输出图的建立与输出 问题描述 建立图的存储结构 图的类型可以是有向图 无向图 有向网 无向网 学生可以任选两种类型 能够输入图的顶点和边的信息 并存储到相应存储 结构中 而后输出图的邻接矩阵 基本要求 给出图的深度优先和广度优先遍历算法 并给出遍历过程的动态演示效果 实现说明 无 7 18 图的建立与输出图的建立与输出 问题描述 建立图的存储结构 图的类型可以是有向图 无向图 有向网 无向网 学生可以任选两种类型 能够输入图的顶点和边的信息 并存储到相应存储 结构中 而后输出图的邻接矩阵 基本要求 给出图的深度优先和广度优先遍历算法 并给出遍历过程的动态演示效果 实现说明 无 7 19 以队列实现的仿真技术预测理发馆的经营状况 以队列实现的仿真技术预测理发馆的经营状况 问题描述 理发馆一天的工作过程如下 1 理发馆有 N 把理发椅 可同时为 N 位顾客进行理发 2 理发师分三个等级 一级 二级 三级 对应不同的服务收费 3 当顾客进门时 需选择某级别理发师 只要该级别的理发师有空椅 则可立即坐下理发 否则需排队等候 4 一旦该级别的理发师有顾客理发完离去 排在队头的顾客便可开始 理发 5 若理发馆每天连续营业 T 分钟 求 1 一天内顾客在理发馆内的平均逗留时间 2 顾客排队等候理发的队列长度平均值 3 营业时间到点后仍需完成服务的收尾工作时间 4 统计每天的营业额 5 统计每天不同级别理发师的创收 基本要求 1 模拟理发馆一天的工作过程 必须采用事件驱动的离散模型 参考教科 书 3 5 节离散事件模拟 p65 2 每个顾客到达和下一顾客到达时间的间隔应是随机的 3 理发师编号 理发师级别和每天的营业时间由用户输入 4 某顾客挑选某一个级别的理发师而不得时 选第一个队列排队等待 5 每个顾客进门时将生成三个随机数 1 durtime 进门顾客理发所需服务时间 简称 理发 时间 2 intertime 下一顾客将到达的时间间隔 简称 间 隔时间 3 select 服务选项 6 服务收费 应包含服务时间和理发师级别两个因素 7 除了输出统计的数据外 还需