算法分析与设计期末复习

第1章 概论

1.1 算法的概念

1.1.1 什么是算法

P3 页有算法的 5 个重要特性，通过它们判断一段程序是否为算法。

算法的5个重要特性：

（1）有限性：一个算法在执行有限步之后结束，每一步在有限时间内完成
（2）确定性：算法中的每一条指令有明确的含义，不会产生歧义
（3）可行性：算法中的每一条运算都是足够基本的，他们在原则上都能精确的执行
（4）输入性：一个算法有零个或多个输入
（5）输出性：一个算法有一个或多个输出

P2 页则有 5 个算法设计的目标，衡量一个算法的优劣。结合例子代码去理解。

算法设计应满足的目标：

（1）正确性：要求算法能够正确的执行预先规定的功能和性能要求，这是最重要也是最基本的标准
（2）可使用性：要求算法能够很方便的使用，（用户友好性）
（3）可读性：算法应该易于人的理解，可读性好，算法的逻辑应该清晰、简单、结构化
（4）健壮性：要求算法有很好的容错性，即提供异常处理，能够对不合理的数据进行检查，不经常出现异常中断或死机等情况
（5）高效率和低存储量需求：效率---算法的执行时间 存储量----算法执行过程中需要的最大存储空间 效率和低存储量都和问题的规模有关

例子代码看书

1.1.2 算法描述

除了用代码描述算法，还可以用伪代码、自然语言等。其它内容基本没用。

总结：算法描述的方式有：

代码、伪代码、自然语言

1.1.3 算法和数据结构

掌握联系与区别

算法的操作对象是数据结构

联系:一种数据结构包括逻辑结构、存储结构、算法(运算)三要素。

区别:没有本质区别。本课程介绍的算法主要面向具体的、实际的问题

1.1.4 算法设计的基本步骤

基本没用。

不过，能看到 P6 页，图 1.5 中，算法设计的最后一步是“算法分析”，可以有一点启示，这里的“分析”是分析算法复杂度，来评估其效率。而不是有人认为的分析问题，以找到解决问题的途径。

1.2 算法分析

目的是分析某算法的时间或空间效率处于什么级别。

设该算法处理的数据规模为 n,则用函数 f(n)表示算法中基本语句的执行次数(或占用的空间大小)，则算法分析就是分析随 n值增大时，f(n)的增长率级别，比如是处于log2(n),n,n^2等哪个级别。

下面举例说明为什么“级别”这么重要:

设有一个 n元素的数组，有2个功能一样的查找算法 A、B，A的级别是n,B的级别是n^2, 则数组长度由 10 增长到 20，A算法的基本语句执行次数增长 1倍，若要达到以前一样的速度，可以用双核 CPU;B算法的基本语句执行次数增长 10 倍，若要达到以前一样的速度，必须用 10 核 CPU。数据量增长一倍，硬件资源投入需增加 10 倍，若数据量很大，则很困难。

1.2.1 算法时间复杂度分析

基本语句的定义:

某算法中执行频度最高的语句（这是老师复习资料中的定义）

课本上关于基本语句的定义是：

执行次数与整个算法的执行次数成正比的语句，通常基本语句是算法中最深层循环内的语句

下面的代码将矩阵对角线元素相加，第5行为基本语句，f(n)=n.

1
2
3
4
5
6
7
int Sum(int a[],int n)
{
  int t=0;
  for(int i=0;i<n;i++)
    t=t+a[i]*i;
  return i;
}

若将循环改为：

1
2
3
4
5
  for(int i=0;i<n;i++)
{
  int k=a[i]*i;
  t=t+k;
}

则这两句都是基本语句

这时f（n）=2n，或f（n）=n都可以，采用后面这种形式，

“基本语句“代表频度最高语句的集合。无论采取哪种，后续在分析复杂度时，结果是一样的。

求出f（n）后，若它是一个和式，则只保留最高级别的项，并去掉常数系数就是复杂度。比如:

某算法的f（n）=10n2+1000n+10000，则它的复杂度为O（n2），这句话也记作

f（n）=O（n^2）（注：这里等号的含义表示某算法复杂度，不是通常数学含义）

若f（n）=10000，则算法复杂度为f（n）=0（1）

P12页递归算法的时间复杂度分析比较常用，应掌握。结合例子，看看怎么根据代码写出T（n）的递推关系式，然后展开，观察特点，化简。

1.2.2算法空间复杂度分析

算法占用的空间只计算临时空间。

比如上面这两个算法比较，由于它们都一定包括输入的数组a，因此比较时就不需要计入数组a的空间了。

对下面的函数而言，由于任何的函数调用，都需要系统的压栈操作，以保存返回地址等信息。因此它的空间复杂度时O（1），不是零。

1
void fac(){}

1.3算法设计工具——STL

知道C++模板概念或Java泛型的同学可以不看。

本课程只用到vector,queen,priority_quene 这三个，见P16页的表，P18开始有一些示例代码。

教材后面代码涉及的STL相关知识比较浅显。

问题

什么是算法：

算法是求解问题的一系列计算步骤，用来将输入数据转换成输出结果

第2章递归算法设计技术

2.1什么是递归

2.1.1递归的定义

有三个术语：递归，间接递归，尾递归。

【术语理解】

如果一个递归过程或者递归函数中的递归调用语句是最后一条执行语句，称这种递归调用为尾递归

若p函数定义中调用了p函数，称为直接递归

若p函数定义调用了q函数，而q函数定义调用了p函数，称之为间接递归

任何间接递归都可以等价的转化为直接递归，本章主要讨论直接递归

直接递归和尾递归不冲突

2.1.2何时使用递归

（1）定义是递归的

斐波那契数列，求n!等问题，许多数学公式、数列、概念的定义是递归的

（2）数据结构是递归的

单链表就是一种递归的数据结构、二叉树的二叉链存储结构

（3）问题的求解方式是递归的

如汉诺塔问题

要解决的问题能够分解成更小规模的子问题，子问题与原问题间有相似性时，可使用递归。

这种相似性，按照实际问题的特点，又分成 定义递归、结构递归、步骤递归。结合阶乘、单链表、汉诺塔去理解。

2.1.3递归模型

模型包括2部分：递归出口（终止条件），递归体。教材上按照“问题“定义的方式来举例,不看也行，我们知道一个递归程序中，递归出口与递归体分别是哪一段就可以。

2.1.4递归算法的执行过程

函数f（x）函数调用g（y）时，需要将g（y）返回后将要用到的信息压栈（自动进行）。

1
2
3
4
5
6
1: void f(int x)
2:{
3:  int t=0;
4:  t=x+g(x+1);
5:  return t;
6:}

需要压栈的信息有形参x，局部变量t，返回时，需要将g的返回值压栈。这样f恢复后从第4行接着执行时，需要的信息都从栈顶取得。

递归调用时，要一层层地压栈。结合教材上的例子，看看究竟栈是如何变化的

2.2递归算法设计

2.2.1递归与数学归纳法

数学归纳法与递归算法的联系很弱，不看。

2.2.2递归算法设计的一般步骤

递归算法的设计能力依赖于经验，多看多练，记忆步骤并没什么用。只看例2.5增加经验值。

例2.5 用递归法求一个整数数组a中的最大元素

设f(a,i)求解数组a中前i个元素（a[0]...a[i-1]）中的最大元素，这是一个大问题;

则f(a,i-1)为求解数组a中前i-1个元素（a[0]...a[i-2]）中的最大元素，这是一个小问题;

只考虑第一个元素时的情况 f(a,1)=a[0]

当i>1时，f(a,i)=MAX{f(a,i-1),a[i-1]}

对应的递归算法如下：

1
2
3
4
5
6
7
int fmax(int a[],int i)
{
  if(i==1)
    return a[0];
  else
    return max(fmax(a,i-1),a[i-1]);
}

