算法设计及分析所有程序

1、-. z.目录 TOC o 1-3 h z u HYPERLINK l _Toc406412024第二章递归与分治 PAGEREF _Toc406412024 h 3HYPERLINK l _Toc4064120251、用递归思想求N! PAGEREF _Toc406412025 h 3HYPERLINK l _Toc4064120262、用递归思想求Fibonacci数列 PAGEREF _Toc406412026 h 3HYPERLINK l _Toc4064120273、用递归思想求排列问题 PAGEREF _Toc406412027 h 4HYPERLINK l _Toc4064120

2、284、用递归思想求整数划分问题 PAGEREF _Toc406412028 h 5HYPERLINK l _Toc4064120295、用递归思想求汉诺塔问题 PAGEREF _Toc406412029 h 6HYPERLINK l _Toc4064120306、用递归思想实现插入排序 PAGEREF _Toc406412030 h 7HYPERLINK l _Toc4064120317、用分治思想实现二分查找 PAGEREF _Toc406412031 h 8HYPERLINK l _Toc4064120328、用分治法求两个大整数的乘法 PAGEREF _Toc406412032 h 9

3、HYPERLINK l _Toc4064120339、用分治思想求一个数组的最大值与最小值 PAGEREF _Toc406412033 h 10HYPERLINK l _Toc40641203410、用分法思想实现合并排序 PAGEREF _Toc406412034 h 12HYPERLINK l _Toc40641203511、用分治思想实现快速排序 PAGEREF _Toc406412035 h 13HYPERLINK l _Toc40641203612、用分治法实现线性时间选择问题 PAGEREF _Toc406412036 h 15HYPERLINK l _Toc40641203713

4、、用分法思想实现残缺棋盘问题 PAGEREF _Toc406412037 h 15HYPERLINK l _Toc406412038第三章动态规划法 PAGEREF _Toc406412038 h 18HYPERLINK l _Toc4064120391、矩阵连乘问题 PAGEREF _Toc406412039 h 18HYPERLINK l _Toc4064120402、最长公子序列 PAGEREF _Toc406412040 h 20HYPERLINK l _Toc4064120413、最大子段和问题 PAGEREF _Toc406412041 h 23HYPERLINK l _Toc40

5、64120424、图像压缩问题 PAGEREF _Toc406412042 h 28HYPERLINK l _Toc4064120435、电路布线问题 PAGEREF _Toc406412043 h 31HYPERLINK l _Toc4064120446、最 PAGEREF _Toc406412044 h 31HYPERLINK l _Toc4064120457、最 PAGEREF _Toc406412045 h 31HYPERLINK l _Toc406412046第四章贪心算法 PAGEREF _Toc406412046 h 32HYPERLINK l _Toc4064120471、哈夫

6、曼编码 PAGEREF _Toc406412047 h 32HYPERLINK l _Toc4064120484、Kruskal算法求最小生成树 PAGEREF _Toc406412048 h 35HYPERLINK l _Toc4064120495、集装箱问题 PAGEREF _Toc406412049 h 38HYPERLINK l _Toc4064120506、活动安排问题 PAGEREF _Toc406412050 h 40HYPERLINK l _Toc406412051第五章回溯法 PAGEREF _Toc406412051 h 42HYPERLINK l _Toc40641205

7、21、用回溯法求01背包问题 PAGEREF _Toc406412052 h 42HYPERLINK l _Toc4064120532、用回溯法求N皇后问题 PAGEREF _Toc406412053 h 45HYPERLINK l _Toc4064120543、用回溯法求旅行售货员问题 PAGEREF _Toc406412054 h 46HYPERLINK l _Toc4064120554、用回溯法求圆排列问题 PAGEREF _Toc406412055 h 48HYPERLINK l _Toc4064120565、用回溯法求符号三角形问题 PAGEREF _Toc406412056 h 5

8、0HYPERLINK l _Toc4064120576、用回溯法求批处理作业调度问题 PAGEREF _Toc406412057 h 52HYPERLINK l _Toc4064120587、用回溯法求连续邮资问题 PAGEREF _Toc406412058 h 54HYPERLINK l _Toc4064120598、用回溯法求图的m着色问题 PAGEREF _Toc406412059 h 57HYPERLINK l _Toc4064120609、用回溯法求最大团问题 PAGEREF _Toc406412060 h 59HYPERLINK l _Toc406412061第六章回溯法 PAGE

