实验二_递归与分治

6 算法设计与分析课程教学大纲

【适用专业】 计算机科学与技术

【课 时】 理论课时：32

【学 分】 2

【课程性质、目标和要求】

《算法设计与分析》是计算机科学与技术专业的专业课。无论是计算科学还是计算实践，算法都在其中扮演着重要角色。本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。

课程基本要求是

⑴掌握算法分析的基本概念和理论。

⑵掌握算法设计技术和分析算法以及算法复杂性。

【教学时间安排】

本课程计 2 学分，理论课时32, 学时分配如下：

序号 课程内容/实验名称 实验类型 课时 备注

1 算法引论 理论课时2

2 递归与分治策略/分治法实验 理论课时4

3 动态规划/动态规划实验 理论课时5

4 贪心算法 理论课时3

5 回溯法 理论课时3

6 分支限界法 理论课时3

7 概率算法 理论课时3

8 NP完全性理论 理论课时3

9 近似算法 理论课时3

6 10 算法优化策略 理论课时3

合 计 理论课时32

【教学内容要点】

第一章 算法引论

一、学习目的要求

1．了解算法的计算复杂性分析方法

2．理解算法分析的基本理论

3．掌握算法分析的基本概念

二、主要教学内容

1. 算法的基本概念

2. 表达算法的抽象机制

3. 采用Java语言与自然语言相结合的方式描述算法的方法

4. 算法的计算复杂性分析方法

第二章 递归与分治策略

一、学习目的要求

1．理解典型范例中递归与分治策略应用技巧

2．掌握递归与分治策略

3．掌握数学归纳法证明算法正确性方法

二、主要教学内容

1. 递归的概念

2. 分治法的基本思想

3. 二分搜索技术

众数问题

一、实验目的

1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。

2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。

3．学会利用分治算法解决实际问题。

二、问题描述

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重数集S中的重数最大的元素称为众数。 例如， S={1,2,2,2,3,5}。 多重集S得众数是2，其重数为3。 对于给定的由n个自然数组成多重数集S，计算S的众数及其重数。

三．算法设计

数据结构与核心算法的设计描述：

void split(int s[], int n, int &l, int &r) //以中间的数字为界限， 确定左右起始和终止界限

{

int mid = n/2;

for(l=0; l

{

if (s[l] == s[mid])

break;

}

for(r=l+1; r

{

if (s[r] != s[mid])

break;

}

}

// num 众数， maxCnt 重数

void getMaxCnt(int &mid, int &maxCnt, int s[], int n)

{

int l, r;

split(s, n, l, r); // 进行切割

int num = n/2;

int cnt = r-l;

// update

if (cnt > maxCnt) {

maxCnt = cnt;

mid = s[num];

}

// l 表示左边的个数，左边的个数必须大于 maxCnt 才有必要搜寻

编写人：杨玉建

1 |

算法分析(第二章)：递归与分治法

一、递归的概念

知识再现：等比数列求和公式：

1、定义： 直接或间接地调用自身的算法称为递归算法。

用函数自身给出定义的函数称为递归函数。

2、与分治法的关系：

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供

了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而

其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归

过程的产生。分治与递归经常同时应用在算法设计之中，并由此产生许多高效算

法。

3、递推方程：

(1)定义：设序列

01,....

naaa

简记为{

na

}，把

na

与某些个()

iain

联系起来的

等式叫做关于该序列的递推方程。

(2)求解：给定关于序列{

na

}的递推方程和若干初值，计算

na。

4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序

5、优缺点：

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，

因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空

间都比非递归算法要多。

二、递归算法改进：

1、迭代法：

(1)不断用递推方程的右部替代左部

(2)每一次替换，随着n的降低在和式中多出一项

(3)直到出现初值以后停止迭代

(4)将初值代入并对和式求和

(5)可用数学归纳法验证解的正确性

2、举例：

-----------Hanoi塔算法----------- ---------------插入排序算法-----------

()2(1)1

(1)1TnTn

T=−+

= ()(1)1WnWnn

W=−+−

（1）=0

编写人：杨玉建

2

|

2

1n-23()2(1)1

2[2(2)1]1

2(2)21

...

2++2...1

21nn

nTnTn

Tn

Tn

T−−=−+

=−++

=−++

=

=++

=−（1）2

()(1)1

实验2-Strassen矩阵乘法

written by yjf66@ 实验2 Strassen矩阵乘法

一、 实验目的

1. 理解Strassen矩阵乘法的分治思想

Strassen矩阵乘法的分治法设计模式是：半分+混合

2. 改进Strassen矩阵乘法对内存的需求

若按Strassen矩阵乘法的直接表述实现，则空间复杂度将是O(3n2)，本实验

将试图改进这个方面。

3. Strassen矩阵乘法的性能问题

改进Strassen矩阵乘法的内存需求，并不一定能改进Strassen矩阵乘法的效

率，本实验将试图测试一些较大规模(n>=1024)的n阶方阵的Strassen矩阵乘，

探讨其效率问题。

二、 实验环境

C/C++编程环境 或 任何编程语言环境

三、 实验内容

1． Strassen矩阵乘法描述

尽管Strassen矩阵乘法的实用价值在当今的多核计算环境下可能不是那么

显著，但其理论价值仍值得我们研究。Strassen矩阵乘法体现了一类重要的分治

算法设计模式，即半分+混合，同样具有这种算法设计模式的是FFT(Fast Fourier

Transform)-“由于FFT这个卓越算法在实践上的重要意义，有些人把它看作是

有史以来人们发明的最重要的算法之一。”[1] 实验2-Strassen矩阵乘法

written by yjf66@

Strassen矩阵乘法的基本思想，可由下述矩阵乘法概括：

输入：两个n=2k维方阵A和B（若A和B的维度不是2k，则通过增加元素

为0的行和列，以使A和B均为2k维的方阵）

输出：n维方阵C

(1)

1+41+4

43-1

1+24

1

34.12-4

3+41

13.123-11+2

24.3424.1314.1

1.2412.4

-4344

+=AB

=AB

=AB

=AB

=AB

M=AB

M=AM

M

BM

MM

(2)

为方便表示，这里采用与书本不同的下标表示法，如对于1个n/2维矩阵