2.2.3递归数据结构及其递归算法设计

看每个例题增加经验值，文字一概不看。

递归数据结构：采用递归方式定义的数据结构称为递归数据结构

例如正整数的定义：n是正整数，则n+1也为正整数 n+1是一种基本的递归运算

递归运算具有封闭性

基于递归数据结构的递归算法设计

例题一：一个不带头节点的单链表L，设计一个算法释放其中的所有节点

递归模型如下： 

1
2
f(L)=不做任何事   当L==NULL时
f(L)=f(L->next); 其他情况  //释放*L节点

递归算法如下： 

1
2
3
4
5
6
7
8
void DestroyList(LinkNode *&L)
{
  if(L!=NULL)
  {
    DestroyList(L->next);
    free(L);   //顺序不能搞反
  }
}
上面的代码逻辑上先挖到最底层，然后从最底层的一个节点开始释放，然后再退回起始节点，其实这里可以换一种思路来实现，如下所示(与下面的例题二统一了形式，更好理解)：

1
2
3
4
5
6
7
8
9
10
11
void DestroyList(LinkNode *&L)
{
  LinkNode *p;
  if(L!=NULL)
  {
    p=L;   //找到当前不为NULL的节点
    L=L->next;  //找下一个节点
    free(p); 
    DestroyList(L);
  }
}

第二个算法相对更好一些，因为它在每次递归调用后立即释放当前节点，能更及时地回收内存。

例题二：设计一个算法删除其中所有节点值为x的节点

递归模型如下： 

1
2
3
f(L,x)=不做任何事                 当L=NULL时
f(L,x)=删除L节点，L指向后继节点    当L->data=x时
f(L,x)=f(L->next,x)              当L->data!=x时

递归算法如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
void Delallx(LinkNode *&L,ElemType x)
{
  LinkNode *p;
  if(L==NULL) return;  //递归出口
  if(L->data==x)  
  {
    p=L;
    L=L->next;
    free(p);
    Delallx(L,x);
  }
  else Delallx(L->next,x);  //递归体
}
例题三：对于含有n个节点的二叉树，所有节点值为int类型，设计一个算法由其先序序列a和中序序列b创建对应的二叉链存储结构。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BTNode *CreateBTree(ElemType a[],ElemType b[],int n)	
//由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链
{
	int k;
	if (n<=0) return NULL;
	ElemType root=a[0];			//根结点值
	BTNode *bt=(BTNode *)malloc(sizeof(BTNode));
	bt->data=root;
	for (k=0;k<n;k++)			//在b中查找b[k]=root的根结点
		if (b[k]==root)
			break;
	bt->lchild=CreateBTree(a+1,b,k);			//递归创建左子树
	bt->rchild=CreateBTree(a+k+1,b+k+1,n-k-1);	//递归创建右子树
	return bt;
}
a,b不是一个序列嘛，怎么能加 k 这种整数，看不懂~

例题四：假设二叉树采用二叉链存储结构，设计一个递归算法释放二叉树bt中的所有节点

1
2
3
4
5
6
7
8
9
void DestroyBTree(BTNode *&bt)
{
  if(bt!=NULL)  
  {
    DestroyBTree(bt->lchild);
    DestroyBTree(bt->rchild);
    free(bt);  //放最后确保所有子节点在父节点之前被释放
  }
}

例题五：由二叉树bt复制产生另一个二叉树bt1 

1
2
3
4
5
6
7
8
9
10
11
12
void CopyBTree(BTNode *bt,BTNode *&bt1)
{
  if(bt==NULL)   //递归出口
    bt1=NULL;
  else   
  {
    bt1=(BTNode*)malloc(sizeof(BTNode));
    bt1->data=bt->data;
    CopyBTree(bt->lchild,bt1->lchild);
    CopyBTree(bt->rchild,bt1->rchild);
  }
}
例五好有意思~

例题六：输出从根节点到x值的节点的路径（有点像搜索问题）

先看递归模型：

1
2
3
f(b,x,path)=false   当 b==NULL
f(b,a,path)=true(将x加入到path中)     当 b->data==x
f(b,x,path)=true（将b->data加入到path中）   当f(b->lchild,x,path)或者f(b->rchild,x,path)为true时

本身为目标节点，或者当前节点的左右子节点是目标节点时，才能将对应的节点加入到path中

算法如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool Findxpath1(BTNode *bt,int x,vector<int> &path)	//解法1
//求根结点到x结点的（逆向）路径
{
	if (bt==NULL)					//空树返回false
		return false;
	if (bt->data==x)				//找到值为x的结点
	{
		path.push_back(x);			//结点值加入path中，并返回true
		return true;
	}
	else if (Findxpath1(bt->lchild,x,path) || Findxpath1(bt->rchild,x,path)) //在判断语句中设置递归，比较有意思~
	{
		path.push_back(bt->data);	//结点值加入path中，并返回true
		return true;
	}
}

解法二： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool Findxpath2(BTNode *bt,int x,vector<int> tmppath,vector<int> &path)	//解法2
//求根结点到x结点的（正向）路径
{
	if (bt==NULL)							//空树返回false
		return false;
	tmppath.push_back(bt->data);			//当前结点加入path
	if (bt->data==x)						//当前结点值为x，返回true
	{
		path=tmppath;
		return true;
	}
	bool find=Findxpath2(bt->lchild,x,tmppath,path);//在左子树中查找
	if (find)								//左子树中成功找到
		return true;
	else									//左子树中没有找到，在右子树中查找
		return Findxpath2(bt->rchild,x,tmppath,path);
}

2.2.4基于归纳思想的递归算法设计

例题不典型，不看。

2.3递归算法设计示例

2.3.1简单选择排序和冒泡排序

增加经验值。体会大数组的排序，转变成小数组的排序

例题一：简单选择排序:在无序区选择最小元素放在开头处

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 简单选择排序递归算法
void SelectSort(int a[],int n,int i)
{
  int j,k;
  if(i==n-1) return;   //数组范围是a[i]到a[n-1]共n-i个元素
  else
  {
    k=i;
    for(j=i+1;j<n;j++)   //从i后面找到最小的元素的下标，记为k
    {
      if(a[j]<a[k])
        k=j;
    }
    if(k!=i)    //最小元素不是a[i]
      swap(a[i],a[k]);  //交换两个元素，这里不展示
    SelectSort(a,n,i+1);
  }   
}

例题二：冒泡排序：采用交换的方式将无序区中最小的元素放到开头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 冒泡排序递归算法
void BubbleSort(int a[],int n,int i)
{
  int j;
  bllo exchang;
  if(i==n-1) return;   //满足递归出口条件
  else
  {
    exchang=false;
    for(j=n-1;j>i;j--)
    {
      if(a[j]<a[j-1])   //当相邻元素反序时
      {
        swap(a[j],a[j-1]);
        exchang=true;
      }
    }
    if(exchang==false)  //当没有反序时算法结束
      return;
    else
      BubbleSort(a,n,i+1);
  }
}

感觉递归的冒泡排序更复杂一点呢，怎么说呢，不是很喜欢......

2.3.2求解n皇后问题

增加经验值。体会大棋盘，转变成小棋盘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//求解n皇后问题的递归模型
void queen(int i,int n)
{
  if(i>n)
    dispasolution(n);    //皇后放置结束，输出结果，不展示
  else
  {
    for(int j=1;j<=n;j++)   //在第i行试探每一列j
    {
      if(place(i,j))   //找到合适的位置（i，j）
      {
        q[i]=j;  
        queen(i+1,n);  //递归，这里没啥说的
      }
    }
  }
}

2.4递归算法转化为非递归算法

2.4.1用循环结构替代递归过程

直接转换法适合尾递归。想想为什么？

