算法设计与分析实验报告.pdfVIP

-

算法设计与分析

报告

学生姓名

学号

专业班级

指导教师

完成时间

目录

一、课程内容3

二、算法分析3

1、分治法3

（1）分治法核心思想3

（2）Ma*Min算法分析3

2、动态规划4

（1）动态规划核心思想4

（2）矩阵连乘算法分析5

3、贪心法5

（1）贪心法核心思想5

（2）背包问题算法分析6

（3）装载问题算法分析6

.z.

-

4、回溯法7

（1）回溯法核心思想7

（2）N皇后问题非递归算法分析7

（3）N皇后问题递归算法分析8

三、例子说明9

1Ma*Min问题9

2、矩阵连乘9

3、背包问题10

4、最优装载10

5N皇后问题（非递归）11

6N皇后问题（递归）11

四、心得体会11

五、算法对应的例子代码12

1、求最大值最小值12

2、矩阵连乘问题13

3、背包问题14

4、装载问题17

5N皇后问题（非递归）18

6N皇后问题（递归）20

.z.

-

一、课程内容

1、分治法，求最大值最小值，ma*min算法；

2、动态规划，矩阵连乘，求最少连乘次数；

3、贪心法，1）背包问题，2）装载问题；

4、回溯法，N皇后问题的循环结构算法和递归结构算法。

二、算法分析

1、分治法

（1）分治法核心思想

当要求解一个输入规模为n，且n的取值相当大的问题时，直接求解往往是非常困难

的。如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，

其中1k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。

那末，这类问题可以用分治法求解。

分治法的核心技术

1）子问题的划分技术。

2）递归技术。反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生

出不用进一步细分就可求解的子问题。

3）合并技术。

.z.

-

（2）Ma*Min算法分析

问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。

分治策略设计思想：

将任一实例I＝(n，A(1)，…，A(n))分成两个实例如果MA*1和MIN1是I1中的最大和

最小元素，MA*2和MIN2是I2中的最大和最小元素，MA*1和MA*2中的大者就是I中

的最大元素MA*，MIN1和MIN2中的小者是I中的最小元素MIN。如果I只包含一个元素，

则不需要作任何分割直接就可得到其解。

核心算法如下：

procedureMA*MIN(i,j,fma*,fmin)

globaln，A[1:n]

case

{i＝j：fma*←fmin←A[i]/*只有一个元素*/

i＝j-1：ifA[i]A[j]then/*两个元素*/

fm