分治法实验报告

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

石家庄经济学院

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

姓 名： 班 级： 学 号： 指导教师： 完成日期：

一、实验名称

分治法实验 二、实验目的

1. 掌握分治法的基本思想、求解问题的基本步骤； 2. 掌握分支算法的一般模式；

3. 根据问题采取有效的分解和合并的方式，能够分析确定问题的阈值； 4. 掌握分治算法的时间复杂度，并能利用C语言实现算法。 三、实验内容及要求

1. 大整数乘法。 要求：

(1) 求解两个n位的二进制整数的乘法，设n=2k； (2) 利用分治的思想分析和求解问题；

(3) 利用C语言实现算法，要求结果正确。 2. 矩阵相乘（选做）

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

(2) 可利用基本的分解方法或者STRANSSEN方法求解； (3) 利用C语言实现算法，要求结果正确。 四、问题分析及算法设计

1. 大整数乘法 问题分析： 算法设计：

算法复杂度分析：

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

2. 矩阵乘法 问题分析： 算法设计：

算法复杂度分析： 五、代码及运行结果 六、实验总结

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

成绩： 优良 中及格 不及格