9、REF _Toc406412061 h 62HYPERLINK l _Toc4064120621、用分支限界法求01背包问题 PAGEREF _Toc406412062 h 62-. z.第二章 递归与分治1、用递归思想求N!王晓东版计算机算法设计与分析第四版 P11页，例21#include void main()long n;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;elseret

10、urn 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(请输入一个数n);scanf(%ld,&n);long result = Fibonacci(n);printf(%ldn,result);3、用递归思想求排列问题王晓东版计算机算法设计与分析第四版 P13页，例24N个元素的全排列的个数为：N!本算法非常重要，因为它

11、是很多算法的根底，比方回溯法那章里的算法很多都是以本算法为根底的。#include / 交换两个元素的值void Swap(int &*,int &y)int t = *;* = y;y = t;/ 产生listk:m的所有排列/ m 是最后一个元素在数组中的下标void Perm(int list,int k,int m)if(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,list

12、k); / 将元素复原void main()int a5 = 1,2,3,4,5;/ 求数组前面三个元素的全排列Perm(a,0,3);4、用递归思想求整数划分问题王晓东版计算机算法设计与分析第四版 P14页，例25整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时根本都将涉及。所谓整数划分，是指把一个正整数n写成如下形式：n=m1+m2+mi; 其中mi为正整数，并且1 = mi = n，则m1,m2,.,mi为n的一个划分。如果m1,m2,.,mi中的最大值不超过m，即ma*(m1,m2,.,mi)0)，只有一种划分即1;(2) 当 m=1 时，不管n的值为多少，只有

13、一种划分即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) 当 n m 时，根据划分中是否包含最大值 m，可以分为两种情况：(a). 划分中包含m的情况，即m,*1,*2, .,*i,其中*1,*2, .,*i 的和为n-m，可能再次出现m，因此是n-m的m划分，因此这种划分个数为f(n-m, m);(b). 划分中不包含m

14、的情况，则划分中所有值都比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以到达回归条件，从而解决问题。其递推表达式如下：f(n, m) =1; ( n = 1 or m = 1 )f(n, m) =f(n, n); ( n m )因此我们可以给出求出 f(n, m) 的递归函数代码如下。/ 求整数n的全部划分数，其中ma*代表最大加数long

15、 GetPartitionCount(int n, int ma*) if (n = 1 | ma* = 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,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

16、(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);for(i=0;iright)return -1;if(*=amiddle)return middle;elseif(*amiddle)return BinarySearch(a,*,middle+1,right);elsereturn BinarySearch(a,*,l

17、eft,middle-1);void main()int a9=-2,2,7,9,19,21,34,65,98;int inde* = BinarySearch(a,100,8);printf(%dn,inde*);方法二：用循环代替递归/ 在a数组里查找是否存在*这个元素，如果存在，则返回元素所在下标，如果不存在/ 则返回-1/ n为最后一个元素的下标int BinarySearch(int a,int *,int n)int left = 0;/ 开场需要查找元素的下标int right = n-1;/ 最后需要查找元素的下标while(leftamiddle)left = middle+

18、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,&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

19、-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、用分治思想求一个数组的最大值与最小值#include #include #include #define LEN 8void ma*min(int a,int *ma*,int *min,int low,int high)int mid,ma*1,min1,ma*2,min2;if(high-low)=

20、alow)*ma* = ahigh;*min = alow;else*ma* = alow;*min = ahigh;elsemid = (high+low)/2;ma*min(a,&ma*1,&min1,low,mid);ma*min(a,&ma*2,&min2,mid+1,high);*ma* = ma*1ma*2ma*1:ma*2;*min = min1min2min1:min2;void main()int aLEN;int ma*=-1,min=1000;srand(unsigned)time(NULL);printf(数组里的元素为:n);for(int i=0;iLEN;i+)a

21、i = rand()%100;printf(%d ,ai);ma*min(a,&ma*,&min,0,LEN-1);printf(n最大值为:%d n最小值为:%dn,ma*,min);#include #include #include #define LEN 8void main()int aLEN;srand(unsigned)time(NULL);printf(数组里的元素为:n);for(int i=0;iLEN;i+)ai = rand()%100;printf(%d ,ai);*/10、用分法思想实现合并排序#includeint b9;void merge(int c,int

