分治法实验报告.doc

文档介绍：石家庄经济学院
《算法设计与分析》实验报告
姓名:
班级:
学号:
指导教师:
完成日期:
一、实验名称
分治法实验
二、实验目的
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字以上,提交报告时删去此行)
教师评语:

成绩: 优良中及格不及格