西安邮电大学《算法设计与分析》课内上机实验题目及其解答

1、西安邮电大学计算机学院西安邮电大学计算机学院算法设计与分析算法设计与分析上机题目解答上机题目解答西安邮电大学计算机学院西安邮电大学计算机学院算法设计与分析算法设计与分析上机存在的问题上机存在的问题（1）上机准备工作不足；）上机准备工作不足；（2）程序设计风格不够好；）程序设计风格不够好；（3）测试用例设计不够全面；）测试用例设计不够全面；（4）上机报告撰写不够认真；）上机报告撰写不够认真；（5）上机报告排版不够规范。）上机报告排版不够规范。西安邮电大学计算机学院西安邮电大学计算机学院算法设计与分析算法设计与分析递归与分治策略递归与分治策略西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策

2、略递归与分治策略基本题基本题 1：用分治法查找数组元素的最大值和用分治法查找数组元素的最大值和最小值。最小值。西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略【问题分析问题分析】（1）数组的生成）数组的生成：许多同学采用固定数组固定数组的做法，实际上采用随机数组随机数组是一个比较好的做法，一是可以生成随机数字，便于测试代码；二是相对于固定长度数组可以很方便地生成任意长度的数组。如下：西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略（2）算法分析）算法分析：给同学们的资料上面的算法如下所示：算法中“假定 n 是 2 的指数倍”，实际算法中可以不局限

3、于此。许多同学都正确地实现了任意长度数组的最值计算分治算法。算法的伪代码如下（并非唯一算法）算法的伪代码如下（并非唯一算法）：西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略（3）小结）小结：大部分同学均能够正确编写程序，但存在一些问题，需要继续努力。西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略基本题基本题 2：众数问题（众数问题（课本课本 P39 算法实现题算法实现题 2的的 2-1 题题）。）。西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略西

4、安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略【问题分析问题分析】（1）算法）算法：可以用很直观的思路来求解“众数”问题，即通过扫描输入文件中的各个数据，如果是新数据则建立“记录”；否则针对老数据累加其出现频度。最后统计出现频度最高的“数据”即为“众数众数”，该频度的值为“重数重数”。由于上述算法中涉及到“查找”，因此一种做法是先将读入的全部数据排序，之后按照上述思路逐个分析、处理。大部分同学都能正确求解此问题，采用的排序算法有“快速排序快速排序”和“合并排序合并排序”（均体均体现了现了“分治法分治

5、法”思想思想）；数据结构有结构体结构体或者二维数组二维数组，用来保存出现的数据及其频度。这些都是正确的做法。西安邮电大学计算机学院西安邮电大学计算机学院递归与分治策略递归与分治策略（2）小结）小结：和“数组求最值”问题相同。西安邮电大学计算机学院西安邮电大学计算机学院算法设计与分析算法设计与分析动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院基本题基本题 1：编辑距离问题（编辑距离问题（第第 4 版教材版教材P79 3-2题题）。动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划【问题分析问题分析

6、】（1）算法原理分析）算法原理分析西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划（2）小结）小结：经过查阅资料和分析，大部分同学都能理解算法并编写出正确的程序，有些同

7、学还有不同的思路，有些同学将“编辑距离”视为一个对象，采用 OOP 的方法编写程序，这些都是值得鼓励的。西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划基本题基本题 2：数字三角形问题（数字三角形问题（第第 4 版教材版教材P80 3-4题题）。西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划【问题分析问题分析】（1）算法原理分析）算法原理分析根据题目描述，如下图所示，可以将数字三角形转化为右边的形式。这样可以用下三角矩阵下三角矩阵来储存各个数字。西安

8、邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划（A）最优子结构）最优子结构：从下往上看从下往上看，“最底层到底最底层到底 n - 1 层层”的最优解包含“最最底层到底底层到底 n 层层”的最优解。（B）重叠子问题）重叠子问题：要求从最底层到从最底层到 n 层的解层的解需求从最低层到从最低层到 n - 1 层的解层的解。本题可用动态规划方法求解本题可用动态规划方法求解。令 TriArray 表示数字三角形转换成的二维矩阵，ResArray i j 为结果数组，表示第表示第 i 层第层第 j 个数字到最低端的最优解个数字到最低端的最优解。则有递推式：ResArray i - 1 j =

