算法设计与分析实验指导书详解

算法设计与分析算法设计与分析 实实 验验 指指 导导 书书 东北大学软件学院东北大学软件学院 20122012 年年 目 录 算法设计与分析 1 实 验 指 导 书 1 前 言 3 实验要求 4 实验 1 分治法的应用 2 学时 5 1 实验目的 5 2 实验类型 5 3 预习要求 5 4 实验基本要求 5 5 实验基本步骤 7 实验 2 动态规划 2 学时 9 1 实验目的 9 2 实验类型 9 3 预习要求 9 4 实验基本要求 9 5 实验基本步骤 10 实验 3 回溯法 4 学时 12 1 实验目的 12 2 实验类型 12 3 预习要求 12 4 实验基本要求 12 5 实验基本步骤 13 东北大学软件学院信息安全专业 算法设计与分析实验 第 3 页 共 17 页 前前 言言 算法设计与分析 是一门面向设计 处于计算机科学与技术学科核心地位的教育课程 通过对计 算机算法系统的学习 使学生理解和掌握计算机算法的通用设计方法 培养对算法的计算复杂性正确分析 的能力 为独立设计算法和对算法进行复杂性分析奠定基础 要求掌握算法复杂度分析 分治法 动态规划法 贪心法 回溯法 分支限界法等算法的设计方法及 其分析方法 能将这些方法灵活的应用到相应的问题中 并且能够用 C 实现所涉及的算法 并尽量做到 低复杂度 高效率 通过本课程的实验 使学生加深对课程内容的理解 培养学生严密的思维能力 运用所学知识结合具 体问题设计适用的算法的能力 培养学生良好的设计风格 激励学生创造新算法和改进旧算法的愿望和热 情 希望同学们能够充分利用实验条件 认真完成实验 从实验中得到应有的锻炼和培养 希望同学们在使用本实验指导书及进行实验的过程中 能够帮助我们不断地发现问题 并提出建 议 使 算法设计与分析 课程成为对大家有益的课程 东北大学软件学院信息安全专业 算法设计与分析实验 第 4 页 共 17 页 实验要求实验要求 算法设计与分析 课程实验的目的是为了使学生在课堂学习的同时 通过一系列的实验 使学生 加深理解和更好地掌握 算法设计与分析 课程教学大纲要求的内容 在 算法设计与分析 的课程实验过程中 要求学生做到 1 仔细观察调试程序过程中出现的各种问题 记录主要问题 做出必要说明和分析 2 认真书写实验报告 实验报告模板见附录1 3 遵守机房纪律 服从辅导教师指挥 爱护实验设备 4 实验课程不迟到 如有事不能出席 所缺实验一般不补 5 本实验采用的开发环境为 Microsoft Visual C 6 0 同学在做实验之前要求熟悉该软件 的使用方法 6 实验成绩主要从以下几方面考核 实验过程态度 实验结果及报告书写 东北大学软件学院信息安全专业 算法设计与分析实验 第 5 页 共 17 页 实验实验 1 分治法的应用 分治法的应用 2 学时 学时 1 实验目的实验目的 1 理解分治法的思想 2 掌握用分治法解决问题 2 实验类型实验类型 设计型 3 预习要求预习要求 熟悉 Visual C 6 0 上机编程调试的基本方法 掌握教材上分治法的思想 掌握各种排序方法及二 分搜索的思想 4 实验基本要求实验基本要求 1 仔细阅读备选实验的题目 选择一个 可选多个 作为此次实验题目 设计的程序要满足正确性 代码中有关键的注释 书写格式清晰 简洁易懂 效率较高 利用 C 的模板 设计的程序通 用性好 适合各种合理输入 并能对不合理输入做出正确的提示 2 可供选择的题目有以下 3 个 i i 中位数问题中位数问题 问题描述问题描述 设 X 0 n 1 和 Y 0 n 1 为两个数组 每个数组中含有 n 个已排好序的数 找出 X 和 Y 的 2n 个数的中位数 编程任务编程任务 利用分治策略试设计一个 O log n 时间的算法求出这 2n 个数的中位数 数据输入数据输入 由文件 input txt 提供输入数据 文件的第 1 行中有 1 个正整数 n n 200 表示每个数组 有 n 个数 接下来的两行分别是 X Y 数组的元素 结果输出结果输出 程序运行结束时 将计算出的中位数输出到文件 output txt 中 输入文件示例输入文件示例输出文件示例输出文件示例 input txtoutput txt 3 5 15 18 3 14 21 14 实现提示实现提示 东北大学软件学院信息安全专业 算法设计与分析实验 第 6 页 共 17 页 比较两个序列的中位数大小 如果两个数相等 则该数为整个 2n 个数据的中位数 否则通过 比较 分别减少两个序列的查找范围 确定查找的起止位置 继续查找 iiii Gray 码问题码问题 问题描述问题描述 Gray 码是一个长度为 2n的序列 序列中无相同的元素 每个元素都是长度为 n 位的串 相邻元 素恰好只有一位不同 用分治策略设计一个算法对任意的 n 构造相应的 Gray 码 编程任务编程任务 利用分治策略试设计一个算法对任意的 n 构造相应的 Gray 码 数据输入数据输入 由文件 input txt 提供输入数据 n 结果输出结果输出 程序运行结束时 将得到的所有编码输出到文件 output txt 中 输入文件示例输入文件示例输出文件示例输出文件示例 input txtoutput txt 3000 100 101 010 011 111 101 001 实现提示实现提示 把原问题分解为两个子问题 分别对两个子问题的每个数组后一位加 0 和 1 iii 归并排序 归并排序 问题描述问题描述 目前的网上拍卖系统会显示很多待拍卖的物品 通常这些系统具有按照某个关键字对打出的 广告进行排序列出的功能 并且能够按照用户输入的某个关键字进行过虑 找到某些特定的物品 编程任务编程任务 定义一个 Advertisement 类 该类中至少包含该物品的数量 名称 联系人 e mail 最好有 开拍时间及关闭时间 根据用户输入的关键字比如名称 mail 时间等 利用非递归的归并排序 对所有的广告进行排序 并列出所有排好序的广告 数据输入数据输入 由文件 input txt 提供输入的所有广告信息 程序中由用户输入要排序的关键字 结果输出结果输出 程序运行结束时 排好序的广告输出到文件 output txt 中 并为每个广告添加序号 输入文件示例输入文件示例输出文件示例输出文件示例 input txtoutput txt Coat 物品名称 3 数量 1 Bag 东北大学软件学院信息安全专业 算法设计与分析实验 第 7 页 共 17 页 a Skirt 5 b Cap 7 c Bag 12 a Title 用户输入按照title 排序 12 a 2 Cap 7 c 3 Coat 物品名称 3 数量 a 4 Skirt 5 b 3 按照指定的格式书写实验报告 实验报告清晰 但不赘述 字体最大为四号 在实验结束一周内 上交实验报告 5 实验基本步骤实验基本步骤 1 选定实验题目 仔细阅读实验要求 设计好输入输出 按照分治法的思想构思算法 选取合适的 存储结构实现应用的操作 2 设计的结果应在 Visual C 实验环境下实现并进行调试 3 实验要有详细详细的测试记录 包括各种可能的测试数据 东北大学软件学院信息安全专业 算法设计与分析实验 第 8 页 共 17 页 实实 验验 报报 告告 一 实验目的一 实验目的 理解分治法的思想 掌握用分治法解决问题 二 实验内容二 实验内容 i i 中位数问题中位数问题 问题描述问题描述 设 X 0 n 1 和 Y 0 n 1 为两个数组 每个数组中含有 n 个已排好序的数 找出 X 和 Y 的 2n 个数的中位数 编程任务编程任务 利用分治策略试设计一个 O log n 时间的算法求出这 2n 个数的中位数 数据输入数据输入 由文件 input txt 提供输入数据 文件的第 1 行中有 1 个正整数 n n 200 表示每个数组 有 n 个数 接下来的两行分别是 X Y 数组的元素 三 实验环境三 实验环境 WINDOWS7家庭版 DEVC 四 问题分析四 问题分析 1 分析要解决的问题 给出你的思路 可以借助图表等辅助表达 设两个长度为 n 的数列分别为 x 0 n 1 和 y 0 n 1 分别找出这两个数列的中位数 x i 和 y j 二者进行比较 根据比较结果可以在每个数列中减少一半的搜索范围 然后再 分别取两个子数列的中位数再比较 再减少搜索范围 继续下去直到找到最后结果 2 分析利用你的想法解决该问题可能会有怎样的时空复杂度 O n 3 其它 你认为需要在此说明的 五 问题解决五 问题解决 1 根据对问题的分析 写出解决办法 设两个长度为 n 的数列分别为 x 0 n 1 和 y 0 n 1 分别找出这两个数列的中位数 x i 和 y j 二者进行比较 根据比较结果可以在每个数列中减少一半的搜索范围 然后再 分别取两个子数列的中位数再比较 再减少搜索范围 继续下去直到找到最后结果 2 描述你在进行实现时 主要的函数或操作内部的主要算法 分析这个算法的时 空复杂度 并说明你设计的巧妙之处 如有创新 将其清晰的表述 int findMedian int x int y int n if n 1 课程名称课程名称 算法设计与分析班级班级 软件 1304 实验成绩实验成绩 实验名称实验名称 分治策略学号学号 批阅教师签字 批阅教师签字 实验编号实验编号 实验一姓名姓名 赵航实验日期 实验日期 2016 年 1 月 1 日 指导教师指导教师 张莉组号组号 实验时间实验时间 时 分 时 分 东北大学软件学院信息安全专业 算法设计与分析实验 第 9 页 共 17 页 return x y x y int m n 1 2 int p m 1 if n 2 0 p if x m y m return x m else if x m y m return findMedian x p y m 1 else return findMedian x y p m 1 O n 算法的巧妙之处在于分别找出这两个数列的中位数 x i 和 y j 二者进行比较 根据比较 结果可以在每个数列中减少一半的搜索范围 然后再分别取两个子数列的中位数再比较 再减 少搜索范围 继续下去直到找到最后结果 3 针对你所选的问题 你认为应该特别注意哪些方面的处理 比如循环何时结束等 分别找出这两个数列的中位数 x i 和 y j 二者进行比较 直到最后的结果 4 你在调试过程中发现了怎样的问题 又做了怎样的改进 在调试中发现了编译不通过 经检查是语法问题 5 其它 你认为需要在此说明的 六 实验结果总结六 实验结果总结 回答以下问题 1 对不同的输入 该算法都存在哪几类可能出现的情况 你的测试数据完全覆盖了你所想到的 这些情况 测试结果如何 1 普通 2 数组中只有一个数 结果如下 2 算法实现的复杂度在问题规模很大时可以接受吗 东北大学软件学院信息安全专业 算法设计与分析实验 第 10 页 共 17 页 可以 3 如果不用分治方法还能想到其他的解决方式吗 和分治相比会有更好的效率吗 有 将二者放到同一数组然后排序取中值 效率更低 4 所选用的数据结构合适吗 选用数组 合适 5 叙述通过实验你对分治方法的理解及你认为的分治法的优缺点 分治法的优点是将大问题拆成小问题来进行解决 可以节约时间 6 其它 你认为需要在此说明的 六 附录六 附录 1 如果你对这个实验还有其他的解决方案或设想 或对我们的实验方案有什么意见 请在此描 述 2 实验参考的资料和网址 注 本实验的考核点主要在问题的分析是否正确 对问题的考虑是否全面 解决方法及程序是否正确 程序代码是否清晰 是否符合编码规范 是否有注释 测试数据是否完整 是否有创新 实验实验 2 动态规划 动态规划 2 学时 学时 1 实验目的实验目的 1 熟练掌握动态规划思想及教材中相关经典算法 2 掌握用动态规划解题的基本步骤 能够用动态规划解决一些问题 2 实验类型实验类型 设计型 3 预习要求预习要求 掌握动态规划思想 复习学过的有关动态规划的算法 并设计实验题目的程序 4 实验基本要求实验基本要求 1 仔细阅读备选实验的题目 选择一个 可选多个 作为此次实验题目 设计的程序要满足正确性 代码中有关键的注释 书写格式清晰 简洁易懂 效率较高 利用 C 的模板 设计的程序通 用性好 适合各种合理输入 并能对不合理输入做出正确的提示 2 可供选择的题目有以下 2 个 i i 找零钱问题 难度系数为 找零钱问题 难度系数为 3 3 问题描述问题描述 设有 n 种不同面值的硬币 各硬币的面值存于数组 T 1 n 中 现要用这些面值的硬币来找钱 可以实用的各种面值的硬币个数不限 当只用硬币面值 T 1 T 2 T i 时 可找出钱数 j 的 最少硬币个数记为 C i j 若只用这些硬币面值 找不出钱数 j 时 记 C i j 编程任务编程任务 设计一个动态规划算法 对 1 j L 计算出所有的 C n j 算法中只允许实用一个长度 为 L 的数组 用 L 和 n 作为变量来表示算法的计算时间复杂性 数据输入数据输入 由文件 input txt 提供输入数据 文件的第 1 行中有 1 个正整数 n n 13 表示有 n 种硬 币可选 接下来的一行是每种硬币的面值 由用户输入待找钱数 j 结果输出结果输出 程序运行结束时 将计算出的所需最少硬币个数输出到文件 output txt 中 输入文件示例输入文件示例输出文件示例输出文件示例 input txtoutput txt 3 1 2 5 3 东北大学软件学院信息安全专业 算法设计与分析实验 12 9 实现提示实现提示 首先要建立递归关系 并将分析过程写在报告中 ii 租用游艇问题 难度系数为租用游艇问题 难度系数为 4 问题描述问题描述 长江游艇俱乐部在长江上设置了 n 个游艇出租站 1 2 n 游客可在这些游艇出租站租 用游艇 并在下游的任何一个游艇出租站归还游艇 游艇出租站 i 到游艇出租站 j 之间的租金 为 r i j 1 i j n 试设计一个算法 计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金 编程任务编程任务 对于给定的游艇出租站 i 到游艇出租站 j 之间的租金为 r i j 1 i j n 编程计算从游艇 出租站 1 到游艇出租站 n 所需的最少租金 数据输入数据输入 由文件 input txt 提供输入数据 文件的第 1 行中有 1 个正整数 n n 200 表示有 n 个游 艇出租站 接下来的 n 1 行是 r i j 1 i j n 结果输出结果输出 程序运行结束时 将计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金输出到文件 output txt 中 输入文件示例输入文件示例输出文件示例输出文件示例 input txtoutput txt 3 5 15 7 12 实现提示实现提示 建立递归关系 然后按照递归关系写出算法 3 按照指定的格式书写实验报告 实验报告清晰 但不赘述 字体最大为四号 在实验结束一周内 上交实验报告 5 实验基本步骤实验基本步骤 4 选定实验题目 仔细阅读实验要求 设计好输入输出 按照分治法的思想构思算法 选取合适的 存储结构实现应用的操作 5 设计的结果应在 Visual C 实验环境下实现并进行调试 6 实验要有详细的测试记录 包括各种可能的测试数据 东北大学软件学院信息安全专业 算法设计与分析实验 13 实实 验验 报报 告告 一 实验目的一 实验目的 熟练掌握动态规划思想及教材中相关经典算法 掌握用动态规划解题的基本步骤 能够用动态规划解决一些问题 二 实验内容与实验步骤二 实验内容与实验步骤 找零钱问题 难度系数为找零钱问题 难度系数为 3 3 问题描述问题描述 设有 n 种不同面值的硬币 各硬币的面值存于数组 T 1 n 中 现要用这些面值的硬币来找钱 可以实用的各种面值的硬币个数不限 当只用硬币面值 T 1 T 2 T i 时 可找出钱数 j 的 最少硬币个数记为 C i j 若只用这些硬币面值 找不出钱数 j 时 记 C i j 编程任务编程任务 设计一个动态规划算法 对 1 j L 计算出所有的 C n j 算法中只允许实用一个长度 为 L 的数组 用 L 和 n 作为变量来表示算法的计算时间复杂性 数据输入数据输入 由文件 input txt 提供输入数据 文件的第 1 行中有 1 个正整数 n n 13 表示有 n 种硬 币可选 接下来的一行是每种硬币的面值 由用户输入待找钱数 j 结果输出结果输出 程序运行结束时 将计算出的所需最少硬币个数输出到文件 output txt 中 输入文件示例输入文件示例输出文件示例输出文件示例 input txtoutput txt 3 1 2 5 9 3 实现提示实现提示 首先要建立递归关系 并将分析过程写在报告中 三 实验环境三 实验环境 操作系统 调试软件名称 版本号 上机地点 机器台号 四 问题分析四 问题分析 1 分析要解决的问题 给出你的思路 可以借助图表等辅助表达 问题为找零钱 则应该采用递归的算法解决问题 一个一个硬币往上加 2 根据分析建立正确的递归关系 c i j 表示从第 1 个到第 i 个硬币可选 要找的钱数是 j 则出口是 课程名称课程名称 算法设计与分析班级班级 软件软件 1304实验成绩实验成绩 实验名称实验名称 动态规划学号学号 批阅教师签字 批阅教师签字 实验编号实验编号 实验二姓名姓名 赵航实验日期 实验日期 2016 年 1 月 5 日 指导教师指导教师 张莉组号组号 实验时间实验时间 时 分 时 分 东北大学软件学院信息安全专业 算法设计与分析实验 14 0 1 1 min 1 0 1 0 1 1 1 iTj iTj iTjicjic jic jic Tj TjTj jc 0 1 1 min 1 0 1 0 1 1 1 iTj iTj iTjicjic jic jic T