西电算法导论上机实验报告材料

《西电算法导论上机实验报告材料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档算法导论上机实验报告册班级：xxxxxx学号：xxxxxxx姓名：xxxx教师：xxxxxx文案大全实用文档目录实验一排序算法1题目一：11、题目描述：12、所用算法：13、算法分析：14、结果截图：15、总结：2题目二：31、题目描述：32、所用算法：33、算法分析：34、结果截图：35、总结：4题目三：41、题目描述：42、所用算法：43、算法分析：54、结果截图：55、总结：5题目四：61、题目描述：62、所用策略：63、算法分析：64、结果截图：65、总结：7实验二动态规划7题目一：71、题目描述：72、所用策略：73、算法分析：74、结果截图：85、总结：8题目二：91

2、、题目描述：92、所用策略：93、算法分析：94、结果截图：95、总结：10题目三：101、题目描述：102、所用策略：103、算法分析：10文案大全实用文档4、结果截图：115、总结：11题目四：111、题目描述：122、所用策略：123、算法分析:124、结果截图：125、总结：13题目五：131、题目描述：132、所用策略：133、算法分析：134、结果截图：145、总结：14实验三贪心算法14题目一：141、题目描述：142、所用策略：143、算法分析：144、结果截图：155、总结：16题目二：161、题目描述：162、所用策略：163、算法分析：164、结果截图：175、总结

3、：17题目三：171、题目描述:172、所用算法：173、算法分析：174、结果截图：185、总结：18题目四：181、题目描述：192、所用算法：193、算法分析：19实验四回溯法19题目一：191、题目描述：192、所用策略：193、算法分析：19题目二：201、题目描述：21文案大全实用文档2、所用策略：213、算法分析：21文案大全实用文档实验一排序算法题目一：1、题目描述：描述一个运行时间为θ(nlgn)的算法，给定n个整数的集合S和另一个整数x，该算法能确定S中是否存在两个其和刚好为x的元素。2、所用算法：1、运用归并排序算法2、在已经排好序的基础上，对其运用二分查找。3、算

4、法分析：（1）归并排序运用的是分治思想，时间复杂度为θ(nlgn)，能够满足题目要求的运行时间。归并排序的分解部分是每次将数组划分两个部分，时间复杂度为θ（1）；再对已经分解的两个部分再进行分解直到将数组分解成单个元素为止；解决部分是递归求解排序子序列；合并部分是将已经排序的子序列进行合并得到所要的答案，时间复杂度为θ(lgn)。（2）二分查找算法的时间复杂度为θ(lgn)在题目要求的范围内，二分查找的条件为待查的数组为有序序列。算法的主要思想为设定两个数，low指向最低元素，high指向最高元素，然后比较数组中间的元素与待查元素进行比较。如果待查元素小于中间元素，那么表明查找元素在数组

5、的前半段；反之，如果待查元素大于中间元素，那么表明查找元素在数组的后半段。4、结果截图：文案大全实用文档5、总结：（1）在主函数中调用二分查找的时候，参数应该为BinSearch(a,j+1,n,x-a[j]），从j+1开始遍历而不是都是从第一个开始。（2）遇到的困难为：由于程序语言规定数组的下标从0开始，而算法伪代码要求从1开始，因此在定义数组大小的时候将数字加1，但是在编译运行的时候会得不到想要的结果，出现数组下标访问错误。采取的解决方案为：在开始定义数组的时候，将数组的大小定义为一个较大的数字，如1000。避免在运行时出现错误，但是造成了空间的浪费。较好的方案为使用动态数组，如ma

6、lloc函数。题目二：文案大全实用文档1、题目描述：实现优先级队列，即需要支持以下操作：INSERT(S,x):把元素x插入到集合S中；MAXMUM(S):返回S中具有最大key的元素；EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素；INCREASE-KEY(S,x,k)：将元素x的关键字值增到k。2、所用算法：堆排序，运用堆来实现优先队列。3、算法分析：（1）堆排序算法是引用堆这个数据结构进行信息管理。堆排序的时间复杂度是θ(nlgn),但是与归并排序不同的是堆排序具有空间的原址性，任何时候都只需要常数个额外的元素空间存储临时数据。堆排序算法分为3个过程，MAX-H

7、EAPIEY:调整堆以满足小顶堆性质，其时间复杂度为θ(lgn)；BUILD-MAXHEAP:从无序的输入数据数组中构造小顶堆，其时间复杂度为线性时间;HEAP-SORT:对数组进行原址排序，其时间复杂度为θ(nlgn)。（2）在堆的基础上实现优先队列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY，时间复杂度为θ(lgn)。4、结果截图：文案大全实用文档5、总结：遇到的困难：没有理解将一个序列转换成小顶