9、max ( TriArray i - 1 j + ResArray i j ), ( TriArray i - 1 j + ResArray i j + 1 西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划算法伪代码算法伪代码西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划（2）小结）小结：本题目相对于“编辑距离”题目而言更为直观，容易思考。绝大多数同学都能正确求解。但很多同学未从“动态规划动态规划”的角度来思考本问题，这是不满足题目要求的。另外测试用例不够全面是存在的普遍问题，许多同学仅仅测试了题目给定的一个例子。事实上，题目要求数字三题目要求数字三角形的行数角形的行

10、数 n 满足条件满足条件 1 = n = 100，而且所有数字在，而且所有数字在 0 99 之间之间。因此设计测试用例时应该考虑上述条件，最好用“随机数随机数”设计方法设计方法来自动设计测试用例并自动测试（比如在同一个程序中设计一个循环，自动生成若比如在同一个程序中设计一个循环，自动生成若干个测试例子并自动测试，最后输出所有结果供分析干个测试例子并自动测试，最后输出所有结果供分析）。上机时发现的另外一个问题是有些同学编写的程序中采用字符方式从文本文件中读取数字采用字符方式从文本文件中读取数字西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划三角形的数字三角形的数字，如果这个数字大于或

11、等于 10（2 位位），就会造成错误。这需要修改程序。西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划基本题基本题 3：最大最大 k 乘积问题（乘积问题（第第 4 版教材版教材P83 3-13题题）。西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划【问题分析问题分析】（1）算法原理分析）算法原理分析先通过若干个简单例子来观察规律，摸索思路先通过若干个简单例子来观察规律，摸索思路。例如十进制整数 1234 划分为 3 段可有如下情形：1 2 34 = 681 23 4 = 9212 3 4 = 144西安邮电大学

12、计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划算法伪代码算法伪代码西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划西安邮电大学计算机学院西安邮电大学计算机学院动态规划动态规划（2）小结）小结：本题目相对容易思考，但不少同学未能做出结果。测试用例不够全面是存在的普遍问题。西安邮电大学计算机学院西安邮电大学计算机学院算法设计与分析算法设计与分析贪心算法贪心算法西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法基本题基本题 1：程序存储问题（程序存储问题（第

13、第 4 版教材版教材 P110 4-5题题）。西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法【问题分析问题分析】（1）算法原理分析）算法原理分析本题目较为简单，先对程序长度进行排序，然后用循环累加排序后的程序长度，并计数程序个数。算法伪代码算法伪代码略略西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法（2）小结）小结：本题目比较容易，同学们基本都做出了结果。但是测试用例不够全面仍然是老问题。西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法基本题基本题 2：最优分解问题（最优分解问题（第第 4 版教

14、材版教材 P113 4-15 题题）。西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法【问题分析问题分析】（1）算法原理分析）算法原理分析对整数分析可有结论：若若 a + b = const，则，则 | a b | 越小，越小，a b 越大越大。根据原问题的描述，需要将正整数需要将正整数 n 分解为若干互不相同的自然数的和，同时又要使自然数的分解为若干互不相同的自然数的和，同时又要使自然数的乘积最大乘积最大。当 n 4 时对 n 的分解的乘积是小于 n 的；当 n 大于或等于 4 时，n = 1 + ( n 1 ) 因子的

15、乘积也是小于 n 的，所以 n = a + ( n a )，2 a n - 2，可以保证乘积大于 n，即越分解乘积越大。因此可以采用如下贪心策略贪心策略：将将 n 分成从分成从 2 开始的连开始的连续自然数的和，如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面续自然数的和，如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项各项。该贪心策略首先保证了正整数所分解出的因子之差的绝对值最小，即该贪心策略首先保证了正整数所分解出的因子之差的绝对值最小，即 | a b |最小；同时又可以将其分解成尽可能多的因子，且因子的值较大，确保最终所分解最小；同时又可以将其分解成尽可能多的因子

16、，且因子的值较大，确保最终所分解的自然数的乘积可以取得最大值的自然数的乘积可以取得最大值。西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法算法伪代码算法伪代码西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法西安邮电大学计算机学院西安邮电大学计算机学院贪心算法贪心算法（2）小结）小结：本题目大部分同学设计正确，也有部分同学考虑不够全面，特别是一些边界值没有考虑。测试用例仍然是老问题。西安邮电大学计算机学院西安邮电大学计算机学院算法设计与分析算法设计与分析回溯法回溯法西安邮电大学计算机学院西安邮电大学计算机学院回溯法回溯法基本题基本题 1：最小重量机器设计问题（最小重量机器

17、设计问题（第第 4 版教材版教材 P152 5-3题题）。西安邮电大学计算机学院西安邮电大学计算机学院回溯法回溯法西安邮电大学计算机学院西安邮电大学计算机学院回溯法回溯法西安邮电大学计算机学院西安邮电大学计算机学院回溯法回溯法【问题分析问题分析】（1）算法原理分析）算法原理分析算法通过使用回溯来选择合适的机器使得在总价格不超过 d 时得到的机器重量最小。首先初始化当前价格 cp = 0, 当前重量 cw = 0。此外还要设置一个变量 sum 表示选择机器的总重量，初始化其为每个部件从 1 号供应商购买的重量。在循环选择 i 号机器时，判断从 j 号供应商购买机器后的价格是否大于总价格，如果不大

18、于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的 sum 小，如果小就赋给 sum，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个解空间搜索完毕。这样，最终得到的 sum 即为最优解。西安邮电大学计算机学院西安邮电大学计算机学院回溯法回溯法还可以加上一个剪枝条件，即在每次选择某一机器时，再判断选择后的当前重量是否已经大于之前的 sum，如果大于就没必要继续搜索，因为得到的肯定不是最优解。 西安邮电大学计算机学院西安邮电大学计算机学院回溯法回溯法算法伪代码算法伪代码西安邮电大学计算机学院西安邮电大学计算机学院回溯法回溯法（2）小结）小结：本题目是一道典型的采用回溯法求解的问题，课本上已经有通用的求解框架，有很多参考代码。大部分同学设计正确。西安邮电大学计算机学院西安邮电大学计算机学院回溯法回溯法基本题基本题 2：工作分配问题（工作分配问题（第第 4 版教材版教材 P156 5-1