算法分析与设计课程实验报告 班 级： 131213 学 号： 13121XXX 姓 名： XXX 指导老师： 邓 凡 目录 算法分析与设计课程实验报告 ............................... 1 实验一 排序 .............................................. 1 1. 课本练习 2.3-7...................................... 1 2. 实现优先队列 ....................................... 2 3.快速排序 ............................................ 2 4. 第 k大元素 ......................................... 3 实验二 动态规划 .......................................... 4 1. 矩阵链乘 ........................................... 4 2. 最长公共子序列 ..................................... 5 3. 最长公共子串 ....................................... 7 4. 最大和 ............................................. 9 5. 最短路径 .......................................... 10 实验三 贪心策略 ......................................... 11 1. 背包问题 .......................................... 11 2. 任务调度 .......................................... 14 3. 单源点最短路径 .................................... 15 4. 任意两点间最短路径 ................................ 16 实验四 回溯法 ........................................... 18 1. 0-1背包问题 ...................................... 18 2. 8-Queen问题 ...................................... 21 1 实验一 排序 1.课本练习2 .3 -7 (1)问题描述 描述一个运行时间为 (nlgn)的算法，给定n 个整数的集合S 和另一个整数x,该算法能确定S 中是否存在两个其和刚好是x 的元素。 (2)问题分析 该问题首先要进行排序，然后用二分查找法判断 S 中是否存在两个其和刚好是x 的元素，因为时间复杂度为(nlgn)，所以可以采用归并排序。 (3)算法分析 归并排序的思想是将 n个元素分成各含 n/2个元素的子序列，然后对两个子序列递归地进行排序，最后合并两个已排序的子序列得到排序结果。二分查找的思想是对于集合中的每一个数字，用二分法找到x-S[i]的位置，若存在且不为其本身，则输出 S中存在有两个和等于x的元素；否则，不存在。 (4)实验结果 2 2.实现优先队列 (1)问题描...
