《算法设计与分析》- 课内上机实验题目及其解答
发布时间:2021-06-11
发布时间:2021-06-11
算法设计与分析
上机题目解答
西安邮电大学计算机学院
算法设计与分析
上机存在的问题(1)上机准备工作不足;
(2)程序设计风格不够好;(3)测试用例设计不够全面;
(4)上机报告撰写不够认真;(5)上机报告排版不够规范。
西安邮电大学计算机学院
算法设计与分析
递归与分治策略
西安邮电大学计算机学院
递归与分治策略 基本题 1:用分治法查找数组元素的最大值和 最小值。
西安邮电大学计算机学院
递归与分治策略【问题分析】(1)数组的生成:许多同学采用固定数组的做法,实际上采用随机数组 是一个比较好的做法,一是可以生成随机数字,便于测试代码;二是相对
于固定长度数组可以很方便地生成任意长度的数组。如下:
西安邮电大学计算机学院
递归与分治策略(2)算法分析:给同学们的资料上面的算法如下所示:
算法中“假定 n 是 2 的指数倍”,实际算法中可以不局限于此。许多同学都正确地 实现了任意长度数组的最值计算分治算法。算法的伪代码如下(并非唯一算法):
西安邮电大学计算机学院
递归与分治策略
西安邮电大学计算机学院
递归与分治策略(3)小结:
大部分同学均能够正确编写程序,但存在一些问题,需要继续努力。
西安邮电大学计算机学院
递归与分治策略 基本题 2:众数问题(课本 P39 算法实现题 2 的 2-1 题)。
西安邮电大学计算机学院
递归与分治策略
西安邮电大学计算机学院
递归与分治策略
西安邮电大学计算机学院
递归与分治策略【问题分析】(1)算法:可以用很直观的思路来求解“众数”问题,即通过扫描输入 文件中的各个数据,如果是新数据则建立“记录”;否则针对老数据累加
其出现频度。最后统计出现频度最高的“数据”即为“众数”,该频度的值为“重数”。由于上述算法中涉及到“查找”,因此一种做法是先将读 入的全部数据排序,之后按照上述思路逐个分析、处理。大部分同学都能 正确求解此问题,采用的排序算法有“快速排序”和“合并排序”(均体 现了“分治法”思想);数据结构有结构体或者二维数组,用来保存出现 的数据及其频度。这些都是正确的做法。
西安邮电大学计算机学院
递归与分治策略(2)小结:
和“数组求最值”问题相同。
西安邮电大学计算机学院
算法设计与分析
动态规划
西安邮电大学计算机学院
动态规划 基本题 1:编辑距离问题(第 4 版教材P79 3-2 题)。
西安邮电大学计算机学院
动态规划
西安邮电大学计算机学院
动态规划【问题分析】(1)算法原理分析
西安邮电大
学计算机学院
动态规划
西安邮电大学计算机学院
动态规划
西安邮电大学计算机学院
动态规划
西安邮电大学计算机学院
动态规划
西安邮电大学计算机学院
上一篇:《斯坦福监狱实验》观后感