算法设计与分析报告所有程序

《算法设计与分析报告所有程序》由会员分享，可在线阅读，更多相关《算法设计与分析报告所有程序（66页珍藏版）》请在装配图网上搜索。

1、word目录第二章递归与分治31、用递归思想求N!32、用递归思想求Fibonacci数列33、用递归思想求排列问题44、用递归思想求整数划分问题55、用递归思想求汉诺塔问题66、用递归思想实现插入排序77、用分治思想实现二分查找88、用分治法求两个大整数的乘法99、用分治思想求一个数组的最大值与最小值1010、用分法思想实现合并排序1211、用分治思想实现快速排序1312、用分治法实现线性时间选择问题1513、用分法思想实现残缺棋盘问题15第三章动态规划法181、矩阵连乘问题182、最长公子序列203、最大子段和问题234、图像压缩问题285、电路布线问题316、最317、最31第四章贪心算

2、法321、哈夫曼编码324、Kruskal算法求最小生成树355、集装箱问题386、活动安排问题40第五章回溯法421、用回溯法求01背包问题422、用回溯法求N皇后问题453、用回溯法求旅行售货员问题464、用回溯法求圆排列问题485、用回溯法求符号三角形问题506、用回溯法求批处理作业调度问题527、用回溯法求连续邮资问题548、用回溯法求图的m着色问题579、用回溯法求最大团问题59第六章回溯法621、用分支限界法求01背包问题6266 / 66第二章 递归与分治1、用递归思想求N!王晓东版计算机算法设计与分析第四版 P11页，例21#include void main()long n;

3、int JieChen(int n);printf(请输入一个数n);scanf(%ld,&n);long result = JieChen(n);printf(%ld,result);int JieChen(int n)if(n=1)return 1;elsereturn n*JieChen(n-1);2、用递归思想求Fibonacci数列王晓东版计算机算法设计与分析第四版 P12页，例22int Fibonacci(int n)if(n=1)return 1;elsereturn Fibonacci(n-1)+Fibonacci(n-2);void main()long n;printf(

4、请输入一个数n);scanf(%ld,&n);long result = Fibonacci(n);printf(%ldn,result);3、用递归思想求排列问题王晓东版计算机算法设计与分析第四版 P13页，例24N个元素的全排列的个数为：N!本算法非常重要，因为它是很多算法的根底，比如回溯法那章里的算法很多都是以本算法为根底的。#include / 交换两个元素的值void Swap(int &x,int &y)int t = x;x = y;y = t;/ 产生listk:m的所有排列/ m 是最后一个元素在数组中的下标void Perm(int list,int k,int m)if(

5、k=m)/ 如果只有一个元素for(int i=0;i=m;i+)printf(%d ,listi);printf(n);elsefor(int i=k;i=m;i+)Swap(listi,listk);Perm(list,k+1,m);Swap(listi,listk); / 将元素复原void main()int a5 = 1,2,3,4,5;/ 求数组前面三个元素的全排列Perm(a,0,3);4、用递归思想求整数划分问题王晓东版计算机算法设计与分析第四版 P14页，例25整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时根本都将涉与。所谓整数划分，是指把一个正整数

6、n写成如下形式：n=m1+m2+mi; 其中mi为正整数，并且1 = mi = n，如此m1,m2,.,mi为n的一个划分。如果m1,m2,.,mi中的最大值不超过m，即max(m1,m2,.,mi)0)，只有一种划分即1;(2) 当 m=1 时，不论n的值为多少，只有一种划分即n个1，1,1, 1, ., 1 ;(3) 当 n=m 时，根据划分中是否包含 n，可以分为两种情况：(a). 划分中包含n的情况，只有一个即 n ；(b). 划分中不包含n的情况，这时划分中最大的数字也一定比 n 小，即 n 的所有 ( n - 1 ) 划分。因此 f(n, n) = 1 + f(n, n-1);(4

7、) 当 n m 时，根据划分中是否包含最大值 m，可以分为两种情况：(a). 划分中包含m的情况，即m,x1,x2, .,xi,其中x1,x2, .,xi 的和为n-m，可能再次出现m，因此是n-m的m划分，因此这种划分个数为f(n-m, m);(b). 划分中不包含m的情况，如此划分中所有值都比m小，即n的(m-1)划分个数为f(n, m - 1);因此 f(n, m) = f(n-m, m) + f(n, m-1);综合以上情况，我们可以看出，上面的结论具有递归定义特征，其中1和2属于回归条件，3和4属于特殊情况，将会转换为情况5。而情况5为通用情况，属于递推的方法，其本质主要是通过减小m

