算法设计与分析实验报告
- 格式：doc
- 大小：170.50 KB
- 文档页数：21
南京邮电大学
页脚内容1
算法设计与分析
报告
学生姓名
学 号
专业班级
指导教师
完成时间 南京邮电大学
页脚内容2 目录
一、课程内容 ................................................................. 3
二、算法分析 ................................................................. 3
1、分治法 ................................................................ 3
（1）分治法核心思想 .................................................. 3
（2）MaxMin算法分析 ................................................. 3
2、动态规划 .............................................................. 4
（1）动态规划核心思想 ................................................ 4
（2）矩阵连乘算法分析 ................................................ 5
3、贪心法 ................................................................ 5
（1）贪心法核心思想 .................................................. 5
（2）背包问题算法分析 ................................................ 6
（3）装载问题算法分析 ................................................ 6
4、回溯法 ................................................................ 7
（1）回溯法核心思想 .................................................. 7
（2）N皇后问题非递归算法分析 ........................................ 7
（3）N皇后问题递归算法分析 .......................................... 8
三、例子说明 ................................................................. 9
1、MaxMin问题 ........................................................... 9
2、矩阵连乘 .............................................................. 9
3、背包问题 ............................................................. 10
4、最优装载 ............................................................. 10
5、N皇后问题（非递归） ................................................. 11
6、N皇后问题（递归） ................................................... 11
四、心得体会 ................................................................ 11
五、算法对应的例子代码 ...................................................... 12
1、求最大值最小值 ....................................................... 12
2、矩阵连乘问题 ......................................................... 13
3、背包问题 ............................................................. 14
4、装载问题 ............................................................. 17
5、N皇后问题（非递归） ................................................. 18
6、N皇后问题（递归） ................................................... 19
南京邮电大学
页脚内容3 一、课程内容
1、分治法，求最大值最小值，maxmin算法；
2、动态规划，矩阵连乘，求最少连乘次数；
3、贪心法，1）背包问题，2）装载问题；
4、回溯法，N皇后问题的循环结构算法和递归结构算法。
二、算法分析
1、分治法
（1）分治法核心思想
当要求解一个输入规模为n，且n的取值相当大的问题时，直接求解往往是非常困难的。如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1
那末，这类问题可以用分治法求解。
分治法的核心技术
1）子问题的划分技术。
2）递归技术。反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。
3）合并技术。
（2）MaxMin算法分析
问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。
分治策略设计思想：
将任一实例I＝(n，A(1)，…，A(n))分成两个实例 如果MAX1和MIN1是I1中的最大和最小元素，MAX2和 MIN2是I2中的最大和最小元素， MAX1和MAX2中的大者就是I中的最大元素MAX， MIN1和MIN2中的小者是I中的最小元素MIN。如果I只包含一个元素，则不需要作任何分割直接就可得到其解。
核心算法如下：
procedure MAXMIN(i,j,fmax,fmin)
global n，A[1:n] 南京邮电大学
页脚内容4 case
{ i＝j： fmax←fmin←A[i] /*只有一个元素*/
i＝j-1：if A[i]
fmax←A[j ] ；fmin←A[i]
else fmax←A[i] ；fmin←A[j]
else：mid← /*分成两部分*/
MAXMIN(i,mid,max1,min1)
MAXMIN(mid+1,j,max2,min2)
fmax←max(max1,max2)
fmin←min(min1,min2)
}
MAXMIN的时间复杂性分析
用T(n)表示比较次数，则所导出的递归关系式：
2)2/()2/(10)(nTnTnT
当n是2的幂时，即对于某个正整数k，n=2k，有
T(n)=2T(n/2)+2
=2(2T(n/4)+2)+2
=4T(n/4)+4+
=2k-1T(2)+2k-1+……+2
=2k-1+2k-2
=3n/2-2
对于任意 n ，存在整数k,有2k-1
2、动态规划
（1）动态规划核心思想
动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的。用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
设计动态规划法的步骤：
1、划分阶段（子问题），分析最优子结构性质。
2、找出阶段间的最优决策的递推关系，写出动态规划方程；
3、设计自底向上计算出最优值的步骤。
4、从最终决策的回溯子问题的决策，构造一个最优解。
南京邮电大学
页脚内容5 （2）矩阵连乘算法分析
问题：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
两个矩阵相乘所需做的数乘次数为 l*n*m， 矩阵乘法满足结合律，故矩阵连乘有可以有许多不同的计算顺序。计算顺序由加括号的方式确定，加括号的方式决定了矩阵连乘的计算量。
核心算法如下：
依次计算各层的子问题集
r=1，初始化
for i ← 1 to n do
m[i][i] ← 0
从 r=2至 r=n
for r← 2 to n do
计算所有 大小为r的子问题
MatrixChain(p[0:n]， n，m[1:n][1:n]，s [1:n][1:n])
{ 1) for i ← 1 to n do //初始化
m[i][i] ← 0
2) for r ← 2 to n do // 子问题由小到大
3) for i ← 1 to n - r+1 do //子问题的起点
4) {j←i+r-1 //子问题的终点
5) m[i][j]←m[i+1][j]+ p[i-1]*p[i]*p[j] // 初值考虑
6) s[i][j] ← i // 记录分割点
7) for k← i+1 to j-1 do //求最好的分割k