22、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,int right)if(leftright) int i=(left+right)/2;mergesort(a,left,i);/ 将左边局部排好序mergesort(a,i+1,right);/ 将右边局部排好序merge(a,b,left,i,right);/ 将左右两边合并

23、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(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)/ 不止一个元素时

24、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 swap(int * *,int * y);int i=p,j=r+1;int *=ap;while(true)while(a+i* & i* & jp);if(i=j)break;swap(&ai,&aj);ap=aj;aj=*;return j;void swap(int *

25、 *,int * y)int t;t = *;* = *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);for( i=0;i9;i+)printf(%dt,ai);printf(n);如果每次划分不以ap为基准，而是随机从ap-ar里取一个数为基准，则可以设计如下随机化快速排序算法。/ 随机选择策略的划分算法,需要调用partition函数int RandomizedPartition(

26、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 RandomizedSelect(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;/ 计

27、算通过划分后，从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、用分法思想实现残缺棋盘问题王晓东版计算机算法设计与分析第四版 P20页，例2.6注意：同一种形状的骨牌，在填充时数字不一样，关键看三个一样数字摆放位置所构成的形状。#include int tile=1; /L型骨牌的编号(递增)int board100100; /棋盘/* tr-当前棋盘左上角的行号

28、* 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+; /每次递增1int s=size/2; /棋盘中间的行、列号(相等的)/检查特殊方块是否在左上角子棋盘中if ( drtr+s & dctc+s ) /在chessBoard ( tr, tc, dr, dc, s );else /不在，将该子棋盘

29、右下角的方块视为特殊方块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 ( 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 );e

30、lse 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 inde*_*,inde*_y;printf(输入特殊方格位置的坐标: );scanf(%d%d,&inde*_*,&inde*_y);chessBoard ( 0,0,inde*_*,inde*_y,size );for ( int i=0; isize; i+ )for ( int j=0; jsize; j+ )printf(%

31、dt,boardij);printf(n);第三章 动态规划法1、矩阵连乘问题#include #include / n 矩阵的个数/ p 记录各矩阵的维数，n个矩阵有n+1个维数，Ai的维数为pi-1,pi/ mij 记录从第i个矩阵到第j个矩阵连乘，最小的数乘次数/ sij 记录从第i个矩阵到第j个矩阵连乘，取最小的数乘次数时，最后两个矩阵相乘时的位置/ 如果sij = k,则代表从第i个矩阵到第k个矩阵连乘,得到一个结果矩阵，/ 从第k+1个矩阵到第j个矩阵连乘,得到另一个结果矩阵，然后这两个结果矩阵做最后的乘法void Matri*Chain(int *p,int n,int (*m)

32、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+)/ 求从第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+)in

33、t 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);Traceback(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

34、=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;Matri*Chain(p,6,m,s);for( i=1;i7;i+)for(int j=1;j7;j+)printf(%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、最长公子序列#inc

35、lude #include #include / *和Y保存两个字符串，m为*字符串里字符的个数,n为Y字符串里字符的个数/ cij代表当*取前面连续i个字符，Y取前面连续j个字符时，这两个子字/ 符串的最大公共子序列的长度，bij记录此时的最大公共子序列是如何/ 得来的。void LCSLength(int m,int n,char * *,char *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+) / *取前面连续i个字符for(int

36、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 * *,int * b,char * result)if(i=0 | j=0)/ 将result里的字符反转for(int j=0;jk/2;j+)char t = resultj;resultj = resultk-1-j;resultk-1-j = t;resultk = 0;return;elseif( bij = 1)resultk+ = *i-1;L

37、CS(i-1,j-1,*,b,result);else if( bij = 2)LCS(i-1,j,*,b,result);elseLCS(i,j-1,*,b,result);void main()char A100=*y*zy*yzzy;char B100=*zyz*yz*yz*y;int lenA = strlen(A);int lenB = strlen(B);printf(%d %dn,lenA,lenB);/ c与b为两个动态二维数组，这样不浪费空间int * c = (int *)malloc(lenA+1)*sizeof(int *);int * b = (int *)mallo

38、c(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(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);c

39、har 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 * *,int * b,char * result)int len = (mnm:n);int k = len+1;while(m!=0 & n!=0)if(bmn=1)result-k = *m-1;/此处与教材有区别，因为教材是从下标为1的元素处保存有效字符 m-;n

40、-;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 #include #define N 8/ 代表列int bestSum = 0;/ 最大子段和的值int besti=0;/ 最大子段和所在段的起始坐标int bestj=0;/ 最大子段和所在段的终止坐标/ 最大子段和的分治算法void Ma*Sub

41、Sum(int *a,int left,int right)if(left = right)int thisSum = aleft0aleft:0;if(thisSum bestSum)bestSum = thisSum;besti = bestj = left;/ elseint middle = (left+right)/2;Ma*SubSum(a,left,middle);Ma*SubSum(a,middle+1,right);int s1 = 0;int lefts = 0;int bi = middle + 1;/ 重要for(int i = middle;i=left;i-)lef

42、ts = 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) / 右边的最大子段和不是小于0int sum = s1 + s2;if(sum bestSum)bestSum = sum;besti = bi;/ 记录最大子段和的起始坐标bestj = bj;/ 记录最大子段和的终止坐标void main()