8、以达到回归条件，从而解决问题。其递推表达式如下：f(n, m) =1; ( n = 1 or m = 1 )f(n, m) =f(n, n); ( n m )因此我们可以给出求出 f(n, m) 的递归函数代码如下。/ 求整数n的全部划分数，其中max代表最大加数long GetPartitionCount(int n, int max) if (n = 1 | max = 1) return 1; else if (n 0)Hanoi(n-1,A,C,B);printf(%d,%c-%cn,n,A,B);/ 模拟移动过程Hanoi(n-1,C,B,A);void main()Hanoi(3,

9、a,b,c);6、用递归思想实现插入排序#include #include #include void insertSort(int *aa,int n)if(n0)n = n-1;insertSort(aa,n);int a= aan;int k = n-1;while(k=0)& aaak)aak+1 = aak;k-;aak+1 = a;void main()int a10;srand(unsigned int)time(NULL);for(int i=0;i10;i+)ai = rand()%100;printf(%d ,ai);printf(n);insertSort(a,10);f

10、or(i=0;iright)return -1;if(x=amiddle)return middle;elseif(xamiddle)return BinarySearch(a,x,middle+1,right);elsereturn BinarySearch(a,x,left,middle-1);void main()int a9=-2,2,7,9,19,21,34,65,98;int index = BinarySearch(a,100,8);printf(%dn,index);方法二：用循环代替递归/ 在a数组里查找是否存在x这个元素，如果存在，如此返回元素所在下标，如果不存在/ 如此返

11、回-1/ n为最后一个元素的下标int BinarySearch(int a,int x,int n)int left = 0;/ 开始需要查找元素的下标int right = n-1;/ 最后需要查找元素的下标while(leftamiddle)left = middle+1;elseright = middle-1;return -1;8、用分治法求两个大整数的乘法最简单的方法，这里没有表现分治法的思想#include int main()char a100,b100,s202;int i,j,g,t=0,k=0,temp;printf(请输入两个大整数，空格分隔n);scanf(%s%s

12、,&a,&b);int m = strlen(a);int n = strlen(b);while(km+n-2)sk=0;temp=0;for(i=0;im;i+)for(j=0;jn;j+)if( (i+j) = k )/第k位上所有数字之和temp += (am-1-i-48)*(bn-1-j-48);g=(temp+t)%10;t=(temp+t)/10;/ t用来保存进位sk=g;k+;/ 求最高1位或者2位，并输出temp=0;for(i=0;im;i+)for(j=0;j=0;i-)printf(%d,si);printf(n);return 0;9、用分治思想求一个数组的最大值

13、与最小值#include #include #include #define LEN 8void maxmin(int a,int *max,int *min,int low,int high)int mid,max1,min1,max2,min2;if(high-low)=alow)*max = ahigh;*min = alow;else*max = alow;*min = ahigh;elsemid = (high+low)/2;maxmin(a,&max1,&min1,low,mid);maxmin(a,&max2,&min2,mid+1,high);*max = max1max2?m

14、ax1:max2;*min = min1min2?min1:min2;void main()int aLEN;int max=-1,min=1000;srand(unsigned)time(NULL);printf(数组里的元素为:n);for(int i=0;iLEN;i+)ai = rand()%100;printf(%d ,ai);maxmin(a,&max,&min,0,LEN-1);printf(n最大值为:%d n最小值为:%dn,max,min);#include #include #include #define LEN 8void main()int aLEN;srand(u

