Download presentation
Presentation is loading. Please wait.
1
第七、八次实验要求
2
第七次实验：动态规划算法 1、最长公共子序列 实验内容：利用动态规划算法求出两个给定序列的最长公共子序列。 实验检查：
程序检查：从助教给定的文件test.txt读取两个序列，输出最长公共子序列，并打印出解 矩阵；并结合源代码给助教讲解主要实现部分。 实验报告：对核心代码进行分析，并自己随机生成若干测试数据，在报告中分析该算法 的时间复杂度。
3
第七次实验：动态规划算法 2、矩阵链乘积 实验内容：给定n个矩阵，利用动态规划算法和备忘录法求出n个矩阵链乘的 一种最优括号方案。
实验检查： 程序检查：从助教给定的test.txt文件中读取n个矩阵的维度，第i行的两个数表示Ai的维 度，输出最优括号方案。 实验报告：对核心代码进行分析，并自己随机生成若干测试数据，在报告中分析比较 动态规划算法和备忘录法的时间复杂度。
4
第七次实验：动态规划算法 3、最大子段和 实验内容：给定整数序列，用动态规划算法求出最大子段和，并打印出最大 子段对应的区间。 实验检查：
程序检查：从助教给定的test.txt文件中读取一个整数序列，输出最大子段和最大子段对 应的区间。 实验报告：对核心代码进行分析，并自己随机生成若干测试数据，在报告中分析该算 法的时间复杂度。 评分标准：实验检查（2+3+2）=7分，实验报告3分
5
第八次实验：贪心算法 1、单源最短路径（Dijkstra算法）
实验检查： 程序检查：从助教给定的test.txt文件中读取一个源节点和邻接矩阵，输出源节点到其他 节点的最短路径长度。 实验报告：对核心代码进行分析，并自己随机生成若干测试数据，在报告中分析该算 法的时间复杂度。
6
第八次实验：贪心算法 2、最小生成树（Prim算法和Kruskal算法）
实验内容：给定无向连通带权图G，分别用Prim算法和Kruskal算法求出G的最 小生成树。 实验检查： 程序检查：从助教给定的test.txt文件中读取图G的邻接矩阵，输出G的最小生成树和树 上所有边的权值之和。 实验报告：对核心代码进行分析，并自己随机生成若干测试数据，分析比较Prim算法和 Kruskal算法的时间复杂度。 评分标准：实验检查（3+4）=7分，实验报告3分
7
输入文件格式
Similar presentations