尾递归只有一个递归调用语句，而且是处于算法的最后，当递归调用返回时返回到上一层再递归调用下一句语句，而这个返回的位置正好是算法的末尾

采用循环结构求解n!的非递归算法如下：(属于尾递归) 

1
2
3
4
5
6
7
8
9
int fun1(int n)
{
  int f=1,i;
  for(i=2;i<=n;i++)
  {
    f=f*i;
  }
  return f;
}

采用循环结构求解斐波那契数列的非递归算法如下：（属于单向递归） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int F(int n)
{
  int i,f1,f2,f3;
  if(n==1||n==2)
    return 1;
  f1=1,f2=1;
  for(i=3;i<=n;i++)
  {
    f3=f1+f2;
    f1=f2;
    f2=f3;
  }
  return f3;
}

2.4.2用栈消除递归过程

代替函数调用使用的系统栈，是对函数调用过程的模拟，通过教材上的例子体会。

2.5递推式的计算

递归算法的复杂度分析时，其基本语句的执行次数写成递推式，要化简后才能得到复杂度。第一章通过将递推式展开，来寻找数列的规律，然后求和的方法来做到这一点。这里提供了更一般化的方法。

2.5.1用特征方程求解递归方程

不常用，不看。

2.5.2用递归树求解递归方程

常用。

例题：分析以下递归方程的时间复杂度

1
2
T(n)=1             当n=1时
T(n)=2T(n/2)+n^2   当n>1时

时间复杂度为：O（n^2）,详见课本P77

课本还有一个例题也值得关注下！

2.5.3用主方法求解递归方程

常用。

一般方法

看书P78

对于一般的方程：

T(n)=aT(n/b)+f(n)

a,b是常数且a大于等于1，b大于1

比较函数n^(logba)（以b为底）与f(n)的大小关系

取较大的那一个

第3章分治法

3.1分治法概述

3.1.1分治法的设计思想

P84页本小节第1段，是分治法的定义。后面看到具体实例的时候，要回顾该定义是怎么体现在其中的。别的文字没什么用。

递归解决子问题（这是在第二章的基础上进行的！！！）

3.1.2分治法的求解过程

P85页最上方绿色字体，是三个步骤。其实也是对分治法定义的解析。别的文字没什么用。

分解成若干个子问题

求解子问题

合并子问题

3.2求解排序问题

3.2.1快速排序

从数据结构、算法这两门课的角度看，都是经典。其中快排中“划分”这一步骤，应用特别广泛。

划分：整个序列被基准分割成两个子序列，基准位于两个子序列中间，一小一大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//快速排序算法
#include <stdio.h>
void disp(int a[],int n)		//输出a中所有元素
{	int i;
	for (i=0;i<n;i++)
		printf("%d ",a[i]);
	printf("\n");
}
int Partition(int a[],int s,int t)	//划分算法
{	int i=s,j=t;
	int tmp=a[s];				//用序列的第1个记录作为基准
	while (i!=j)				//从序列两端交替向中间扫描,直至i=j为止
	{	while (j>i && a[j]>=tmp) 
			j--;				//从右向左扫描,找第1个关键字小于tmp的a[j]
		a[i]=a[j];				//将a[j]前移到a[i]的位置
		while (i<j && a[i]<=tmp) 
			i++;				//从左向右扫描,找第1个关键字大于tmp的a[i]
		a[j]=a[i];				//将a[i]后移到a[j]的位置
	}
	a[i]=tmp;       // tmp这个值在最中间，左边全是比其小的，右边全是比其大的
	return i;
}
void QuickSort(int a[],int s,int t)	//对a[s..t]元素序列进行递增排序
{	int i;
	if (s<t) 					//序列内至少存在2个元素的情况
	{	i=Partition(a,s,t);
		QuickSort(a,s,i-1);		//对左子序列递归排序
		QuickSort(a,i+1,t);		//对右子序列递归排序
	}
}
int main()
{	int n=10;
	int a[]={2,5,1,7,10,6,9,4,3,8};
	printf("排序前:"); disp(a,n);
	QuickSort(a,0,n-1);
	printf("排序后:"); disp(a,n);
}

3.2.2归并排序

归并排序，结合微助教上的“求逆序数”来看。

二路归并、多路归并

自底向上的二路归并排序算法，将两个相邻的有序子序列合并为一个有序子序列的过程。

自顶向下的二路归并排序算法，属于典型的二分法算法

课本习题：3.8.3

求排列的逆序数（分治）

一、题目描述

在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列，求它的逆序数。

输入

第一行是一个整数n，表示该排列有n个数（n <= 100000）。 第二行是n个不同的正整数，之间以空格隔开，表示该排列。

输出

输出该排列的逆序数。

样例输入

6

2 6 3 4 5 1

样例输出

8

提示

1、利用二分归并排序算法（分治）； 与二路归并排序非常相似。

2、在合并过程中，（low<=i<=mid,mid+1<=j<=high）,当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在前半部分比i大的元素都比a[j]大，产生的逆序数个数为mid-i+1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 using namespace std;
5 int n,a[100009],tmp[100009];
6 long long sum;
7 void Merge_sort(int,int);
8 void Merge_nx(int,int,int);
9 int main()
10 {
11     scanf("%d",&n);
12     for(int i=1;i<=n;i++)
13     scanf("%d",&a[i]);
14     Merge_sort(1,n);
15     printf("%d",sum);//输出逆序总数 
16     return 0;
17 }
18 void Merge_sort(int l,int r)   //这里使用的是自顶向下的方法
19 {
20     if(l<r)//要有判断 
21     {
22     int mid=(l+r)>>1;// 
23     Merge_sort(1,mid);//归并左边 
24     Merge_sort(mid+1,r);//归并右边 
25     Merge_nx(l,mid,r);//归并排序 
26     }
27 }
28 void Merge_nx(int l,int m,int r)  //左边右边和中间的下标
29 {
30     int z=l,y=m+1;
31     int num=l;    
32     while(z<=m&&y<=r)  //两个子序列都没用完
33     {
34         if(a[z]<=a[y])
35         {
36             tmp[num++]=a[z++];  
37         }
38         else
39         {
40             tmp[num++]=a[y++];
41             sum+=(m-z+1); //逆序总数 
42         }
43     }
44     while(z<=m){tmp[num++]=a[z++];}//将剩下的直接放入 
45     while(y<=r){tmp[num++]=a[y++];}
46     for(int i=l;i<=r;i++)
47         a[i]=tmp[i];//将排好的数返回数组a
48 }

【问题】为何能够基于归并排序求解逆序数？

在合并过程中，（low<=i<=mid,mid+1<=j<=high）,当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在前半部分比i大的元素都比a[j]大，产生的逆序数个数为mid-i+1.

这里需要搞懂！！！

3.3求解查找问题

3.3.1查找和次大元素

较简单，浏览一下，对理解分治法不错，帮助提高写递归程序的能力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//求解最大和次大元素算法
#include <stdio.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define INF 99999		//表示最大的整数
void solve(int a[],int low,int high,int &max1,int &max2)
{
	if (low==high)		//区间只有一个元素
	{
		max1=a[low];
		max2=-INF;
	}
	else if (low==high-1)	//区间只有两个元素
	{
		max1=max(a[low],a[high]);
		max2=min(a[low],a[high]);
	}
	else
	{
		int mid=(low+high)/2;
		int lmax1,lmax2;
		solve(a,low,mid,lmax1,lmax2);		//左区间求lmax1和lmax2
		int rmax1,rmax2;
		solve(a,mid+1,high,rmax1,rmax2);	//右区间求lmax1和lmax2
		if (lmax1>rmax1)
		{
			max1=lmax1;
			max2=max(lmax2,rmax1);	//lmax2,rmax1中求次大元素
		}
		else
		{
			max1=rmax1;
			max2=max(lmax1,rmax2);	//lmax1,rmax2中求次大元素
		}
	}
}

