《算法设计与分析》教学上机实验报告

《算法设计与分析》教学上机实验报告

实验题目：

利用分治法求解典型案例

实验目的和要求：

实验目的：

1.掌握分治算法的基本思想、技巧和效率分析方法。 
2.熟练掌握用递归设计分治算法的基本步骤。 
3.学会利用分治算法解决实际问题。

实验要求：

1.根据实验内容构思设计算法，选取适合的数据结构； 
2.对所设计的算法采用大O符号进行时间复杂性分析； 
3.上机实现算法； 
4.实验报告内容应包括问题描述、问题分析、算法设计、算法实现、运行结果及算法复杂度分析等内容。

实验过程：

1) 问题描述：大整数乘法：采用分治算法实现两个n位二进制（或者十进制）大整数的乘法。

2) 问题分析：在某些情况下，要处理很大的整数，它无法在计算机硬件能直接表示的整数范围内进行处理，若用浮点数表示，只能近似表示大小，计算结果中的有效数字也受到限制。为了解决这一问题，实现精确地表示大整数并在计算结果中精确地得到所有位数上的数字，必须采用数组存储大整数及结果，同时运用分治法进行运算：将大整数分为小整数，一直递归分解至一位数相乘，这样就很简单了，最后将结果合并，得到正确答案。

3) 算法设计：
1、分解：输