算法设计与分析 第七章符号串

《算法设计与分析》复习提纲一、基本概念1.算法设计与分析的基本概念和目标2.时间复杂度和空间复杂度的定义及其分析方法3.渐进符号的含义和应用4.最坏情况、平均情况和最好情况的分析方法二、排序算法1.冒泡排序、插入排序和选择排序的原理、特点和时间复杂度2.归并排序和快速排序的原理、特点和时间复杂度3.堆排序和基数排序的原理、特点和时间复杂度4.对各种排序算法的时间复杂度进行比较和分析5.排序算法的稳定性及其应用三、查找算法1.顺序查找和二分查找的原理、特点和时间复杂度2.哈希查找的原理、特点和时间复杂度3.查找算法的性能比较和选择4.查找算法在实际问题中的应用四、图算法1.图的基本概念和表示方法2.图的遍历算法：深度优先和广度优先的原理、特点和应用3. 最短路径算法：Dijkstra算法和Floyd算法的原理、特点和时间复杂度4. 最小生成树算法：Prim算法和Kruskal算法的原理、特点和时间复杂度5.图的应用：拓扑排序、关键路径和网络流问题五、动态规划算法1.动态规划算法的基本思想和特点2.最优子结构、重叠子问题和状态转移方程的定义和应用3.0-1背包问题和最长公共子序列问题的动态规划算法4.动态规划算法的时间复杂度分析和优化方法5.动态规划算法在实际问题中的应用六、贪心算法1.贪心算法的基本思想和特点2.哈夫曼编码和活动选择问题的贪心算法3.贪心算法的正确性证明和近似算法的设计4.贪心算法在实际问题中的应用七、分治算法1.分治算法的基本思想和特点2.快速排序和归并排序的分治算法3.分治算法在实际问题中的应用八、回溯算法1.回溯算法的基本思想和特点2.八皇后问题和0-1背包问题的回溯算法3.回溯算法的剪枝策略和性能优化4.回溯算法在实际问题中的应用九、随机化算法1.随机化算法的基本思想和特点2.蒙特卡罗算法和拉斯维加斯算法的原理和特点3.随机化算法在实际问题中的应用十、算法设计技巧1.分解复杂问题、找出递归公式和设计递归算法2.利用递归和迭代进行算法设计和分析3.利用动态规划、贪心算法和分治算法进行算法设计和分析4.利用回溯算法和随机化算法进行算法设计和分析5.开发和应用合适的数据结构进行算法设计和分析以上是《算法设计与分析》复习提纲的内容，涵盖了该课程的基本概念、排序算法、查找算法、图算法、动态规划算法、贪心算法、分治算法、回溯算法、随机化算法以及算法设计技巧等内容。