3.3.2折半查找

体会分治法可以使用递归与非递归2种形式

折半查找（二分查找）

折半查找要求序列是有序的，假设递增

折半查找的递归与非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//递归和非递归折半查找算法
#include <stdio.h>
int BinSearch(int a[],int low,int high,int k) //递归拆半查找算法
{	int mid;
	if (low<=high)				//当前区间存在元素时
	{	mid=(low+high)/2;		//求查找区间的中间位置
		if (a[mid]==k)			//找到后返回其物理下标mid
			return mid;
		if (a[mid]>k)			//当a[mid]>k时,在a[low..mid-1]中递归查找
			return BinSearch(a,low,mid-1,k);
		else					//当a[mid]<k时,在a[mid+1..high]中递归查找
			return BinSearch(a,mid+1,high,k);
	}
	else	return -1;			//若当前查找区间没有元素时返回-1
}
int BinSearch1(int a[],int n,int k)	//非递归拆半查找算法
{	int low=0,high=n-1,mid;
	while (low<=high)			//当前区间存在元素时循环
	{	mid=(low+high)/2;		//求查找区间的中间位置
		if (a[mid]==k)			//找到后返回其物理下标mid
			return mid;
		if (a[mid]>k)			//继续在a[low..mid-1]中查找
			high=mid-1;
		else					//a[mid]<k
			low=mid+1;			//继续在a[mid+1..high]中查找
	}
	return -1;					//若当前查找区间没有元素时返回-1
}
void main()
{	int n=10,i;
	int k=6;
	int a[]={1,2,3,4,5,6,7,8,9,10};
	i=BinSearch(a,0,n-1,k);
	if (i>=0)	printf("a[%d]=%d\n",i,k);
	else printf("未找到%d元素\n",k);
}

算法的时间复杂度计算：

对应的搜索树的高度为：log2n（向下取整）+1

折半查找的时间复杂度为O（log2n）

3.3.3寻找一个序列中第k小的元素

特别重要。以它为基础，可解算法里很多题

先给这个序列进行排序，采用类似快速排序的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//找第k小元素的算法
int QuickSelect(int a[],int s,int t,int k)	//在a[s..t]序列中找第k小的元素
{	int i=s,j=t;
	int tmp;
	if (s<t) 					//区间内至少存在2个元素的情况
	{	tmp=a[s];				//用区间的第1个记录作为基准
		while (i!=j)			//从区间两端交替向中间扫描,直至i=j为止
		{	while (j>i && a[j]>=tmp) 
				j--;			//从右向左扫描,找第1个关键字小于tmp的a[j]
			a[i]=a[j];			//将a[j]前移到a[i]的位置
			while (i<j && a[i]<=tmp) 
				i++;			//从左向右扫描,找第1个关键字大于tmp的a[i]
			a[j]=a[i];			//将a[i]后移到a[j]的位置
		}
		a[i]=tmp;
		if (k-1==i) return a[i];
		else if (k-1<i) return QuickSelect(a,s,i-1,k);	//在左区间中递归查找
		else return QuickSelect(a,i+1,t,k);				//在右区间中递归查找
	}
	else if (s==t && s==k-1)	//区间内只有一个元素并且s是第k小的元素的下标（k-1）
		return a[k-1];
}

3.3.4寻找两个等长有序序列的中位数

重要，同时又一定难度。在搞清算法原理的基础上，会觉得比较精妙，看似繁杂的步骤，也不用记忆，很自然就知道怎么解，参考微助教。思考的起点是：一个序列，从它的两端各去掉相同数量的元素，中位数不变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//寻找两个等长有序序列的中位数的算法
void prepart(int &s,int &t)			//求a[s..t]序列的前半子序列
{	int m=(s+t)/2;
	t=m;
}
void postpart(int &s,int &t)		//求a[s..t]序列的后半子序列
{	int m=(s+t)/2;
	if ((s+t)%2==0)					//序列中有奇数个元素
		s=m;
	else							//序列中有偶数个元素
		s=m+1;
}
double midnum(int a[],int s1,int t1,int b[],int s2,int t2)
{	//求两个有序序列a[s1..t1]和b[s2..t2]的中位数
	int m1,m2;
	if (s1==t1 && s2==t2)	//两序列只有一个元素时返回较小者
		return a[s1]<b[s2]?a[s1]:b[s2];
	else
	{	m1=(s1+t1)/2;				//求a的中位数
		m2=(s2+t2)/2;				//求b的中位数
		if (a[m1]==b[m2])			//两中位数相等时返回该中位数
			return a[m1];
		if (a[m1]<b[m2])			//当a[m1]<b[m2]时
		{	postpart(s1,t1);		//a取后半部分
			prepart(s2,t2);			//b取前半部分
			return midnum(a,s1,t1,b,s2,t2);
		}
		else						//当a[m1]>b[m2]时
		{	prepart(s1,t1);			//a取前半部分
			postpart(s2,t2);		//b取后半部分
			return midnum(a,s1,t1,b,s2,t2);
		}
	}
}

还有等价的非递归算法，不做说明（就是改成了while循环而已）

或者考虑将其排个序，合成一个递增数组，然后直接求中位数

例3.2不看。

3.4求解组合问题

3.4.1求解最大连续子序列和问题

比起3.3.1，3.3.2的例子更有启发性的例子。在大致阅读文字，粗浅地了解原理后，阅读代码能更清楚地反映细节。

采用分治法解决，书上的思想将问题分为三种情况展开讨论：

先对整个序列从中部划分左右各一半

（1）最大子序列和完全在左半部，递归求解左半部的最大子序列和

（2）最大子序列和完全在右半部，递归求解右半部的最大子序列和

（3）最大子序列和横跨左右半部，该子序列和中一定会含有mid元素，求出最大值

上述三种情况再求最大值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//求解最大连续子序列和的算法
long max3(long a,long b,long c)				//求出三个long中的最大值
{	if (a<b) a=b;							//用a保存a、b中的最大值
	if (a>c) return a;						//比较返回a、c中的最大值
	else return c;  
} 
long maxSubSum4(int a[],int left,int right)	//求a[left..right]序列中最大连续子序列和
{	int i,j;
	long maxLeftSum,maxRightSum;
	long maxLeftBorderSum,leftBorderSum;
	long maxRightBorderSum,rightBorderSum;
	if (left==right)						//子序列只有一个元素时
	{	if (a[left]>0) 					//该元素大于0时返回它
			return a[left];
		else								//该元素小于或等于0时返回0
			return 0; 
	} 
	int mid=(left+right)/2;					//求中间位置
	maxLeftSum=maxSubSum4(a,left,mid);		//求左边的最大连续子序列之和
	maxRightSum=maxSubSum4(a,mid+1,right);	//求右边的最大连续子序列之和
	maxLeftBorderSum=0,leftBorderSum=0;
	for (i=mid;i>=left;i--)		//求出以左边加上a[mid]元素构成的序列的最大和
	{	leftBorderSum+=a[i];
		if (leftBorderSum>maxLeftBorderSum)
			maxLeftBorderSum=leftBorderSum;
	}
	maxRightBorderSum=0,rightBorderSum=0;
	for (j=mid+1;j<=right;j++)	//求出a[mid]右边元素构成的序列的最大和
	{	rightBorderSum+=a[j];
		if (rightBorderSum>maxRightBorderSum)
			maxRightBorderSum=rightBorderSum;
	}
	return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum); 
}

上述算法无法求解最大连续子序列积的问题，因为该问题的子序列不满足最优性原理！

分治法需要满足最优性原理

即整个问题的最优解由各个子问题的最优解构成！

3.4.2求解棋盘覆盖问题

了解原理。体会分治法从一维走向二维

这里第一遍复习时没看，后面有时间补，感觉不是很重要

3.4.3求解循环日程安排问题

