分治法实验报告

石家庄经济学院

《算法设计与分析》实验报告

姓名：

班级：

学号：

指导教师：

完成日期：

一、实验名称

分治法实验

二、实验目的

1. 掌握分治法的基本思想、求解问题的基本步骤；

2. 掌握分支算法的一般模式；

3. 根据问题采取有效的分解和合并的方式，能够分析确定问题的阈值；

4. 掌握分治算法的时间复杂度，并能利用C语言实现算法。

三、实验内容及要求

1. 大整数乘法。

要求：

(1) 求解两个n位的二进制整数的乘法，设n=2k；

(2) 利用分治的思想分析和求解问题；

(3) 利用C语言实现算法，要求结果正确。

2. 矩阵相乘（选做）

(1) 求解两个n阶方阵的乘法，设n=2k；

(2) 可利用基本的分解方法或者STRANSSEN方法求解；

(3) 利用C语言实现算法，要求结果正确。

四、问题分析及算法设计

1. 大整数乘法

问题分析：

算法设计：

算法复杂度分析：

2. 矩阵乘法

问题分析：

算法设计：

算法复杂度分析：

五、代码及运行结果

六、实验总结

（要求总结本次实验遇到的问题及解决方法，收获和不足，300字以上，提交报告时删去此行）

教师评语：

成绩：优良中及格不及格