15、nsigned)time(NULL);printf(数组里的元素为:n);for(int i=0;iLEN;i+)ai = rand()%100;printf(%d ,ai);*/10、用分法思想实现合并排序#includeint b9;void merge(int c,int d,int l,int m,int r)int i=l,j=m+1,k=l;while(i=m)&(j=r)if(ci=cj)dk+=ci+;elsedk+=cj+;/ 将剩余局部处理好while(j=r)dk+=cj+;while(i=m)dk+=ci+;void mergesort(int a,int left,i

16、nt right)if(leftright) int i=(left+right)/2;mergesort(a,left,i);/ 将左边局部排好序mergesort(a,i+1,right);/ 将右边局部排好序merge(a,b,left,i,right);/ 将左右两边合并for(int j=left;j=right;j+)aj = bj;void main()int a9=4,3,6,8,9,1,25,2,34;printf(原始数据为:n);for(int i=0;i9;i+)printf(%dt,ai);mergesort(a,0,8);printf(n合并后的数据为:n);for

17、(i=0;i9;i+)printf(%dt,ai);printf(n);11、用分治思想实现快速排序#includevoid quicksort(int a,int p,int r) int partition(int a,int p,int r);if(pr)/ 不止一个元素时int q = partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);/ 以ap为基准，将数组ap-ar段元素分为两部，其实一局部/ 比ap小，另一局部比ap大，/ 返回值为ap最终所在位置int partition(int a,int p,int r)void

18、swap(int * x,int * y);int i=p,j=r+1;int x=ap;while(true)while(a+ix & ix & jp);if(i=j)break;swap(&ai,&aj);ap=aj;aj=x;return j;void swap(int * x,int * y)int t;t = *x;*x = *y;*y = t;void main()int a9=9,8,7,6,5,4,3,2,1;printf(n排序前的结果n);for(int i=0;i9;i+)printf(%dt,ai);quicksort(a,0,8);printf(n排序后的结果n);f

19、or( i=0;i9;i+)printf(%dt,ai);printf(n);如果每次划分不以ap为基准，而是随机从ap-ar里取一个数为基准，如此可以设计如下随机化快速排序算法。/ 随机选择策略的划分算法,需要调用partition函数int RandomizedPartition(int a,int p,int r)srand(unsigned int)time(NULL);int i = p+rand()%(r-p+1);swap(&ai,&ap);return partition(a,p,r);12、用分治法实现线性时间选择问题本算法要用到上面快速排序的随机划分算法int Random

20、izedSelect(int a,int p,int r,int k)if(p=r)/ 如果只剩下一个数，如此这个肯定就是第k小的数return ap;elseint i = RandomizedPartition(a,p,r);/ 经过快速排序进展划分int j = i-p+1;/ 计算通过划分后，从ap到ai有多少数if(k=j)/ 第k小的数在ai的前半段return RandomizedSelect(a,p,i,k);else/ 第k小的数在ai的后半段，并且从ap到ai这些数都小于第k小的数return RandomizedSelect(a,i+1,r,k-j);13、用分法思想实现

21、残缺棋盘问题王晓东版注意：同一种形状的骨牌，在填充时数字不一样，关键看三个一样数字摆放位置所构成的形状。#include int tile=1; /L型骨牌的编号(递增)int board100100; /棋盘/* tr-当前棋盘左上角的行号* tc-当前棋盘左上角的列号* dr-当前特殊方格所在的行号* dc-当前特殊方格所在的列号* size：当前棋盘的:2k*/void chessBoard ( int tr, int tc, int dr, int dc, int size )if ( size=1 ) /棋盘方格大小为1,说明递归到最里层return;int t=tile+; /每次