日常有用，对分治法的理解帮助不大，不用看。

3.5求解大整数乘法和矩阵乘法问题

不典型，不看。

3.6并行计算简介

具体的硬件相关，不看。

第4章蛮力法

4.1蛮力法概述

蛮力法，也叫暴力法(brute force method),穷举法。

原理：把所有可能的解列举出来，找出满足条件的解。

特点：通用性强，效率低。

通过看后面小节中的例子，来理解上述三点。其它内容可不看。

（教材上将蛮力法应用的场景分成4种，可以在后面几节的例子里去体会它们属于哪一种。这些也不紧要。）

4.2蛮力法的基本应用

4.2.1采用直接穷举思路的一般格式

例4.1

前提知识是一个数m除了本身以外的其他因子都在1-m/2之间，只需要遍历这个区间即可，减少运算量

1
2
3
4
5
6
7
8
9
10
11
12
13
//例4.1
#include <stdio.h>
void main()
{	int m,i,s;
	for (m=2;m<=1000;m++)
	{	s=0;
		for (i=1;i<=m/2;i++)
			if (m%i==0) s+=i;   //i是m的一个因子
		if (m==s)   //所有的因子和s等于原数m，是我们要找的完全数
			printf("%d ",m);
	}
	printf("\n");
}

例4.3 计算一个逻辑算式各个符号代表什么具体的数字 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//例4.3
void fun()
{	int a,b,c,d,e,m,n,s;
	for (a=1;a<=9;a++)
		for (b=0;b<=9;b++)
			for (c=0;c<=9;c++)
				for (d=0;d<=9;d++)
					for (e=0;e<=9;e++)   //5个自变量，5重循环
						if (a==b || a==c || a==d || a==e || b==c || b==d 
								 || b==e || c==d || c==e || d==e)   //个不相等才行
							continue;
						else
						{	m=a*1000+b*100+c*10+d;
							n=a*1000+b*100+e*10+d;
							s=e*10000+d*1000+c*100+a*10+d;
							if (m+n==s)
								printf("兵:%d 炮:%d 马:%d 卒:%d 车:%d\n",
									a,b,c,d,e);
						}
}

4.2.2简单选择排序和冒泡排序

不看

4.2.3字符串匹配

看

直接穷举法，也称为BF算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int BF(string s,string t)	//字符串匹配
{
	int i=0,j=0;
	while (i<s.length() && j<t.length())
	{
		if (s[i]==t[j])		//比较的两个字符相同时
		{
			i++; j++;       //比翼齐飞
		}
		else				//比较的两个字符不相同时
		{
			i=i-j+1;		//i回退到原来i的下一个位置
			j=0;			//j从0开始  重新来过
		}
	}
	if (j==t.length())		//t的字符比较完毕
		return i-j;			//t是s的子串,返回位置（t的首字母在s中的下标）
	else					//t不是s的子串
		return -1;			//返回-1
}

例题4.5

比较简单，不看了

4.2.4求解最大连续子序列和问题

三种方法，很有代表性。结合图4.5，看代码来分析a[i][j]元素的计算量的多寡，课件上更清晰。

第三章使用分治法求解过，现在使用穷举法思想解决之，看课本解释

思路一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//求解最大连续子序列和问题-解法1
int maxSubSum1(int a[],int n)		//求a的最大连续子序列和
{	int i,j,k;
	int maxSum=0,thisSum; 
	for (i=0;i<n;i++)				//两重循环穷举所有的连续子序列
	{	for (j=i;j<n;j++)
		{	thisSum=0;
			for (k=i;k<=j;k++)   //计算从i到j的序列和
				thisSum+=a[k];    //求解当前子序列的和
			if (thisSum>maxSum)	//通过比较求最大连续子序列之和
				maxSum=thisSum;  //maxsum是历史最优 thissum是本局最优
		}
	}
	return maxSum;
}

本质上是三重循环，时间复杂度为O（n^3）

思路二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//求解最大连续子序列和问题-解法2
int maxSubSum2(int a[],int n)	//求a的最大连续子序列和
{	int i,j;
	int maxSum=0,thisSum;
	for (i=0;i<n;i++)  
	{	thisSum=0;
		for (j=i;j<n;j++)
		{	thisSum+=a[j];   //thissum表示从i开始，往后到任意位置（最多是最后）的最优解
			if (thisSum>maxSum)  
				maxSum=thisSum;
		}
	}
	return maxSum;
}

解法二两重循环，时间复杂度为O(n^2)

思路三

1
2
3
4
5
6
7
8
9
10
11
12
//求解最大连续子序列和问题-解法3
int maxSubSum3(int a[],int n)		//求a的最大连续子序列和
{	int i,maxSum=0,thisSum=0;
	for (i=0;i<n;i++)
	{	thisSum+=a[i];
		if (thisSum<0)		//若当前子序列和为负数，则重新开始下一个子序列
			thisSum=0;   
		if (maxSum<thisSum)	//比较求最大连续子序列和
			maxSum=thisSum;  //这里更新全局最优值
	}
	return maxSum;
}

解法三只需要遍历一遍数组，时间复杂度为O(n)

4.2.5求解幂集问题

算法中的基本问题，要掌握。

幂集问题可以使用穷举法实现，例题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//求解幂集问题-解法1
//求a{1,2,3}的幂集
#include <stdio.h>
#include <math.h>
#define MaxN 10
void inc(int b[], int n)		//将b表示的二进制数增1
{	for(int i=0;i<n;i++)		//遍历数组b
	{	if(b[i])				//将元素1改为0
			b[i]=0;
		else					//将元素0改为1并退出for循环
		{	b[i]=1;
			break;
		}
	}
}
void PSet(int a[],int b[],int n)	//求幂集
{	int i,k;
	int pw=(int)pow(2,n);			//求2^n
	printf("1～%d的幂集:\n  ",n);
	for(i=0;i<pw;i++)			//执行2^n次
	{	printf("{ ");
		for (k=0;k<n;k++)		//执行n次
			if(b[k])
				printf("%d ",a[k]);
		printf("} ");
		inc(b,n);				//b表示的二进制数增1
	}
	printf("\n");
}
void main()
{	int n=3;
	int a[MaxN],b[MaxN];
	for (int i=0;i<n;i++)
	{	a[i]=i+1;			//a初始化为{1,2,3}
		b[i]=0;				//b初始化为{0,0,0}
	}
	PSet(a,b,n);
}

求幂集问题上面的例题有三个元素，可以对应三位二进制 从000-111 0表示不选，1表示选择

利用二叉选择树来进行求解亦可

4.2.6求解简单0/1背包问题

经典问题。以前一节为基础。

可以尝试在前一节的基础上开展，0表示不选，1表示选择

求出幂集即可求出结果，具体实现细节不多赘述

因为是蛮力法嘛，就是求出全部的排列情况，就知道哪个方案最好了

4.2.7求解全排列问题

算法中的基本问题，要掌握。

给定正数n，求解1-n的所有全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//求解全排列问题
#include <stdio.h>
#include <vector>
using namespace std;
vector<vector<int> > ps;						//存放全排列
void Insert(vector<int> s,int i,vector<vector<int> > &ps1)
//在每个集合元素中间插入i得到ps1
{	vector<int> s1;
	vector<int>::iterator it;
	for (int j=0;j<i;j++)						//在s(含i-1个整数)的每个位置插入i
	{	s1=s;
		it=s1.begin()+j;						//求出插入位置
		s1.insert(it,i);						//插入整数i
		ps1.push_back(s1);						//添加到ps1中
	}
}
void Perm(int n)								//求1～n的所有全排列
{	vector<vector<int> > ps1;					//临时存放子排列
	vector<vector<int> >::iterator it;			//全排列迭代器
	vector<int> s,s1;
	s.push_back(1);
	ps.push_back(s);							//添加{1}集合元素
	for (int i=2;i<=n;i++)						//循环添加1～n
	{	ps1.clear();							//ps1存放插入i的结果
		for (it=ps.begin();it!=ps.end();++it)
			Insert(*it,i,ps1);					//在每个集合元素中间插入i得到ps1
		ps=ps1;
	}
}
void dispps()									//输出全排列ps
{	vector<vector<int> >::reverse_iterator it;	//全排列的反向迭代器
	vector<int>::iterator sit;					//排列集合元素迭代器
	for (it=ps.rbegin();it!=ps.rend();++it)
	{	for (sit=(*it).begin();sit!=(*it).end();++sit)
			printf("%d",*sit);
		printf("  ");
	}
	printf("\n");
}
void main()
{	int n=3;
	printf("1～%d的全排序如下:\n  ",n);
	Perm(n);
	dispps();
}

