实验一 分治法
一、实验目的
1. 掌握分治法的基本思想
基本思想：即将一个规模为 n 的问题分解为 k 个规模为 m 的相互独立且与原问
题解法相同的子问题，然后将子问题的解合并得到原问题的解。
2. 掌握相关问题的分治算法
(1) 第 k 小元素问题
(2) 大整数乘法问题
3. 验证、巩固和补充课堂讲授的理论知识。
二、实验内容
(1) 第 k 小元素问题
从 n 个数中查找第 k 小元素
(2 )大整数乘法问题
采用分治法实现两个十进制大整数的乘法。
三、实验结果及分析
主要包括算法设计思路，详细设计、调试分析、运行结果以及算法的时间复杂度
分析等。
3.1. 算法设计
1) 第 k 小元素问题
使用快速排序中所采用的分划方法，以主元为基准，将一个表划分成左
右两个子表，左子表中的所有元素均小于或等于主元，而右子表中的元
素均大于或等于主元。设原表长度为 n,假定经过一趟分划，分成两个左
右子表，其中左子表是主元及其左边元素的子表，设其长度为 p，右子
表是主元右边元素的子表。那么，若 k=p,则主元就是第 k 小元素;否则若