22、递增1int s=size/2; /棋盘中间的行、列号(相等的)/检查特殊方块是否在左上角子棋盘中if ( drtr+s & dctc+s ) /在chessBoard ( tr, tc, dr, dc, s );else /不在，将该子棋盘右下角的方块视为特殊方块boardtr+s-1tc+s-1=t;chessBoard ( tr, tc, tr+s-1, tc+s-1, s );if ( dr=tc+s ) /在chessBoard ( tr, tc+s, dr, dc, s );else /不在，将该子棋盘左下角的方块视为特殊方块boardtr+s-1tc+s=t;chessBoard

23、 ( tr, tc+s, tr+s-1, tc+s, s );/检查特殊方块是否在左下角子棋盘中if ( dr=tr+s & dc=tr+s & dc=tc+s ) chessBoard ( tr+s, tc+s, dr, dc, s );else boardtr+stc+s=t;chessBoard ( tr+s, tc+s, tr+s, tc+s, s );void main()int size;printf(输入棋盘的size,大小必须是2的n次幂: );scanf(%d,&size);int index_x,index_y;printf(输入特殊方格位置的坐标: );scanf(%d%

24、d,&index_x,&index_y);chessBoard ( 0,0,index_x,index_y,size );for ( int i=0; isize; i+ )for ( int j=0; jsize; j+ )printf(%dt,boardij);printf(n);第三章 动态规划法1、矩阵连乘问题#include #include / n 矩阵的个数/ p 记录各矩阵的维数，n个矩阵有n+1个维数，Ai的维数为pi-1,pi/ mij 记录从第i个矩阵到第j个矩阵连乘，最小的数乘次数/ sij 记录从第i个矩阵到第j个矩阵连乘，取最小的数乘次数时，最后两个矩阵相乘时的位置

25、/ 如果sij = k,如此代表从第i个矩阵到第k个矩阵连乘,得到一个结果矩阵，/ 从第k+1个矩阵到第j个矩阵连乘,得到另一个结果矩阵，然后这两个结果矩阵做最后的乘法void MatrixChain(int *p,int n,int (*m)7,int (*s)7)for(int i=1;i=n;i+)mii = 0;for(int len = 2;len=n;len+)/ 遍历矩阵链的长度/ 当矩阵链的长度的长度固定为len时，这时有n-len+1个矩阵链需要求最小数乘/ 下面的循环用来从前往后求这n-len+1个矩阵链的最小数乘值for(int i=1;i=n-len+1;i+)/ 求从

26、第i个矩阵到第i+len-1个矩阵的最小数乘值int j = i+len-1;mij = mii + mi+1j +pi-1*pi*pj;/ 假设从第i个矩阵处划分是最小的,mii=0sij = i;for(int k=i+1;kj;k+)int t = mik + mk+1j +pi-1*pk*pj;if(tmij)mij = t;sij = k;/ 当矩阵链相乘取最小数乘时，输出矩阵链加括号的格式void Traceback(int i,int j,int (*s)7)if(i=j)printf(A%d,i);return;printf();Traceback(i,sij,s);Trace

27、back(sij+1,j,s);printf();/ 下面两条语跟书本上一致，供参考/printf(Multiply A%d,%d,i,sij);/printf( and A%d,%dn,sij+1,j);void main()int p6+1=30,35,15,5,10,20,25;int m6+16+1;/ 下标为0的行与列没有用int s6+16+1; / 初始化m和s这两个矩阵for(int i=0;i7;i+)for(int j=0;j7;j+)mij=-1;sij=-1;MatrixChain(p,6,m,s);for( i=1;i7;i+)for(int j=1;j7;j+)pr

28、intf(%dt,mij);printf(n);printf(n);for( i=1;i7;i+)for(int j=1;j7;j+)printf(%dt,sij);printf(n);Traceback(1,6,s);2、最长公子序列#include #include #include / X和Y保存两个字符串，m为X字符串里字符的个数,n为Y字符串里字符的个数/ cij代表当X取前面连续i个字符，Y取前面连续j个字符时，这两个子字/ 符串的最大公共子序列的长度，bij记录此时的最大公共子序列是如何/ 得来的。void LCSLength(int m,int n,char * X,char

