logo资料库

算法设计与分析实验报告.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.29M 资料格式：doc 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    实 验 报 告 课程名称：算法设计与分析 班级： 实验成绩： 实验名称：分治策略 实验编号：实验一 指导教师： 学号： 姓名： 组号： 批阅教师签字： 实验日期： 实验时间： 一、实验目的 1. 理解分治法的思想。 2. 掌握用分治法解决问题。 3. 保证准确性与创新性。 二、实验内容 1. 设 X[0:n-1]和 Y[0:n–1]为两个数组，每个数组中含有 n 个已排好序的数。找出 X 和 Y 的 2n 个数的中位数。利用分治策略试设计一个 O (log n)时间的算法求出这 2n个数的 中位数。 2. 利用分治策略设计一个算法对任意的 n 构造相应的 Gray 码。 3. 定义一个 Advertisement 类，该类中至少包含该物品的数量，名称，联系人 e-mail，最 好有开拍时间及关闭时间，根据用户输入的关键字比如名称，mail，时间等，利用非递 归的归并排序对所有的广告进行排序，并列出所有排好序的广告。 三、实验环境 操作系统：Windows 7 & Windows XP 调试软件：Microsoft Visual C++ 6.0 上机地点： 四、问题分析 1. 设两个长度为 n 的数列分别为 X[0:n-1]和 Y[0:n–1]，分别找出这两个数列的中位数 x[i] 和 y[j]，二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围，然后再分 别取两个子数列的中位数再比较，再减少搜索范围，继续下去直到找到最后结果。 2. Gray 码是一个长度为 2n 的序列。序列中没有相同的元素，每个元素都是长度为 n 位的 串，相邻元素恰好只有一位不同。 Gray 码序列规律示意图： 1
    如上图，对于宽度为 4 的 Gray 码，除最高位以外，虚线①的上下两侧是对称的，对称 的两组码字恰好均是宽度为 3 的 Gray 码，并且虚线①上方最高位全为“0”，下方全为“1”； 对于宽度为 3 的 Gray 码，除最高位以外，虚线②的上下两侧也是对称的，对称的两组码字 恰好均是宽度为 2 的 Gray 码，并且虚线②上方最高位同样全为“0”，下方全为“1”。同 理，向下推广至 Gray 码宽度为 2 和 1，向上推广至宽度为 5、6、……。可以发现，这种规 律对于任意宽度的 Gray 码都是适用的。 3. 利用分治策略的归并算法的基本思想是：将待排序元素分成大小大致相同的两个子集 合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。 五、问题解决 1. 中位数问题 1) 基本算法思想 设两个长度为 n 的数列分别为 X[0:n-1]和 Y[0:n–1]，分别找出这两个数列的中位数 x[i] 和 y[j]，二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围，然后再分别 取两个子数列的中位数再比较，再减少搜索范围，继续下去直到找到最后结果。 2) 求解过程 查找范围确定：由于 n 是奇数还是偶数会影响查找范围，所以要先判断一下（如果 n 是偶数， 则中位数选较小者） 当 n 为 奇 数 时 ， 令 n=2m +1 ， 则 两 个 数 列 的 中 位 数 分 别 为 x[ m ] 和 y[ m ] ， 则 ： x[0:m-1]
    当 n 为 偶 数 时， 令 n=2m ， 则 两 个数 列 的 中 位 数分 别 为 x[ m-1 ]和 y[ m-1 ]， 则 ： x[0:m-2]
    1) 基本算法思想 归并排序的原理是不断地将两个有序的序列合并为一个有序列，设有 n 个元素，那么第 一步是长度为 1 的序列进行合并，第二步是长度为 2 的序列进行合并，第 3 步是长度为 4 的序列进行合并，以此类推。 2) 复杂度分析 对于所给的 n 元素数组已排好序的极端情况，此算法不需要执行合并步骤，而算法 MergeSort 需要执行（log n）次合并，因此这种情况下，算法需要 O(n)时间，而算法 MergeSort 需要 O(nlogn)时间。 3) 注意的问题 注意物品广告类的构造函数的参数，时间没有加入到参数列表中，是自动将系统当前时 间作为起拍时间，并规定持续时间为一个月，即结束时间也固定。 六、实验结果总结 1. 中位数问题 1) 测试结果： input.txt 中的内容： 控制台： output.txt 中的内容： 2) 算法实现的复杂度在问题规模很大时可以接受。 3) 如果不用分治方法，可以先把两个排好序的数组合并成一个数组，然后再找中位数，这 样的算法时间复杂度为 O(n)，不会比分治算法有更好的效率。 4) 选用简单的一维数组，利用下标便于操作，比较合适。 2. Gray 码问题 4
    1) 测试结果： input.txt 中的内容： 控制台： output.txt 中的内容： 2) 算法实现的复杂度在问题规模很大时，不太满足要求，因为需要特别大的二维数组，数 量级为 2n ，造成很大的空间浪费。 3) 除了分治法解 Gray 码问题，没有想到其他的方法。 4) 所选数据结构不太合适，有可能造成极大的空间浪费。 3. 归并排序 1) 测试结果： input.txt 中的内容： 5
    控制台： output.txt 中的内容： 6
    2) 算法实现的复杂度在问题规模很大时可以接受。 3) 如果不用分治算法，可以用其他的排序算法，但是有可能效率比较低。 4) 选用的数据结构比较合适。 5) 因为时间问题，物品的起拍时间和关闭时间在构造时固定为当前系统时间，但是可以写 设置时间的函数，这次没有实现，但是要求的显示时间还是有的。 七、附录 宋传鸣 计算机工程与设计 Vol.25 No.7，2004.7 王晓东 计算机算法设计与分析【C】 北京：电子工业出版社 2001 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料