【程序7-1】多段图的向前递推算法template<class T>T Graph<T>::FMultiGraph(int k, int *p){//采用程序6-8的邻接表存储图GTc,*cost=new float[n]; int q, *d=new int[n];cost[n-1]=0, d[n-1]= -1; //设置向前递推的初值for (int j=n-2; j>=0; j--){ //按n-2, …, 0的次序计算cost和d float min=INFTY; //按式（7-1）计算最小值为cost[j]for (ENode<T> *r=a[j]; r; r=r->nextArc) {int v=r->adjVex;if (r->w+cost[v]<min) {min=r->w+cost[v];q=v;}}cost[j]=min; d[j]=q; //q是j在最短子路径上的后继结点}p[0]=0; p[k-1]=n-1; c=cost[0]; //p[0]和p[n-1]是源点和汇点for(j=1; j<=k-2; j++) p[j]=d[p[j-1]]; //p[i]是最短路径上第i阶段的结点delete []cost; delete []d; return c;}【程序7-2】弗洛伊德算法template<class T>void MGraph<T>::Floyd(T**& d, int **& path){int i, j, k;d= new T*[n]; path=new int *[n];for(i=0; i<n; i++){d[i]=new T [n]; path[i]=new int[n];for (j=0; j<n; j++){ //初始化d[i][j]=a[i][j];if (i！=j && w[i][j]<INFTY) path[i][j]=i;else path[i][j]= -1;}}for (k=0; k<n; k++) //考察结点kfor (i=0; i<n; i++)for (j=0; j<n; j++)·135·if (d[i][k]+d[k][j] < d[i][j] ){d[i][j]=d[i][k]+d[k][j];path[i][j]=path[k][j];}}【程序7-3】矩阵连乘算法class MatrixChain{public:MatrixChain(int mSize, int *q); //创建二维数组m和s，一维数组p，并初始化int MChain(); //一般动态规划法求最优解值int LookupChain(); //备忘录方法求最优解值（程序7-4）void Traceback(); //构造最优解的公有函数……private:void Traceback(int i, int j); //构造最优解的私有递归函数int LookupChain(int i, int j); //备忘录方法私有递归（程序7-4）int *p, **m, **s, n;};int MatrixChain::MChain(){ //求A[0:n-1]的最优解值for (int i=0;i<n; i++) m[i][i]=0;for (int r=2; r<=n; r++)for (int i=0; i<=n-r; i++) {int j=i+r-1;m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; //m[i][j] 的初值s[i][j]=i;for (int k=i+1; k<j; k++) {int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];if (t<m[i][j]) {m[i][j]=t; s[i][j]=k;}}}return m[0][n-1];}void MatrixChain::Traceback(int i, int j){if(i==j) { cout<<'A'<<i; return;}·136·if (i<s[i][j]) cout<<'('; Traceback(i, s[i][j]); if (i<s[i][j])cout<<')';if(s[i][j]+1<j)cout<<'('; Traceback(s[i][j]+1, j); if(s[i][j]+1<j) cout<<')';}void MatrixChain::Traceback(){cout<<'('; Traceback(0, n-1); cout<<')';cout<<endl;}【程序7-4】矩阵连乘的备忘录方法int MatrixChain::LookupChain(int i, int j){if (m[i][j]>0) return m[i][j]; //子问题已经求解，直接引用if(i==j) return 0; //单一矩阵无须计算int u=LookupChain(i+1, j)+p[i]*p[i+1]*p[j+1]; //按式（7-9）求最小值s[i][j]=i;for (int k=i+1; k<j; k++) {int t=LookupChain(i, k)+LookupChain(k+1, j)+p[i]*p[k+1]*p[j+1];if (t<u) {u=t; s[i][j]=k;}}m[i][j]=u; return u; //保存并返回子最优解值}int MatrixChain::LookupChain(){return LookupChain(0, n-1); //返回A[0:n-1]的最优解值}·137·【程序7-5】求LCS的长度class LCS{public:LCS(int nx, int ny, char *x, char*y); //创建二维数组c、s和一维数组a、b，并进行初始化void LCSLength(); //求最优解值（最长公共子序列长度）void CLCS(); //构造最优解（最长公共子序列）……private:void CLCS(int i, int j);int **c, **s.m, n;char *a, *b;};int LCS::LCSLength()·138·for(int i=1; i<=m; i++) c[i][0]=0;for(i=1; i<=n; i++) c[0][i]=0;for (i=1; i<=m; i++)for (int j=1; j<=n; j++)if (x[i]==y[j]){c[i][j]=c[i-1][j-1]+1; s[i][j]=1; //由c[i-1][j-1]计算c[i][j]}else if (c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j]; s[i][j]=2; //由c[i-1][j]得到c[i][j]}else {c[i][j]=c[i][j-1]; s[i][j]=3; //由c[i][j-1]得到c[i][j]}return c[m][n]; //返回最优解值}【程序7-6】构造最长公共子序列void LCS::CLCS(int i, int j){if (i==0||j==0) return;if (s[i][j]==1){CLCS(i-1, j-1);cout<<a[i];}else if (s[i][j]==2) CLCS(i-1, j);else CLCS(i, j-1);}【程序7-7】构造最优二叉搜索树int Find(int i, int j, int **r, float**c){float min=INFTY; int k;for (int m=i+1; m<=j; m++)if ((c[i][m-1]+c[m][j])<min) {min=c[i][m-1]+c[m][j]; k=m;}return k;}void CreateOBST(float* p, float* q, float **c, int **r, float**w, int n)·139·for (int i=0; i<=n-1; i++) { //初始化w[i][i]=q[i]; c[i][i]=0.0; r[i][i]=0;w[i][i+1]=q[i]+q[i+1]+p[i+1];c[i][i+1]=q[i]+q[i+1]+p[i+1];r[i][i+1]=i+1;}w[n][n]=q[n]; c[n][n]=0.0; r[n][n]=0;for (int m=2; m<=n; m++) //计算n-2条对角线元素for (i=0; i<=n-m; i++) {int j=i+m;w[i][j]=w[i][j-1]+p[j]+q[j];int k = Find(i, j, r, c);c[i][j] = w[i][j] + c[i][k-1] + c[k][j];r[i][j] = k;}}【程序7-8】0/1背包的递归算法template<class T>class Knapsack{public:Knapsack(int mSize, float cap, float *wei, T *prof);T RKnap();private:T f(int j, float X);float m, *w;T *p;int n;};template<class T>T Knapsack<T>::f(int j, float X){if (j<0) return ((X<0) ？-INFTY: 0);if (X<w[j]) return f(j-1, X);else {T a=f(j-1, X);T b=f(j-1, X-w[j])+p[j];if(a>b)return a; else return b;}·140··141·template<class T> T Knapsack<T>:: RKnap() { if(n>0) return f(n -1, m); else return NoAns;//NoAns 可定义为类型T 的一个代表无收益的常量}【程序7-9】 0/1背包算法的粗略描述void DKP(float *p, float *w, int n, float M, float &P, int *x) {S -1={(0, 0)};for (i =0; i <n -1; i ++){1i S ={(X , P )|(X -w i , P -p i )∈S i -1 and X M }; S i =MergerPurge(S i -1,1i S );//合并两集合，并从中舍弃应去除的阶跃点}(X 1, P 1)=S n -2中最后一个阶跃点;(X 2, P 2)=(X +w n -1, P +p n -1)，其中(X , P )是S n -1中使得X +w n -1≤M 的最大的阶跃点; P =max{P 1, P 2};//P 为最优解值If (P 2＞P 1) x n -1=1;else x n -1=0;回溯确定x n -2, x n -3, …, x 0; }【程序7-10】 0/1背包最优解值算法struct XP {float X, P; };template<class T> class Knapsack { public:Knapsack(int sz, float cap, float *wei, T *prof); T DKnap(int *x); …… private:T DKnap();void TraceBack(int*x);int Largest(int low, int high, int i); float m, *w;·142·XP *p; T *pf; int n, *b; };template<class T>int Knapsack<T>::Largest(int low, int high, int i) { int u=low-1;for (int j=low; j<=high; j++){ float ww=p[j].X+w[i];if(ww<=m) u=j;}return u;}template<class T>T Knapsack<T>:: DKnap() { float ww, pp; int next; b[0]=0;p[0].X=p[0].P=0.0; p[1].X=w[0]; p[1].P=pf[0]; //S 0int low=0, high=1; //S 0的起止位置b[1]=next=2;//数组p 的下一个空闲位置 for (int i=1; i<=n -1; i++) {//由S i -1产生S iint k=low;int u=Largest(low, high, i); for (int j=low; j<=u; j++) {//从S i -1生成1i S ，并合并成S i ww=p[j].X+w[i]; pp=p[j].P+pf[i];//生成1i S 中的一个阶跃点(ww, pp) while ((k<=high) && (p[k].X<ww)) {//复制S i -1中的部分阶跃点到S i 中p[next].X=p[k].X; p[next++].P=p[k++].P;}if (k<=high && p[k].X==ww) if (pp<p[k].P) pp=p[k++].P;if (pp>p[next -1].P) {//若(ww, pp)不被支配，则加入S i 中p[next].X=ww; p[next++].P=pp;}while (k<=high && p[k].P<=p[next -1].P) k++; //舍弃所有被支配的阶跃点 }while (k<=high){//复制S i -1中剩余阶跃点到S i 中p[next].X=p[k].X; p[next++].P=p[k++].P;}low=high+1; high=next-1; b[i+1]=next;//S i +1的初始化}return p[next-1].P ; //返回最大收益}【程序7-11】0/1背包最优解算法template<class T>void Knapsack<T>:: TraceBack(int*x ){float ww=p[b[n] -1].X;for (int j=n-1; j>0; j--){x[j]=1;for (int k=b[j-1]; k<b[j]; k++)if(ww==p[k].X) x[j]=0;if(x[j]) ww=ww-w[j];}if(ww==0) x[0]=0; else x[0]=1;}【程序7－12】Johnson算法struct Triplet{ //三元组结构int operator <(Triplet b)const { return t<b.t;}int jobNo,t,ab; //jobNo为作业号，t为处理时间，ab为设备号};void FlowShop(int n, int *a,int *b,int *c){Triplet d[mSize]={{0,0,0}};for(int i=0;i<n;i++) //算法步骤（1）生成三元组表dif(a[i]<b[i]) {d[i].jobNo=i;d[i].ab=0;d[i].t=a[i];}else {d[i].jobNo=i;d[i].ab=1;d[i].t=b[i];}Sort(d,n); //算法步骤（2），任意排序算法int left=0,right=n-1;for (i=0;i<n;i++) //算法步骤（3），生成最优解if(d[i].ab==0) c[left++]=d[i].jobNo;else c[right--]=d[i].jobNo;}·143·。

第一章算法概述1、算法的五个性质：有穷性、确定性、能行性、输入、输出。

2、算法的复杂性取决于：(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法本身的设计(A)，C=F(N,I,A。

3、算法的时间复杂度的上界，下界，同阶，低阶的表示。

4、常用算法的设计技术：分治法、动态规划法、贪心法、回溯法和分支界限法。

5、常用的几种数据结构：线性表、树、图。

第二章递归与分治1、递归算法的思想：将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。

递归的时间复杂性可归结为递归方程：1 11= 1T(n) <aT(n—b) + D(n) n> 1其中，a是子问题的个数，b是递减的步长，~表示递减方式，D(n)是合成子问题的开销。

递归元的递减方式~有两种：1、减法，即n -b，的形式。

2、除法，即n / b，的形式。

2、D(n)为常数c：这时，T(n) = 0(n P)。

D(n)为线形函数cn：r O(n) 当a. < b(NT(n) = < Ofnlog^n) "n = blljI O(I1P)二"A bl吋其中.p = log b a oD(n)为幕函数n x：r O(n x) 当a< D(b)II JT{ii) = O(ni1og b n) 'ia = D(b)ll].O(nr)D(b)lHJI：中，p= log b ao考虑下列递归方程：T(1) = 1⑴ T( n) = 4T(n/2) +n⑵ T(n) = 4T(n/2)+n2⑶ T(n) = 4T(n/2)+n3解：方程中均为a = 4，b = 2，其齐次解为n2。

对⑴，T a > b (D(n) = n) /• T(n) = 0(n);对⑵，•/ a = b2 (D(n) = n2) T(n) = O(n2iog n);对⑶，•/ a < b3(D(n) = n3) - T(n) = 0(n3)；证明一个算法的正确性需要证明两点：1、算法的部分正确性。

算法分析与设计教程习题解答第1章 算法引论1. 解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。

频率计数是指计算机执行程序中的某一条语句的执行次数。

多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。

指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。

2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。

3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。

4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。

5. 解：①n=11； ②n=12； ③n=982； ④n=39。

第2章 递归算法与分治算法1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。

2． 解：通过分治算法的一般设计步骤进行说明。

3． 解：int fibonacci(int n) {if(n<=1) return 1;return fibonacci(n-1)+fibonacci(n-2); }4. 解：void hanoi(int n,int a,int b,int c) {if(n>0) {hanoi(n-1,a,c,b); move(a,b);hanoi(n-1,c,b,a); } } 5. 解：①22*2)(−−=n n f n② )log *()(n n n f O =6． 解：算法略。

算法设计与分析复习知识点算法设计与分析是计算机科学中的重要概念，它涉及到各种问题的解决方法和效率分析。

在本文中，我将回顾一些算法设计与分析的核心知识点。

一、算法的基本概念1. 算法的定义：算法是一系列明确指定的步骤，用于解决特定问题或执行特定任务。

2. 算法的特性：输入、输出、确定性、可行性和有穷性。

3. 算法的效率：时间复杂度和空间复杂度是衡量算法效率的两个重要指标。

4. 算法的分类：常见的算法分类有分治法、贪心法、动态规划、回溯法等。

二、时间复杂度和空间复杂度1. 时间复杂度：描述算法的时间耗费，通常使用大O符号表示。

常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)、O(n^2)等。

2. 空间复杂度：描述算法在执行过程中所需的额外空间，也使用大O符号表示。

常见的空间复杂度有O(1)、O(n)、O(n^2)等。

三、常见的算法思想和技巧1. 分治法：将一个大问题划分成若干个小问题，然后逐个解决，并将结果合并得到最终解。

2. 贪心法：在每一步选择中都采取当前状态下最好或最优的选择，从而希望能得到全局最优解。

3. 动态规划：将一个大问题分解成若干个子问题，通过求解子问题得到最优解，从而得到原问题的解。

4. 回溯法：通过不断地尝试所有可能的选择，然后进行回溯，找到问题的解。

四、常见算法的应用1. 排序算法：快速排序、归并排序、插入排序等。

2. 搜索算法：深度优先搜索、广度优先搜索、A*算法等。

3. 图算法：最短路径算法、最小生成树算法、拓扑排序等。

4. 字符串匹配算法：暴力匹配算法、KMP算法、Boyer-Moore算法等。

五、算法复杂度分析1. 最优复杂度：最好情况下算法执行所需的最小资源。

2. 平均复杂度：在所有输入情况下算法执行所需的资源的平均值。

3. 最坏复杂度：最坏情况下算法执行所需的最大资源。

六、常见问题和优化技巧1. 递归算法的优化：尾递归优化、记忆化搜索等。

第一章什么是算法算法是解决一个计算问题的一系列计算步骤有序、合理的排列。

对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。

算法的三个要素1）.数据: 运算序列中作为运算对象和结果的数据.2）.运算: 运算序列中的各种运算:赋值,算术和逻辑运算3）.控制和转移: 运算序列中的控制和转移.算法分类从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本运算为逻辑运算.从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法算法的五个重要的特性（1）有穷性：在有穷步之后结束。

（2）确定性：无二义性。

（3）可行性：可通过基本运算有限次执行来实现。

（4）有输入表示存在数据处理（5）伪代码有输出程序设计语言（PDL），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。

特点：1）使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征；2）以自然语言的自由语法描述了处理过程；3）数据声明应该既包括简单的也包括复杂的数据结构；4）使用支持各种模式的接口描述的子程序定义或者调用技术。

求两个n 阶方阵的相加C=A+B 的算法如下，分析其时间复杂度。

#define MAX20n1n1n1n1ii1nn 1 n* 2 n n O(1) O( 1) O(i)i 0 j 0i0i0nnn j 1 j 1NO(i)NO( i)O(N(N21)) O(N2)i1i12赋值，比较，算术运算，逻辑运算，读写单个变量（常量）只需1单位时间2）. 执行条件语句if c then S1 else S2 的时间为TC +max(TS1,TS2).3）. 选择语句case A of a1: s1；a2: s2；...；am: sm 需要的时间为max（TS1,TS2 ,..., TSm）. 4）. 访问数组的单个分量或纪录的单个域需要一个单位时间.5）. 执行for 循环语句的时间=执行循环体时间* 循环次数.6）. while c do s （repeat s until c）语句时间=（Tc+Ts）*循环次数.7）. 用goto 从循环体内跳到循环体末或循环后面的语句时,不需额外时间8）. 过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7 进行分析；对递归调用，可建立关于T（n）的递归方程,求解该方程得到T（n）.插入排序算法的实现要点：（1）【参数和返回值】确定输入数据个数和数据类型，输出个数和数据类型，数据的组织形式（即逻辑结构：线性表、树、图，线性表还包括栈、队列），数据的存储格式（数组还是链表），函数返回值。

【程序7-1】多段图的向前递推算法template<class T>T Graph<T>::FMultiGraph(int k, int *p){//采用程序6-8的邻接表存储图GTc,*cost=new float[n]; int q, *d=new int[n];cost[n-1]=0, d[n-1]= -1; //设置向前递推的初值for (int j=n-2; j>=0; j--){ //按n-2, …, 0的次序计算cost和d float min=INFTY; //按式（7-1）计算最小值为cost[j]for (ENode<T> *r=a[j]; r; r=r->nextArc) {int v=r->adjVex;if (r->w+cost[v]<min) {min=r->w+cost[v];q=v;}}cost[j]=min; d[j]=q; //q是j在最短子路径上的后继结点}p[0]=0; p[k-1]=n-1; c=cost[0]; //p[0]和p[n-1]是源点和汇点for(j=1; j<=k-2; j++) p[j]=d[p[j-1]]; //p[i]是最短路径上第i阶段的结点delete []cost; delete []d; return c;}【程序7-2】弗洛伊德算法template<class T>void MGraph<T>::Floyd(T**& d, int **& path){int i, j, k;d= new T*[n]; path=new int *[n];for(i=0; i<n; i++){d[i]=new T [n]; path[i]=new int[n];for (j=0; j<n; j++){ //初始化d[i][j]=a[i][j];if (i！=j && w[i][j]<INFTY) path[i][j]=i;else path[i][j]= -1;}}for (k=0; k<n; k++) //考察结点kfor (i=0; i<n; i++)for (j=0; j<n; j++)·135·if (d[i][k]+d[k][j] < d[i][j] ){d[i][j]=d[i][k]+d[k][j];path[i][j]=path[k][j];}}【程序7-3】矩阵连乘算法class MatrixChain{public:MatrixChain(int mSize, int *q); //创建二维数组m和s，一维数组p，并初始化int MChain(); //一般动态规划法求最优解值int LookupChain(); //备忘录方法求最优解值（程序7-4）void Traceback(); //构造最优解的公有函数……private:void Traceback(int i, int j); //构造最优解的私有递归函数int LookupChain(int i, int j); //备忘录方法私有递归（程序7-4）int *p, **m, **s, n;};int MatrixChain::MChain(){ //求A[0:n-1]的最优解值for (int i=0;i<n; i++) m[i][i]=0;for (int r=2; r<=n; r++)for (int i=0; i<=n-r; i++) {int j=i+r-1;m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; //m[i][j] 的初值s[i][j]=i;for (int k=i+1; k<j; k++) {int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];if (t<m[i][j]) {m[i][j]=t; s[i][j]=k;}}}return m[0][n-1];}void MatrixChain::Traceback(int i, int j){if(i==j) { cout<<'A'<<i; return;}·136·if (i<s[i][j]) cout<<'('; Traceback(i, s[i][j]); if (i<s[i][j])cout<<')';if(s[i][j]+1<j)cout<<'('; Traceback(s[i][j]+1, j); if(s[i][j]+1<j) cout<<')';}void MatrixChain::Traceback(){cout<<'('; Traceback(0, n-1); cout<<')';cout<<endl;}【程序7-4】矩阵连乘的备忘录方法int MatrixChain::LookupChain(int i, int j){if (m[i][j]>0) return m[i][j]; //子问题已经求解，直接引用if(i==j) return 0; //单一矩阵无须计算int u=LookupChain(i+1, j)+p[i]*p[i+1]*p[j+1]; //按式（7-9）求最小值s[i][j]=i;for (int k=i+1; k<j; k++) {int t=LookupChain(i, k)+LookupChain(k+1, j)+p[i]*p[k+1]*p[j+1];if (t<u) {u=t; s[i][j]=k;}}m[i][j]=u; return u; //保存并返回子最优解值}int MatrixChain::LookupChain(){return LookupChain(0, n-1); //返回A[0:n-1]的最优解值}·137·【程序7-5】求LCS的长度class LCS{public:LCS(int nx, int ny, char *x, char*y); //创建二维数组c、s和一维数组a、b，并进行初始化void LCSLength(); //求最优解值（最长公共子序列长度）void CLCS(); //构造最优解（最长公共子序列）……private:void CLCS(int i, int j);int **c, **s.m, n;char *a, *b;};int LCS::LCSLength()·138·for(int i=1; i<=m; i++) c[i][0]=0;for(i=1; i<=n; i++) c[0][i]=0;for (i=1; i<=m; i++)for (int j=1; j<=n; j++)if (x[i]==y[j]){c[i][j]=c[i-1][j-1]+1; s[i][j]=1; //由c[i-1][j-1]计算c[i][j]}else if (c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j]; s[i][j]=2; //由c[i-1][j]得到c[i][j]}else {c[i][j]=c[i][j-1]; s[i][j]=3; //由c[i][j-1]得到c[i][j]}return c[m][n]; //返回最优解值}【程序7-6】构造最长公共子序列void LCS::CLCS(int i, int j){if (i==0||j==0) return;if (s[i][j]==1){CLCS(i-1, j-1);cout<<a[i];}else if (s[i][j]==2) CLCS(i-1, j);else CLCS(i, j-1);}【程序7-7】构造最优二叉搜索树int Find(int i, int j, int **r, float**c){float min=INFTY; int k;for (int m=i+1; m<=j; m++)if ((c[i][m-1]+c[m][j])<min) {min=c[i][m-1]+c[m][j]; k=m;}return k;}void CreateOBST(float* p, float* q, float **c, int **r, float**w, int n)·139·for (int i=0; i<=n-1; i++) { //初始化w[i][i]=q[i]; c[i][i]=0.0; r[i][i]=0;w[i][i+1]=q[i]+q[i+1]+p[i+1];c[i][i+1]=q[i]+q[i+1]+p[i+1];r[i][i+1]=i+1;}w[n][n]=q[n]; c[n][n]=0.0; r[n][n]=0;for (int m=2; m<=n; m++) //计算n-2条对角线元素for (i=0; i<=n-m; i++) {int j=i+m;w[i][j]=w[i][j-1]+p[j]+q[j];int k = Find(i, j, r, c);c[i][j] = w[i][j] + c[i][k-1] + c[k][j];r[i][j] = k;}}【程序7-8】0/1背包的递归算法template<class T>class Knapsack{public:Knapsack(int mSize, float cap, float *wei, T *prof);T RKnap();private:T f(int j, float X);float m, *w;T *p;int n;};template<class T>T Knapsack<T>::f(int j, float X){if (j<0) return ((X<0) ？-INFTY: 0);if (X<w[j]) return f(j-1, X);else {T a=f(j-1, X);T b=f(j-1, X-w[j])+p[j];if(a>b)return a; else return b;}·140··141·template<class T> T Knapsack<T>:: RKnap() { if(n>0) return f(n -1, m); else return NoAns;//NoAns 可定义为类型T 的一个代表无收益的常量}【程序7-9】 0/1背包算法的粗略描述void DKP(float *p, float *w, int n, float M, float &P, int *x) {S -1={(0, 0)};for (i =0; i <n -1; i ++){1i S ={(X , P )|(X -w i , P -p i )∈S i -1 and X M }; S i =MergerPurge(S i -1,1i S );//合并两集合，并从中舍弃应去除的阶跃点}(X 1, P 1)=S n -2中最后一个阶跃点;(X 2, P 2)=(X +w n -1, P +p n -1)，其中(X , P )是S n -1中使得X +w n -1≤M 的最大的阶跃点; P =max{P 1, P 2};//P 为最优解值If (P 2＞P 1) x n -1=1;else x n -1=0;回溯确定x n -2, x n -3, …, x 0; }【程序7-10】 0/1背包最优解值算法struct XP {float X, P; };template<class T> class Knapsack { public:Knapsack(int sz, float cap, float *wei, T *prof); T DKnap(int *x); …… private:T DKnap();void TraceBack(int*x);int Largest(int low, int high, int i); float m, *w;·142·XP *p; T *pf; int n, *b; };template<class T>int Knapsack<T>::Largest(int low, int high, int i) { int u=low-1;for (int j=low; j<=high; j++){ float ww=p[j].X+w[i];if(ww<=m) u=j;}return u;}template<class T>T Knapsack<T>:: DKnap() { float ww, pp; int next; b[0]=0;p[0].X=p[0].P=0.0; p[1].X=w[0]; p[1].P=pf[0]; //S 0int low=0, high=1; //S 0的起止位置b[1]=next=2;//数组p 的下一个空闲位置 for (int i=1; i<=n -1; i++) {//由S i -1产生S iint k=low;int u=Largest(low, high, i); for (int j=low; j<=u; j++) {//从S i -1生成1i S ，并合并成S i ww=p[j].X+w[i]; pp=p[j].P+pf[i];//生成1i S 中的一个阶跃点(ww, pp) while ((k<=high) && (p[k].X<ww)) {//复制S i -1中的部分阶跃点到S i 中p[next].X=p[k].X; p[next++].P=p[k++].P;}if (k<=high && p[k].X==ww) if (pp<p[k].P) pp=p[k++].P;if (pp>p[next -1].P) {//若(ww, pp)不被支配，则加入S i 中p[next].X=ww; p[next++].P=pp;}while (k<=high && p[k].P<=p[next -1].P) k++; //舍弃所有被支配的阶跃点 }while (k<=high){//复制S i -1中剩余阶跃点到S i 中p[next].X=p[k].X; p[next++].P=p[k++].P;}low=high+1; high=next-1; b[i+1]=next;//S i +1的初始化}return p[next-1].P ; //返回最大收益}【程序7-11】0/1背包最优解算法template<class T>void Knapsack<T>:: TraceBack(int*x ){float ww=p[b[n] -1].X;for (int j=n-1; j>0; j--){x[j]=1;for (int k=b[j-1]; k<b[j]; k++)if(ww==p[k].X) x[j]=0;if(x[j]) ww=ww-w[j];}if(ww==0) x[0]=0; else x[0]=1;}【程序7－12】Johnson算法struct Triplet{ //三元组结构int operator <(Triplet b)const { return t<b.t;}int jobNo,t,ab; //jobNo为作业号，t为处理时间，ab为设备号};void FlowShop(int n, int *a,int *b,int *c){Triplet d[mSize]={{0,0,0}};for(int i=0;i<n;i++) //算法步骤（1）生成三元组表dif(a[i]<b[i]) {d[i].jobNo=i;d[i].ab=0;d[i].t=a[i];}else {d[i].jobNo=i;d[i].ab=1;d[i].t=b[i];}Sort(d,n); //算法步骤（2），任意排序算法int left=0,right=n-1;for (i=0;i<n;i++) //算法步骤（3），生成最优解if(d[i].ab==0) c[left++]=d[i].jobNo;else c[right--]=d[i].jobNo;}·143·。

算法分析与设计基础知识在计算机科学领域中，算法是指为解决特定问题而设计的一系列明确步骤的集合。

算法分析与设计是计算机科学中的基础知识，它涉及到算法的性能、效率和可靠性等方面。

本文将介绍算法分析与设计的基础知识。

一、算法分析算法分析主要关注算法的效率和性能。

在设计算法时，我们通常要考虑以下几个因素：1. 时间复杂度时间复杂度是衡量算法执行时间的度量，通常用大O记法表示。

例如，如果一个算法的时间复杂度为O(n)，表示随着输入规模的增大，算法执行时间与输入规模成正比。

常见的时间复杂度有O(1)、O(logn)、O(n)、O(nlogn)和O(n^2)等。

2. 空间复杂度空间复杂度是衡量算法所需内存空间的度量。

它通常也用大O记法表示。

算法的空间复杂度主要由算法中使用的数据结构和变量所需的内存空间决定。

3. 最好、最坏和平均情况复杂度除了时间复杂度和空间复杂度，我们还需要考虑算法在不同情况下的效率。

最好情况复杂度是在最理想情况下的复杂度，最坏情况复杂度是在最不利情况下的复杂度，而平均情况复杂度是对所有可能情况下的复杂度进行平均。

二、算法设计算法设计是指根据问题的特性和需求，设计出解决问题的具体算法。

在设计算法时，我们常用到以下几种算法设计技术：1. 分而治之分而治之是一种将大问题分解成更小的子问题并逐个解决的方法。

通常通过递归或迭代实现。

这种方法可以降低问题复杂度，并且使得算法易于理解和实现。

2. 动态规划动态规划是一种通过将问题分解成相互重叠的子问题，并只解决一次子问题，从而避免重复计算的方法。

动态规划通常适用于那些可以通过最优子结构性质进行求解的问题。

3. 贪心算法贪心算法是一种通过每一步都选择当前状态下最优解，以希望最终达到全局最优解的方法。

贪心算法通常用于那些具有最优子结构性质的问题。

4. 回溯算法回溯算法是一种通过尝试所有可能的解并逐步搜索得到问题的解的方法。

它通常用于那些可以通过遍历搜索所有可能解空间的问题。