29、*Y,int * c ,int * b)for(int i=0;i=n;i+)c0i = 0;b0i = 0;for(i=0;i=m;i+)ci0 = 0;bi0 = 0;for(i=1;i=m;i+) / X取前面连续i个字符for(int j=1;j= cij-1)cij = ci-1j;bij = 2;elsecij = cij-1;bij = 3;/ 获取最长公共子序列符号(递归实现,书本上所用的方法)int k=0;void LCS(int i,int j,char * X,int * b,char * result)if(i=0 | j=0)/ 将result里的字符反转for(i

30、nt j=0;jk/2;j+)char t = resultj;resultj = resultk-1-j;resultk-1-j = t;resultk = 0;return;elseif( bij = 1)resultk+ = Xi-1;LCS(i-1,j-1,X,b,result);else if( bij = 2)LCS(i-1,j,X,b,result);elseLCS(i,j-1,X,b,result);void main()char A100=xyxzyxyzzy;char B100=xzyzxyzxyzxy;int lenA = strlen(A);int lenB = str

31、len(B);printf(%d %dn,lenA,lenB);/ c与b为两个动态二维数组，这样不浪费空间int * c = (int *)malloc(lenA+1)*sizeof(int *);int * b = (int *)malloc(lenA+1)*sizeof(int *);for(int i=0;i=lenA;i+)ci = (int *)malloc(sizeof(int)*(lenB+1);bi = (int *)malloc(sizeof(int)*(lenB+1);LCSLength(lenA,lenB,A,B,c,b);for( i=0;i=lenA;i+)for(

32、int j=0;j=lenB;j+)printf(%d ,cij);printf(n);printf(n);for( i=0;i=lenA;i+)for(int j=0;j=lenB;j+)printf(%d ,bij);printf(n);char result100;LCS(lenA,lenB,A,b,result);/ 输出最长公共字符串for( i=0;istrlen(result);i+)printf(%c,resulti);printf(n);获取最长公共子序列符号的非递归实现/ 获取最长公共子序列符号void LCS(int m,int n,char * X,int * b,ch

33、ar * result)int len = (mn?m:n);int k = len+1;while(m!=0 & n!=0)if(bmn=1)result-k = Xm-1;/此处与教材有区别，因为教材是从下标为1的元素处保存有效字符 m-;n-;else if(bmn=2)m-;elsen-;/ 将result数组里的数据平移for(int i=k,j=0;i=len;i+,j+)resultj = resulti;resultj = 0; / 设置完毕字符3、最大子段和问题1分治思路实现改良了书本上的算法，可以求出最大子段和的起始坐标和终止坐标#include #include #inc

34、lude #define N 8/ 代表列int bestSum = 0;/ 最大子段和的值int besti=0;/ 最大子段和所在段的起始坐标int bestj=0;/ 最大子段和所在段的终止坐标/ 最大子段和的分治算法void MaxSubSum(int *a,int left,int right)if(left = right)int thisSum = aleft0?aleft:0;if(thisSum bestSum)bestSum = thisSum;besti = bestj = left;/ elseint middle = (left+right)/2;MaxSubSum(

35、a,left,middle);MaxSubSum(a,middle+1,right);int s1 = 0;int lefts = 0;int bi = middle + 1;/ 重要for(int i = middle;i=left;i-)lefts = lefts + ai;if(leftss1)s1 = lefts;bi = i;if(bi middle +1) / 左边的最大子段和不是小于0int s2 = 0;int rights = 0;int bj = middle;for(int i = middle+1;is2)s2 = rights;bj = i;if(bj middle)

36、 / 右边的最大子段和不是小于0int sum = s1 + s2;if(sum bestSum)bestSum = sum;besti = bi;/ 记录最大子段和的起始坐标bestj = bj;/ 记录最大子段和的终止坐标void main()int aN+1;/ 下标为0的元素没有意义srand(unsigned int)time(NULL);/ 设置随机种子for(int i=1;i=N;i+)int flag = rand()%2;/ flag为1代表正数，flag为0代表负数if(flag)ai= rand()%30;elseai = -rand()%30;printf(%d ,a

37、i);int bi=0,bj=0;MaxSubSum(a,1,N);printf(n从%d到%d的子段和最大，最大值为：%dn,besti,bestj,bestSum);2动态规划思路实现补充了书本上不完美的地方：在求最大子段和，随便可以求出最大子段和的起始坐标和终止坐标；在求最大子矩阵和时，可以随便求出子矩阵的左上角和右下角坐标。#include #include #include #define N 4/ 代表列#define M 4/ 代表行/ 求最大子段和的动态规划算法int MaxSum(int n,int *a,int &besti,int &bestj)int sum = 0,b

38、=0;besti = 0;int ti = 0;int tj = 0;for(int i=1;i0)b += ai;elseb = ai;ti = i;if(b sum)sum = b;besti = ti;bestj = i;return sum;/ m 代表数组的行数，下标为0的行没有使用/ n 代表数组的列数，下标为0的列没有使用int MaxSum2(int m,int n,int * a,int &rowStart,int &rowEnd,int &colStart,int &colEnd)int sum = 0;int * b = (int *) malloc(sizeof(int

39、)*(n+1);int tRowStart = 0;int tRowEnd = 0;int tColStart = 0;int tColEnd = 0;for(int i=1;i=m;i+)/ 遍历起始行for(int k=1;k=n;k+)bk = 0;for(int j=i;j=m;j+)/ 遍历终止行for(int k=1;ksum)sum = max;rowStart = i;rowEnd = j;colStart = tColStart;colEnd = tColEnd;return sum;/*void main()int aN+1;/ 下标为0的元素没有意义srand(unsig

40、ned int)time(NULL);/ 设置随机种子for(int i=1;i=N;i+)int flag = rand()%2;/ flag为1代表正数，flag为0代表负数if(flag)ai= rand()%30;elseai = -rand()%30;printf(%d ,ai);int bi=0,bj=0;int max = MaxSum(N,a,bi,bj);printf(n从%d到%d的子段和最大，最大值为：%dn,bi,bj,max);*/void main()int * a;a = (int * )malloc(M+1)*sizeof(int *);for(int i=1;

41、i=M;i+)ai =(int *) malloc(N+1)*sizeof(int);srand(unsigned int)time(NULL);/ 设置随机种子for( i=1;i=M;i+)for(int j=1;j=N;j+)int flag = rand()%2;/ flag为1代表正数，flag为0代表负数if(flag)aij= rand()%30;elseaij = -rand()%30;printf(%dt,aij);printf(n);int brs = 0;int bre = 0;int bcs = 0;int bce = 0;int max = MaxSum2(M,N,a

42、,brs,bre,bcs,bce);printf(n从(%d,%d)到(%d,%d)的子块和最大，最大值为：%dn,brs,bcs,bre,bce,max);4、图像压缩问题王晓东版书本上P67页上第一行bj = bsj行错误，本程序修正了这个错误，在求每段的最大位数时，只需要从头到位扫描一次，时间复杂度为O(n)。小有成就感_#include int length(int i)int k=1;i = i/2;while(i0)k+;i = i/2;return k;/ n 像素总个数/ pi 第i个像素点的灰度值/ si 记录前i个像素的最小存储空间/ li 记录前i个像素取最小存储空间里，

43、最后一个分段里元素的个数/ bi 存储第i个像素的灰度值值需要多少位void press(int n,int p,int s,int l,int b)int Lmax = 256;/ 每个分段里像素个数不超过256个int header = 11;/ 每个分段里像素的头部信息为11位s0 = 0;for(int i=1;i=n;i+)bi = length(pi);int bmax = bi; / 记录最后一段里，各像素的所需存储位数的最大值/ 以最后一个像素单独作为最后一段si = si-1 + bi;li = 1;for(int j=2;j=i& j=Lmax;j+)if(bmax si-j