4.2.8求解任务分配问题

经典问题。以前一节为基础。

在前一节的基础上可以理解为一种排列就是一种分配方案（和顺序的1234相比）

4.3递归在蛮力法中的应用

4.3.1用递归方法求解幂集问题

结合4.2.5看。

4.3.2用递归方法求解全排列问题

结合4.2.7看。

4.3.3用递归方法求解组合问题

难度比前2节大，更精妙，理解之后很愉快。

从1-n个正整数中取出k个不重复的正整数的所有组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//递归求解组合列问题
#include <stdio.h>
#define MAXK 10
int a[MAXK];					//存放一个组合
int n,k;						//全局变量
void dispacomb()				//输出一个组合
{
	for (int i=0;i<k;i++)
		printf("%3d",a[i]);
	printf("\n");
}
void comb(int n,int k)	     //求1..n中k个整数的组合
{
	if (k==0)					//k为0时输出一个组合
		dispacomb();
	else
	{	for (int i=k;i<=n;i++)
		{	a[k-1]=i;	       //a[k-1]位置取k～n的整数
			comb(i-1,k-1); 	   //a[k-1]组合a[0..i-1]中的k-1个整数产生一个组合   
			//就是最后一个数一定不能从前面1到k-1中取，不然1到k-2个数不够分给k-1个位置的，所以对于最后一个数来说，其取值的坐标范围应该是k到n
			//然后对于未安排的最后一个数重复上述操作即可
		}
	}
}
void main()
{	
	n=5; k=3;
	printf("1..%d中%d个的整数的所有组合:\n",n,k);
	comb(n,k);
}

4.4图的深度优先和广度优先遍历

不看

第5章回溯法

5.1回溯法概述

5.1.1问题的解空间

1.术语：解空间、可行解、最优解。

本节的例子，只能说明术语 解空间。到5.2节的0—1背包问题，可体会这三个术语究竟指什么。

2.术语：子集树、排列树

结合图5.2理解子集树、图5.4理解排列树。

子集树：当所给的问题是从n个元素的集合S中找到满足某种性质的子集时，对应的解空间树称为子集树。

排列树当所给的问题是确定n个元素满足某种性质的排列时，对应的解空间树称为排列树。

本小节的图5.3的例子由于问题本身比较繁琐，并不适合作为例子理解回溯法，故不要看

5.1.2什么是回溯法

1.术语：活结点、扩展结点、死结点

所有例子都可用于理解它们

2.术语：剪枝函数、约束函数、限界函数

下一小节例5.2可用于理解约束函数，直到5.2节的0—1背包问题才出现限界函数。在此之前的其它例子，都不包括剪枝函数。

剪枝函数包括约束函数和限界函数;

约束函数是在拓展结点处剪除不满足约束条件的路径（注意是在拓展的时候）

限界函数是剪去得不到问题解或者最优解的路径（这里可以理解为遍历树时剔除的分枝）

5.1.3回溯法的算法框架及其应用

算法的框架只粗略浏览一下即可，必须要多看几个实例，从实例中去总结经验，再反过来看这个框架才能理解。

回溯法的框架分为非递归和递归两种

书上的例子都可以看看

递归回溯框架：

