算法设计与分析

上机题目解答

西安邮电大学计算机学院

算法设计与分析

上机存在的问题(1)上机准备工作不足；

(2)程序设计风格不够好；(3)测试用例设计不够全面；

(4)上机报告撰写不够认真；(5)上机报告排版不够规范。

西安邮电大学计算机学院

算法设计与分析

递归与分治策略

西安邮电大学计算机学院

递归与分治策略 基本题 1:用分治法查找数组元素的最大值和 最小值。

西安邮电大学计算机学院

递归与分治策略【问题分析】(1)数组的生成：许多同学采用固定数组的做法，实际上采用随机数组 是一个比较好的做法，一是可以生成随机数字，便于测试代码；二是相对

于固定长度数组可以很方便地生成任意长度的数组。如下：

西安邮电大学计算机学院

递归与分治策略(2)算法分析：给同学们的资料上面的算法如下所示：

算法中“假定 n 是 2 的指数倍”,实际算法中可以不局限于此。许多同学都正确地 实现了任意长度数组的最值计算分治算法。算法的伪代码如下(并非唯一算法):

西安邮电大学计算机学院

递归与分治策略

西安邮电大学计算机学院

递归与分治策略(3)小结：

大部分同学均能够正确编写程序，但存在一些问题，需要继续努力。

西安邮电大学计算机学院

递归与分治策略 基本题 2:众数问题(课本 P39 算法实现题 2 的 2-1 题)。

西安邮电大学计算机学院

递归与分治策略

西安邮电大学计算机学院

递归与分治策略

西安邮电大学计算机学院

递归与分治策略【问题分析】(1)算法：可以用很直观的思路来求解“众数”问题，即通过扫描输入 文件中的各个数据，如果是新数据则建立“记录”;否则针对老数据累加

其出现频度。最后统计出现频度最高的“数据”即为“众数”,该频度的值为“重数”。由于上述算法中涉及到“查找”,因此一种做法是先将读 入的全部数据排序，之后按照上述思路逐个分析、处理。大部分同学都能 正确求解此问题，采用的排序算法有“快速排序”和“合并排序”(均体 现了“分治法”思想);数据结构有结构体或者二维数组，用来保存出现 的数据及其频度。这些都是正确的做法。

西安邮电大学计算机学院

递归与分治策略(2)小结：

和“数组求最值”问题相同。

西安邮电大学计算机学院

算法设计与分析

动态规划

西安邮电大学计算机学院

动态规划 基本题 1:编辑距离问题(第 4 版教材P79 3-2 题)。

西安邮电大学计算机学院

动态规划

西安邮电大学计算机学院

动态规划【问题分析】(1)算法原理分析

西安邮电大

学计算机学院

动态规划

西安邮电大学计算机学院

动态规划

西安邮电大学计算机学院

动态规划

西安邮电大学计算机学院

动态规划

西安邮电大学计算机学院