43、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 ,ai);int bi=0,bj=0;Ma*SubSum(a,1,N);printf(n从%d到%d的子段和最大，最大值为：%dn,besti,bestj,bestSum);2动态规划思路实现补充了书本上不完美的地方：在求最大子段和，随便可以求出最大子

44、段和的起始坐标和终止坐标；在求最大子矩阵和时，可以随便求出子矩阵的左上角和右下角坐标。#include #include #include #define N 4/ 代表列#define M 4/ 代表行/ 求最大子段和的动态规划算法int Ma*Sum(int n,int *a,int &besti,int &bestj)int sum = 0,b=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

45、;/ m 代表数组的行数，下标为0的行没有使用/ n 代表数组的列数，下标为0的列没有使用int Ma*Sum2(int m,int n,int * a,int &rowStart,int &rowEnd,int &colStart,int &colEnd)int sum = 0;int * b = (int *) malloc(sizeof(int)*(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

46、= 0;for(int j=i;j=m;j+)/ 遍历终止行for(int k=1;ksum)sum = ma*;rowStart = i;rowEnd = j;colStart = tColStart;colEnd = tColEnd;return sum;/*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 = -ran

47、d()%30;printf(%d ,ai);int bi=0,bj=0;int ma* = Ma*Sum(N,a,bi,bj);printf(n从%d到%d的子段和最大，最大值为：%dn,bi,bj,ma*);*/void main()int * a;a = (int * )malloc(M+1)*sizeof(int *);for(int i=1;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

48、 = 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 ma* = Ma*Sum2(M,N,a,brs,bre,bcs,bce);printf(n从(%d,%d)到(%d,%d)的子块和最大，最大值为：%dn,brs,bcs,bre,bce,ma*);4、图像压缩问题王晓东版计算机算法设计与分析第四版 P65页，例3.7书本上P67页上第一

49、行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个像素取最小存储空间里，最后一个分段里元素的个数/ bi 存储第i个像素的灰度值值需要多少位void press(int n,int p,int s,int l,int b)int Lma* = 256;/ 每个分段里像素个数

50、不超过256个int header = 11;/ 每个分段里像素的头部信息为11位s0 = 0;for(int i=1;i=n;i+)bi = length(pi);int bma* = bi; / 记录最后一段里，各像素的所需存储位数的最大值/ 以最后一个像素单独作为最后一段si = si-1 + bi;li = 1;for(int j=2;j=i& j=Lma*;j+)if(bma* si-j + bma* * j)si = si-j + bma* * j;li = j;si += header;void Traceback(int n,int &i,int s,int l)if(n=0)

51、return ;Traceback(n-ln,i,s,l);/*si+ = n-ln;/书本上的写法：重新为s数组赋值，用来存储分段位置 */l+i = ln;void Output(int s,int l,int b,int n)printf(n图像压缩后的最小空间：%dn,sn);int m = 0;Traceback(n,m,s,l);/* / 书本上的写法，其中bj = bsj这一行是错误的sm = n;/ 最后一段的分段位置for(int j=1;j=m;j+)lj = lsj;bj = bsj;*/int j=1;/ 段计数器int ne*tSplit = lj;/ 下一段的分届f

52、or(int i=1;ine*tSplit)/ 到了下一段的开场元素j+;ne*tSplit += lj;bj = bi;continue;if(bibj)bj = bi;printf(n将原灰度序列分成%d段序列段n,m);for( j=1;j=m;j+)printf(第%d段有%d个像素，存储每个像素止少需要%d位n,j,lj,bj);void main()int p6+1 = 0,10,12,15,255,2,1;int s6+1,l6+1,b6+1;printf(各像素的灰度值为：n);for(int i=1;i=6;i+)printf(%d ,pi);printf(n);press(

53、6,p,s,l,b);Output(s,l,b,6);5、电路布线问题6、最7、最第四章 贪心算法1、哈夫曼编码#include #include #include typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode, *HuffmanTree;/ 动态分配数组存储赫夫树typedef char * HuffmanCode;/ 动态分配数组存储赫夫曼编码表/ w数组存放n个字符的权值均0，构造赫夫曼树HT, 并求出n个字符的赫夫曼编码HCvoid HuffmanCoding(HuffmanTree

54、 &HT, HuffmanCode &HC,int *w,int n)if(n=1)return;int m = 2*n-1; / 整棵树结点的个数HT = (HuffmanTree)malloc(m+1)*sizeof(HTNode);/ 构造一个动态数组用作赫夫曼树，其中0号单元未用HuffmanTree p = NULL;int i;for(i=1,p = HT+1;iweight = *w;p-lchild = 0;p-rchild = 0;p-parent = 0;for(i = n+1;iweight = 0;p-lchild = 0;p-rchild = 0;p-parent =

55、 0;for(i=n+1;i=m;i+)/*=在HT1到HTi-1里查找parent为0，而weight值最小的两个结点，其序号分别为s1,s2=*/unsigned int minValue1 = 999999;int s1 = -1;unsigned int minValue2 = 999999;int s2 = -1;for(int k = 1;ki;k+)if(HTk.parent = 0)if(HTk.weightminValue1)minValue2 = minValue1;s2 = s1;minValue1 = HTk.weight;s1 = k;else if(HTk.weig

56、htminValue2)minValue2 = HTk.weight;s2 = k;HTi.weight = HTs1.weight + HTs2.weight;HTi.lchild = s1;HTi.rchild = s2;HTi.parent = 0;HTs1.parent = i;HTs2.parent = i;printf(哈夫曼树为n);printf(weighttparenttlchildtrchildn);for( i=1;i=m;i+)printf(%dt%dt%dt%dn,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);/ =从叶子结

57、点到根逆向求每个字符的赫夫曼编码=HC = (HuffmanCode)malloc(n+1)*sizeof(char *);char * cd = (char *)malloc(n*sizeof(char);cdn-1 = 0;int start;for(i = 1;i=n;i+)/ 求每个字符编码，循环1次，求出1个start = n-1;for(unsigned int c = i,p = HTc.parent; p!=0; c = p,p = HTp.parent)if(HTp.lchild = c)cd-start = 0;elsecd-start = 1;HCi = (char *)

58、 malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);/ 解码过程void Decoding(HuffmanTree &HT, char *needDecode,char * code,int n)int inde*=2*n-1;int k = 0;char result100;int len =strlen(needDecode);for(int i=0;ilen;i+)/ 如果到达叶子结点，代表找到*一个字符，输出这个字符，/ 并且将inde*恢复到树根处，方便查找下一个字符if(needDecodei = 0)inde* = HTinde*

59、.lchild;elseinde* = HTinde*.rchild;if(HTinde*.lchild = 0)resultk+ = codeinde*;inde* = 2*n-1;printf(密文为%sn,needDecode);if(inde* = 2*n-1) / 将密文全部处理完毕后，inde*应当回得赫夫曼树的树根处printf(明文为n);resultk = 0;puts(result);elseputs(密文不正确n);/ 主函数void main()HuffmanTree HT;HuffmanCode HC;char code = ,A,B,C,D,E,F,G,H;int

60、w = 0,5,29,7,8,14,23,3,11;HuffmanCoding(HT, HC,w+1,8);printf(n赫夫曼编码为:n);int sum = 0;for(int i=1;i=8;i+)printf(字符:%ct权值:%dt编码为:%sn,codei,wi,HCi);sum += wi*strlen(HCi);printf(n总长度：%dn,sum);char needDecode = 10;Decoding(HT,needDecode,code,8);4、Kruskal算法求最小生成树设有如下无向图，求这个图的最小生成树。判断两个节点是否连通，用并查集构造来实现。#inc