第2章 递归与分治策略
P11 例2-1阶乘函数
#include<stdio.h> #include<stdlib.h> int factorial(int n){ if(n>1) return n*factorial(n-1); else return 1; } int main(){ printf("输入数:"); int n=0; scanf("%d",&n); printf("阶乘为:%d",factorial(n)); }
P12 例2-2fibonacci函数
#include<stdio.h> #include<stdlib.h> int fibonacci(int n){ if(n<=1) return 1; else return fibonacci(n-1)+fibonacci(n-2); } int main(){ printf("输入数:"); int n=0; scanf("%d",&n); printf("fibonacci数为:%d\n",fibonacci(n)); }
P12 例2-3Ackerman函数
#include<stdio.h> #include<stdlib.h> int Ackerman(int n,int m){ if(n==1 && m==0) return 2; else if(n==0 && m>1) return 1; else if(n>=2 && m==0) return n+2; else if(n>=1 && m>=1) return Ackerman(Ackerman(n-1,m),m-1); } int main(){ printf("输入两个数:"); int n=0,m=0; scanf("%d %d",&n,&m); printf("Ackerman函数为:%d",Ackerman(n,m)); }
第3章 动态规划
P47 3.1矩阵连乘问题
void matrixMultiply(int **a,int **b,int **c,int ra,int ca,int rb,int cb){ if(ca!=rb)//前面的A矩阵的行数不等于后面的B矩阵的列数 error("矩阵不可乘"); for(int i=0;i<ra;i++){//i<行数ra for(int j=0;j<cb;j++){//j<列数cb int sum=a[i][0]*b[0][j];//先求新数组的第一个元素 for(int k=1;k<ca;k++) sum+=a[i][k]*b[k][j];//C矩阵的第i行第j列的元素等于A矩阵第i行中所有元素与B矩阵第j列中对应元素的乘积之和 c[i][j]=sum;//将sum赋值给相乘后的数组C的元素 } } }
P49 3.1.3计算最优值
//用动态规划算法解决，可依据其递推式以自底向上的方式进行计算 //在计算过程中，保存已解决的子问题答案，而在后面需要是只要简单查一下 //从而避免大量的重复计算，最终得到多项式时间的算法(时间复杂度小于等于n^2) void MatrixChain(int *p,int n,int **m,int **s){//输入参数存储在p数组，最优值数组m //s为一个n*n的二维整型数组，表示断开的位置(分为两个矩阵的断点处) for(int i=1;i<=n;i++) m[i][i]=0;//m为n*n的二维整型数组，表示每个子问题的最优值，即m[i][j]表示矩阵链Ai...j的最小乘次数。 for(int r=2;r<=n;r++){ for(int i=1;i<n-r+1;i++){ int j=i+r-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; //计算矩阵链m[i][j]的最小乘次数，同时记录断点位置s[i][j] for(int k=i+1;k<j;k++){//s[i][j]表示使得矩阵链Ai...j分为两个最小矩阵链之和，断开的位置k //当长度为k的左右两个矩阵链分别对应m[i][k]和m[k+1][j]时，计算得到当前断点下的乘运算次数t int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t<m[i][j]){//如果t比已知的最小值m[i][j]还小，则更新m[i][j](最优解)和s[i][j](最佳断点位置)的值 s[i][j]=k; } } } } }
P50 3.1.4构造最优解
void Traceback(int i,int j,int **s){//按算法MatrixChain计算出的断点矩阵s指示的加括号方式输出计算A[i:j]的最佳计算次序 if(i==j) return; Traceback(i,s[i][j],s); Traceback(s[i][j]+1,j,s); cout<<"Multiply A "<<i<<","<<s[i][j]; cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl; }//要输出A[1:n]的最优计算次序只要调用Traceback(1,n,s)即可
P51 3.2.2重叠子问题
//在用递归算法自顶向下解决问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算 //动态规划算法对每个子问题只解一次，然后将其解保存在一个表格中 //当再次需要解该问题时，只是简单地用常数时间查看一下结果 int RecurMatrixChain(int i,int j){ if(i==j)//检查是否只有一个矩阵 return 0; int u=RecurMatrixChain(i,j)+p[i-1]*p[i]*p[j];//计算当前的矩阵链的最小乘法运算次数 s[i][j]=i; for(int k=i+1;k<j;k++){ int t=RecurMatrixChain(i,k)+RecurMatrixChain(K+1,j)+p[i-1]*p[k]*p[j]; if(t<u){ u=t; s[i][j]=k; } } return u;//返回当前矩阵链的最小乘法运算次数u }
P53 3.2.3备忘录方法
//记忆化搜索优化的矩阵连乘动态规划算法 int MemoizedMatrixChain(int n,int **m,int **s){//m记录子问题的最优值，s为最优解的矩阵链 for(int i=1;i<=n;i++){ for(int j=i;i<=n;j++) m[i][j]=0;//对m[][]数组初始化 return LookupChain(1,n);//调用LookupChain函数，将1到n的矩阵链分解为子问题求解 } } int LookupChain(int i,int j){ if(m[i][j]>0)//判断是否已经求过子问题 return m[i][j];//如果是，则直接返回最优解 if(i==j)//只有一个矩阵 return 0; int u=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1;k<j;k++){//枚举中间断点k，将其分解为i到k和k+1到j两个子问题 int u=Lookup(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];//p[]数组存储了子矩阵的维度 if(t<u){ u=t;//记录最优值 s[i][j]=k;//记录最优值对应的断点 } } m[i][j]=u; return u; }
P55 3.3.2计算最优值
//求解最长公共子序列(LCS)的动态规划算法 void LCSLength(int m,int n,char *x,char *y,int **c,int **b){//m和n是两个字符串的长度 //c[][]是最长公共子序列长度，b[][]是最长公共子序列长度和两个字符串的匹配情况(1表示匹配，2表示取x字符，3表示取y字符) int i,j; for(i=1;i<=m;i++) c[i][0]=0; for(i=1;i<=n;i++) c[0][i]=0; //将第0行和第0列全部赋值为0，因为长度为0的字符串没有公共子序列 for(i=1;i<=m;i++){ for(k=1;j<=n;j++){ if(x[i-1]==y[i-1]){ c[i][j]=c[i-1][j-1]+1; b[i][j]=1;//最长公共子序列包含了这个字符 }//如果不相同，说明这两个字符不可能同时存在于最长公共子序列中，需要在x[0:i-2]和y[0:j-2]中寻找最长的公共子序列 //这时，可以比较c[i-1][j]和c[i][j-1]，将其较大值作为c[i][j]的值，并将对应的情况记录在b[i][j]中 else if(c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i-1][j]; b[i][j]=2; }//如果是c[i-1][j]大，则说明最长公共子序列不包含x[i-1]，因此b[i][j]为2，表示取x[i-1]字符 else{ c[i][j]=c[i][j-1]; b[i][j]=3; }//否则，最长公共子序列不包含y[j-1]，b[i][j]为3，表示取y[j-1]字符 } } }
P56 3.3.4构造最长公共子序列
//通过回溯记录的LCS最优路径，构造出最长公共子序列的函数 void LCS(int i,int j,char *x,int **b){//i和j分别表示两个字符串的末尾位置 if(i==0||j==0) return; if(b[i][j]==1){//当前字符匹配，属于最长公共子序列的一部分 LCS(i-1,j-1,x,b);//递归到b[i-1][j-1]，输出x[i-1]，即当前匹配的字符 cout<<x[i-1]; } else if(b[i][j]==2)//说明当前字符没有匹配在公共子序列中，需要递归到b[i-1][j] LCS(i-1,j,x,b);//即在第一个字符串中向前找到一个字符，与第二个字符串中的当前字符匹配 else//说明当前字符也没有匹配在公共子序列中，需要递归到b[i][j-1] LCS(i,j-1,x,b);//即在第二个字符串中向前找到一个字符，与第一个字符串中的当前字符匹配 }
P56 3.4.3最大子段和问题的动态规划算法
int MaxSum(int n,int *a){//利用Kadane算法求解最大子段和问题 int sum=0,b=0;//sum记录最大子段和 for(int i=1;i<=n;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; } return sum; }
P57 3.4.1最大子段和问题的改进算法
int MaxSum(int n,int *a,int& besti,int& bestj){//Kadane算法，将时间复杂度降到O(n^2) int sum=0; for(int i=1;i<=n;i++){ int thissum=0; //从第0个元素开始逐一遍历数组a，记录当前的最大子段和sum和当前的子段和thissum for(int j=i;j<=n;j++){ thissum+=a[j]; if(thissum>sum){//如果thissum比sum大 sum=thissum;//更新sum besti=i;//记录对应的起点besti(即i) bestj=j;//记录终点bestj(即j) } } } return sum; }
P57 3.4.1最大子段和问题的简单算法
int MaxSum(int n,int *a,int& besti,int& bestj){//暴力枚举，用于求解数组a中的最大子段和，算法的时间复杂度为O(n^3) int sum=0; for(int i=1;i<=n;i++){//遍历所有可能的起点i for(int j=i;j<=n;j++){//便利所有可能的终点j int thissum=0; for(int k=i;k<=j;k++)//遍历了i到j范围内所有元素，以求出i到j的子段和thissum thissum+=a[k]; if(thissum>sum){//如果thissum大于目前已经求出的最大子段和sum sum=thissum;//更新sum besti=j; bestj=j; //记录下对应的起点besti和终点bestj } } } return sum; }
P59 3.4.2最大子段和问题的分治算法
int MaxSubSum(int *a,int left,int right){//分治算法的实现求解最大子段和问题 int sum=0; if(left==right)//左left和右边界right相等 sum=a[left]>0?a[left]:0; else{ int center=(left+right)/2;//通过分治的方式不断缩小问题规模，最终求得区间[left,right]的最大子段和 int leftsum=MaxSubSum(a,left,center);//左子段 int rightsum=MaxSubSum(a,center+1,right);//右子段 int s1=0; int lefts=0; for(int i=center;i>=left;i--){ lefts+=a[i]; if(lefts>s1) s1=lefts; } int s2=0; int rights=0; for(int i=center+1;i<=right;i++){ rights+=a[i]; if(rights>s2) s2=rights; } sum=s1+s2; if(sum<leftsum) sum=leftsum; if(sum<rightsum) sum=rightsum; } return sum; } int MaxSum(int n,int* a){//接受数组a的长度n和指向数组a的指针 return MaxSubSum(a,1,n);//调用了MaxSubSum函数求解最大子段和问题。 }
P60 3.4.3最大子段和问题与动态规划算法的推广
int MaxSum2(int m,int n,int **a){//MaxSum2函数的总时间复杂度为O(n^3) int sum=0; int *b=new int[n+1];//定义一维数组b，用于计算二维数组中从上到下某些行的元素和。 for(int i=1;i<=m;i++){ for(int k=1;k<=n;k++) b[k]=0; for(int j=i;j<=m;j++){ for(int k=i;k<=n;k++) b[k]+=a[j][k]; int max=MaxSum(n,b);//调用一个MaxSum函数求出b数组的最大子段和 if(max>sum) sum=max; } } return sum; }
P70 3.8.2递归计算最优值
void MNS(int C[],int n,int **size){//二维数组size用来表示函数Size(i,j)的值 for(int j=0;i<C[1];j++)//第一上端点在[1][j]之前都是0 size[1][j]=0; for(int j=C[1];j<=n;j++)//第一上端点在[1][j]后都为1 size[1][j]=1; for(int i=2;i<n;i++){ for(int j=0;j<C[i];j++)//j<C[i-1]，出现交叉打架，不能选择当前线 size[i][j]=size[i-1][j];//size[i][j]值等于正上方的值 for(int j=C[i];j<=n;j++)//j>C[i-1]，没有交叉了，可以选择当前线 size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1); //这时需要选择，是选择当前线还是不选择，选择标准是选择的线路数量要求最大 //前为选用当前线，后为不选用 } size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1); //数组的最后一个值，即为整个线路中可选择的线路的最大数量 }
P71 3.8.3构造最优解
void Traceback(int C[],int **size,int n,int Next[],int& m){ int j=n; m=0; for(int i=n;i>1;i--){ if(size[i][j]!=size[i-1][j]){ Next[m++]=i;//上端点m向后进一 j=C[i]-1;//下端点j向前进一 } if(j>=C[1]) Net[m++]=1; } }
第4章 贪心算法
P96 4.1活动安排问题
void GreedySelector(int n,int s[],int f[],bool A[]){ A[1]=true;//用集合A来存储所选择的活动，A[1]为已选项 int j=1; for(int i=2;i<=n;i++){//从A[2]开始挑选活动 if(s[i]>=f[j]){//待选择活动的起始时间s[i],目前已选择的最后一个活动的结束时间f[j]，作比较 j=i;//将活动i加入选择队列中 } else A[i]=false;//表示不选择活动i } }
P99 4.1背包问题
void Knapsack(int n,float m,float v[],float w[],float x[]){//贪心算法解决背包问题(非0-1背包) Sort(n,v,w);//Sort函数，排序各个物体的单位体积下的价值(价值v/质量w) int i; for(i=1;i<=n;i++)//n为所有物品的总大小，用x[i]=0表示没被装入背包，x[i]=1表示被装入背包了 x[i]=0; float c=M;//c被赋初值为原始背包大小 for(i=1;i<=n;i++){ if(w[i]>c)//背包满了 break; x[i]=1;//表示这个单位体积的物品被全部装入背包 c-=w[i];//现在背包的大小c要被减去装入物品占据的大小 } if(i<=n) x[i]=c/w[i];//x[i]表示第i个物品的所占体积在当前规定背包最大容量M的条件下被装入的比例 //比如x[i]=0.5，表示第i个物品的一半被放入背包，另一半没有放入 }