求幂集问题(子集树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//例5.3的算法1
#include <stdio.h>
#include <string.h>
#define MAXN 100
void dispasolution(int a[],int n,int x[])	//输出一个解
{
	printf("   {");
	for (int i=0;i<n;i++)
		if (x[i]==1)
			printf("%d",a[i]);
	printf("}");
}
void dfs(int a[],int n,int i,int x[])	//回溯算法
{
	if (i>=n)   //到达叶子节点
		dispasolution(a,n,x);
	else
	{
		x[i]=0;                 //0表示不选，1表示选
		dfs(a,n,i+1,x);			//不选择a[i]
		x[i]=1;
		dfs(a,n,i+1,x);			//选择a[i]
	}
}
void main()
{
	int a[]={1,2,3};				//s[0..n-1]为给定的字符串,设置为全局变量
	int n=sizeof(a)/sizeof(a[0]);
	int x[MAXN];					//解向量
	memset(x,0,sizeof(x));			//解向量初始化
	printf("求解结果\n");
	dfs(a,n,0,x);
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//例5.3的算法2
#include <stdio.h>
#include <vector>
using namespace std;
void dispasolution(vector<int> path)		//输出一个解
{
	printf("   {");
	for (int i=0;i<path.size();i++)
			printf("%d",path[i]);
	printf("}");
}
void dfs(int a[],int n,int i,vector<int> path)	//回溯算法求子集path
{
	if (i>=n)
		dispasolution(path);
	else
	{
		dfs(a,n,i+1,path);			//不选择a[i]
		path.push_back(a[i]);
		dfs(a,n,i+1,path);			//选择a[i]
	}
}
int main()
{
	int a[]={1,2,3};				//s[0..n-1]为给定的字符串,设置为全局变量
	int n=sizeof(a)/sizeof(a[0]);
	vector<int> path;         //用容器path存放获得的子集
	printf("求解结果\n");
	dfs(a,n,0,path);
	printf("\n");
}

例题5.4 排列树框架

可以理解为运算符合和这些数字之间的排列组合，检查是否满足题目的条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//例5.4算法
#include <stdio.h>
#define N 9
void fun(char op[],int sum,int prevadd,int a[],int i)
{
	if (i==N)						//扫描完所有位置
	{
		if (sum==100)				//找到一个解
		{
			printf("  %d",a[0]);	//输出解
			for (int j=1;j<N;j++)
			{
				if (op[j]!=' ')
					printf("%c",op[j]);
				printf("%d",a[j]);
			}
			printf("=100\n");
		}
		return;
	}

	//计算+
	op[i]='+';						//位置i插入'+' 
	sum+=a[i];						//计算结果
	fun(op,sum,a[i],a,i+1);			//继续处理下一个位置
	sum-=a[i];						//回溯

	//计算-
	op[i]='-';						//位置i插入'-'
	sum-=a[i];						//计算结果
	fun(op,sum,-a[i],a,i+1);		//继续处理下一个位置
	sum+=a[i];						//回溯

	//计算空（表示左右两个连在一起）
	op[i]=' ';						//位置i插入' '
	sum-=prevadd;					//先减去前面的元素值
	int tmp;						//计算新元素值
	if (prevadd>0)
		tmp=prevadd*10+a[i];		//如prevadd=5,a[i]=6,结果为56
	else
		tmp=prevadd*10-a[i];		//如prevadd=-5,a[i]=6,结果为-56
	sum+=tmp;						//计算合并结果
	fun(op,sum,tmp,a,i+1);			//继续处理下一个位置
	sum-=tmp;						//回溯sum
	sum+=prevadd;                   //再加上前面的元素值
}
void main()
{
	int a[N];
	char op[N];					//op[i]表示在位置i插入运算符
	for (int i=0;i<N;i++)		//为a赋值为1,2，...,9
		a[i]=i+1;
	printf("求解结果\n");
	fun(op,a[0],a[0],a,1);		//插入位置i从1开始
}

5.1.4回溯法与深度优先遍历的异同

本节的精华都在最后一句：回溯法=DFS+剪枝。结合前面的例子来理解。其它的描述都不看。

5.1.5回溯法的时间分析

看过后，再看后面的例子时，都要进行复杂度分析。

通常，解空间树为子集树时对应算法的时间复杂度为O(n^2);涉及到选与不选的问题

解空间树为排列树时对应的算法时间复杂度为O(n!)，涉及到排列组合的问题

5.2求解0/1背包问题

本节无废话，子集树的典型。

重点关注左右子树剪枝的过程以及不同情况下的剪枝思路

5.3～5.9都看，其中5.5节、5.7节使用排列树框架为好（教材上用的是子集树框架）

可参照微助教中的课件“全排列简洁版”，看看排列树怎么编写回溯代码。

alt text

求解n后问题的非递归回溯算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Queens(int n)						//求解n皇后问题
{
	int i=1;							//i表示当前行,也表示放置第i个皇后
	q[i]=0;								//q[i]是当前列,从0列即开头试探  
	while (i>=1)						//重复试探
	{
		q[i]++;                         //数组下标为0的元素不用！从1开始遍历
		while (q[i]<=n && !place(i))	//试探一个位置(i,q[i])
			q[i]++;                     
		if (q[i]<=n)					//为第i个皇后找到了一个合适位置(i,q[i])
		{
			if (i==n)					//若放置了所有皇后,输出一个解
				dispasolution(n);
			else						//皇后没有放置完
			{
				i++;					//转向下一行,即开始下一个皇后的放置
				q[i]=0;					//每次放一个新皇后,都从该行的列头进行试探
			}
		}
		else i--;						//若第i个皇后找不到合适的位置,则回溯到上一个皇后
	}
}

每次放一个新皇后,都从该行的列头进行试探

每个皇后都要试探n列，其解空间是一个子集树，每个节点都可能有n棵子树，时间复杂度是O(n^n)

5.7 任务分配问题需要重点关注

第四章的任务分配采用蛮力法，求出所有分配方案的全排列，再选择成本最低的方案

本章使用回溯法来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//问题表示
int n=4;
int c[MAXN][MAXN]={{0}, {0,9,2,7,8},{0,6,4,3,7},{0,5,8,1,8},{0,7,6,9,4} };	//下标0的元素不用
//求解结果表示
int x[MAXN];					//临时解
int cost=0;						//临时解的成本
int bestx[MAXN];				//最优解
int mincost=INF;				//最优解的成本
bool worker[MAXN];				//worker[j]表示任务j是否已经分配人员
void dfs(int i)					//为第i个人员分配任务
{
	if (i>n)					//到达叶子结点
	{
		if (cost<mincost)		//比较求最优解
		{
			mincost=cost;
			for (int j=1;j<=n;j++)
				bestx[j]=x[j];
		}
	}
	else
	{
		for (int j=1;j<=n;j++)			//为人员i试探任务j:1到n
			if (!worker[j])				//若任务j还没有分配
			{
				worker[j]=true;
				x[i]=j;					//任务j分配给人员i
				cost+=c[i][j];
				dfs(i+1);				//为人员i+1分配任务
				worker[j]=false;		//回退
				x[i]=0;                 //人员i恢复原来的状态
				cost-=c[i][j];
			}
	}
}

算法分析：每个人员试探1-n个任务，对应的解空间是一个n叉树时间，复杂度为O（n^n）

【第五章回溯法总结】

回溯法在解空间树中按照深度优先的策略来拓展节点

回溯法需要借助栈这种数据结构来保存从根节点到当前拓展节点的路径

是一种通用解题法

既带有系统性，也带有跳跃性的搜索算法

回溯法的效率不依赖于确定解空间的时间

第6章分枝限界法

6.1分枝限界法概述

6.1.1什么是分枝限界法

在本节第2段提到，所谓“分枝”，就是采用广度优先策略搜索解空间树,这是与回溯法的主要区别，其它的区别都是间接来自这一点。

回溯法搜索方式是深度优先

回溯法的目标是找出所有解，分枝限界法的目标是找到最优解

分枝限界法依靠的数据结构是队列和优先队列

6.1.2分枝限界法的设计思想

数据结构课里面，广度优先搜索（树的层次遍历）借助队列实现。本节不看也可以。

感觉和A*有点像呢

确定合适的限界函数

组织待处理节点的活结点表

如何确定解向量的各个分量

6.1.3分枝限界法的时间性能

它的剪枝数量不定，因此速度与回溯法无法理论比较，要借助实验。用大O表示法，它们的都与解空间树结点数相关，在剪枝数目难以确定的情况下，都是按满二叉树计算的。

由于入队的结点，相互之间没有办法保存相互间的父子关系，分限法经常需要在每个结点中记录当前的解；回溯法是按深度优先搜索的，搜索的顺序就是沿着父—子”路径的，因此通常只用一个数组，保留一个当前的解，在搜索的过程中，根据父子关系的变化，动态地修改该数组即可。在看0—1背包分限法是，体会这一段文字，看看它的代码中队列结点的结构题类型中有一个int x[MAXN]数组。

因此，从理论上得到的复杂度，分限法往往比回溯法高

6.2求解0/1背包问题

通读掌握，非常典型。

队列和优先队列两种分枝限界法

队列：先进先出

采用队列式分枝限界法，对于每个节点求解上界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 计算分枝结点e的上界
void bound(NodeType &e)			
{
	int i=e.i+1;                //考虑e节点的余下物品
	int sumw=e.w;               //已经装入的总重量
	double sumv=e.v;            //已经装入的总价值
	while ((sumw+w[i]<=W) && i<=n)
	{	sumw+=w[i];				//计算背包已装入载重
		sumv+=v[i];				//计算背包已装入价值
		i++;
	}
	if (i<=n)	               //余下物品只能部分装入
		e.ub=sumv+(W-sumw)*v[i]/w[i];
	else                        //走到这里表示到了叶子节点，说明余下物品可以全部装入
		e.ub=sumv;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 求0/1背包的最优解
void bfs()							
{
	int j;
	NodeType e,e1,e2;				//定义3个结点
	queue<NodeType> qu;				//定义一个队列
	e.i=0;							//根结点置初值，其层次计为0
	e.w=0; e.v=0;
	e.no=total++; 
	for (j=1;j<=n;j++)
		e.x[j]=0;                   //e.x是解向量，初始化为全0
	bound(e);						//求根结点的上界
	qu.push(e);						//根结点进队
	while (!qu.empty())				//队不空循环,注意循环的条件是队列不为空，叶子节点需要出队列才能算，进队列不算结束，这里和A*是一样的
	{
		e=qu.front(); qu.pop();		//出队结点e
		printf("出队");dispnode(e);
		if (e.w+w[e.i+1]<=W)		//剪枝：检查左孩子结点
		{
			e1.no=total++; 
			e1.i=e.i+1;				//建立左孩子结点
			e1.w=e.w+w[e1.i];
			e1.v=e.v+v[e1.i];
			for (j=1;j<=n;j++)		//复制解向量
				e1.x[j]=e.x[j];
			e1.x[e1.i]=1;           //这一步表示选取当前节点的左孩子节点
			bound(e1);				//求左孩子结点的上界
			if (EnQueue(e1,qu))	    //左孩子结点进队操作
				printf("  左孩子进队");dispnode(e1);
		}
		e2.no=total++;				//建立右孩子结点
		e2.i=e.i+1;
		e2.w=e.w; e2.v=e.v;
		for (j=1;j<=n;j++)			//复制解向量
			e2.x[j]=e.x[j];
		e2.x[e2.i]=0;
		bound(e2);					//求右孩子结点的上界
		if (e2.ub>maxv)				//若右孩子结点可行,则进队,否则被剪枝
		{
			if (EnQueue(e2,qu))
				printf("  右孩子进队");dispnode(e2);
		}
		else
		{
			printf("  右孩子不进队");dispnode(e2);
		}
	}
}

采用优先队列式分枝限界

大根堆，按ub越大越先出队来进行计算

求解上界的函数不变

最坏的时间空间复杂度都为O(2^n)，n是物品的个数

6.3求解图的单源短路径

不典型，可不看。

6.4求解任务分配问题

需看懂。

需要涉及求解节点下界的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
void bound(NodeType &e)		//求结点e的限界值	
{
	int minsum=0;   
	for (int i1=e.i+1;i1<=n;i1++)	//求c[e.i+1..n]行中最小元素和  就是e节点（当前节点下面的节点）遍历
	{  
		int minc=INF;     
		for (int j1=1;j1<=n;j1++)   
			if (e.worker[j1]==false && c[i1][j1]<minc)   //先找到未分配的任务且该人员对应的任务成本是最小的
				minc=c[i1][j1];    //更新最小值
		minsum+=minc;   //将最小值求和
	}
	e.lb=e.cost+minsum;   //加上当前节点已经分配的任务需要的成本，得到将所有人员都理想分配任务的最小成本（实际成本一定会大于等于该最小成本）
}

6.5求解流水作业调度问题

问题本身比较复杂，弄清楚问题本身到底是什么意思即一些细节，要花不少时间，用来说明分限法并不好，不看。

第7章贪心算法

7.1贪心法概述

7.1.1什么是贪心法

本节并没有值得看的内容。

7.1.2用贪心法求解的问题应具有的性质

这2个性质非常重要。要结合7.2节的例子来理解，不然这段文字比较抽象，要形成一个自己的通俗的理解。这样才能举一反三。证明这2个性质，比具体算法的编码更重要

1、贪心选择性质

所求解的问题的整体最优解可以通过一系列的局部最优的选择（即贪心选择）来达到，每一步所做的贪心选择最终导致问题的整体最优解

数学归纳法

2、最优子结构性质

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质

反证法

7.1.3贪心法的一般求解过程

没用

7.2求解活动安排问题

简单、入门非常好

求解兼容活动最多的个数

将活动按结束时间递增排序

算法的时间主要花费在排序上，排序的时间复杂度为O（nlog2n）,整个算法的时间复杂度也是如此

7.3求解背包问题

典型需掌握

选择的贪心策略：选择单位重量下价值最大的物品，在价值与容量之间寻求平衡

需要根据单位价值递减排序然后依次选择

7.4求解装载问题

掌握

情景：不考虑集装箱的体积限制，只限制重量，要求尽可能多的集装箱

策略：采用贪心算法，优先选择重量轻的集装箱

对w从小到大进行排序

7.5求解田忌赛马问题

问题本身太复杂，不适合做贪心算法的示例，不看。

7.6求解多机调度问题

实际上只能得到近似解，不看。

7.7哈夫曼编码

掌握证明

前缀码的概念

每次都合并两棵根节点权值最小的二叉树，这体现出了贪心法的思想

带权路径长度和 WPL 等于权值乘以节点的路径长度再求和

具有最小带权路径长度和的树是哈夫曼树（最优树）

算法的证明：

贪心选择性质：构造一棵哈夫曼树的过程可以从合并两个权值最小的字符开始

满足最优子结构性质：该问题的最优解包含其子问题的最优解

7.8求解流水作业调度问题

问题本身太复杂，不适合做贪心算法的示例，不看。

第8章动态规划

8.1动态规划概述

8.1.1从求解斐波那契数列看动态规划法

通过斐波那契数列的计算，理解什么是重叠子问题，这个例子足够简单

8.1.2动态规划的原理

学握逆序解法

从后往前进行推理的算法

8.1.3动态规划求解的基本步骤

在本节开始部分提到了应用动态规划的3个性质，（1）（3）是主要的，应理解；性质（2）无后效性在一些其它教材里是没有的。除了刚开始的这一段关于性质的描述，后面文字的没 有用处。

（1）最优性原理：问题的最优解包含的子问题的解也是最优的，具有最优子结构，满足最优性原理

（2）无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关

（3）有重叠子问题：子问题之间不是独立的，一个子问题在下一个阶段被多次使用到

8.1.4动态规划与其他方法的比较

需要理解它

基本思想与分治法类似，但是分治法的各个子问题独立，dp的子问题重叠

dp又与贪心类似，

dp只有多项式的时间复杂度，效率较高

8.2求解整数拆分问题

掌握

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Split(int n,int k)		//求解算法
{
	for (int i=1;i<=n;i++)
		for(int j=1;j<=k;j++)
		{
			if (i==1 || j==1)
				dp[i][j]=1;
			else if (i<j)
				dp[i][j]=dp[i][i];
			else if (i==j)
				dp[i][j]=dp[i][j-1]+1;
			else
				dp[i][j]=dp[i][j-1]+dp[i-j][j];
		}
}

采用递归算法来实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int dpf(int n,int k)
{
	if (dp[n][k]!=0) return dp[n][k];   //这一步是递归dp的精髓
	if (n==1 || k==1)         //注意下面四种情况属于是并列式的，在一个节点只能出现一种情况，因此每种情况都需要设置 return 
	{
		dp[n][k]=1;
		return dp[n][k];
	}
	else if (n<k)
	{
		dp[n][k]=dpf(n,n);
		return dp[n][k];
	}
	else if (n==k)
	{
		dp[n][k]=dpf(n,k-1)+1;
		return dp[n][k];
	}
	else
	{
		dp[n][k]=dpf(n,k-1)+dpf(n-k,k);
		return dp[n][k];
	}
}

这种方式也叫备忘录的方式

8.3求解连续子序列和问题

不看

8.4求解三角形小路径问题

看

8.5求解长公共子序列问题

掌握

8.6求解长递增子序列问题

不看

8.7求解编辑距离问题

不看

8.8求解0/1背包问题

掌握

8.9求解完全背包问题

不看

8.10求解资源分配问题

不看

8.11求解会议安排问题

不看

8.12滚动数组

看

滚动数组：压缩存储空间，使用求模的方式来实现

第11章计算复杂性理论简介

11.1计算模型

11.1.1求解问题的分类

本节的概念比较清晰，在最后一句提到了需要关于图灵机的概念。现代计算机可抽象成图灵机，因此我们就按照现代计算机去理解就行，不用研究图灵机模型

11.1.2图灵机模型

不看

11.2P类和NP类问题

掌握

用确定性图灵机用多项式时间界可以解决的问题称为P类问题

用非确定性图灵机以多项式时间界可解的问题称为NP类问题，N表示非确定性

P类问题属于NP类问题的一个子集

11.3 NPC问题

证明不看，只掌握文字性的描述

TSP问题是NPC问题

题型

一选择题（共10分，每空2分）

第1、3、5、7、8章各一题

二判断题（共5分、5题）

第6章2题，第5、8、11章各一题

三、程序填空题（共20分，10空）

第3、4章各一题

四、算法过程分析（共32分、2题

第6、8章各一题

五、算法复杂度分析（共24分、2题

第5、8章各一题

回溯法：解空间为子集树O(2^n)，解空间为派列树O(n!)

六、证明一个问题适用贪心算法（9分）

注：有10分左右，它待解的问题，并不是书上或作业上练过的问题

结合微助教上面的作业，以及“课件”下面的各章“学习”要点复习。

算法优化
算法分析与设计期末复习
http://jrhu0048.github.io/2024/06/18/suan-fa-fen-xi-yu-she-ji-qi-mo-fu-xi/
作者
JR.HU
发布于
2024年6月18日
更新于
2024年10月15日
许可协议