算法設(shè)計及分析所有程序

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數(shù)列 PAGEREF _Toc406412026 h 3HYPERLINK l _Toc4064120273、用遞歸思想求排列問題 PAGEREF _Toc406412027 h 4HYPERLINK l _Toc4064120

2、284、用遞歸思想求整數(shù)劃分問題 PAGEREF _Toc406412028 h 5HYPERLINK l _Toc4064120295、用遞歸思想求漢諾塔問題 PAGEREF _Toc406412029 h 6HYPERLINK l _Toc4064120306、用遞歸思想實現(xiàn)插入排序 PAGEREF _Toc406412030 h 7HYPERLINK l _Toc4064120317、用分治思想實現(xiàn)二分查找 PAGEREF _Toc406412031 h 8HYPERLINK l _Toc4064120328、用分治法求兩個大整數(shù)的乘法 PAGEREF _Toc406412032 h 9

3、HYPERLINK l _Toc4064120339、用分治思想求一個數(shù)組的最大值與最小值 PAGEREF _Toc406412033 h 10HYPERLINK l _Toc40641203410、用分法思想實現(xiàn)合并排序 PAGEREF _Toc406412034 h 12HYPERLINK l _Toc40641203511、用分治思想實現(xiàn)快速排序 PAGEREF _Toc406412035 h 13HYPERLINK l _Toc40641203612、用分治法實現(xiàn)線性時間選擇問題 PAGEREF _Toc406412036 h 15HYPERLINK l _Toc40641203713

4、、用分法思想實現(xiàn)殘缺棋盤問題 PAGEREF _Toc406412037 h 15HYPERLINK l _Toc406412038第三章動態(tài)規(guī)劃法 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、用回溯法求批處理作業(yè)調(diào)度問題 PAGEREF _Toc406412057 h 52HYPERLINK l _Toc4064120587、用回溯法求連續(xù)郵資問題 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!王曉東版計算機算法設(shè)計與分析第四版 P11頁，例21#include void main()long n;int JieChen(int n);printf(請輸入一個數(shù)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數(shù)列王曉東版計算機算法設(shè)計與分析第四版 P12頁，例22int Fibonacci(int n)if(n=1)return 1;elsereturn Fibonacci(n-1)+Fibonacci(n-2);void main()long n;printf(請輸入一個數(shù)n);scanf(%ld,&n);long result = Fibonacci(n);printf(%ldn,result);3、用遞歸思想求排列問題王曉東版計算機算法設(shè)計與分析第四版 P13頁，例24N個元素的全排列的個數(shù)為：N!本算法非常重要，因為它

11、是很多算法的根底，比方回溯法那章里的算法很多都是以本算法為根底的。#include / 交換兩個元素的值void Swap(int &*,int &y)int t = *;* = y;y = t;/ 產(chǎn)生listk:m的所有排列/ m 是最后一個元素在數(shù)組中的下標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); / 將元素復(fù)原void main()int a5 = 1,2,3,4,5;/ 求數(shù)組前面三個元素的全排列Perm(a,0,3);4、用遞歸思想求整數(shù)劃分問題王曉東版計算機算法設(shè)計與分析第四版 P14頁，例25整數(shù)劃分問題是算法中的一個經(jīng)典命題之一，有關(guān)這個問題的講述在講解到遞歸時根本都將涉及。所謂整數(shù)劃分，是指把一個正整數(shù)n寫成如下形式：n=m1+m2+mi; 其中mi為正整數(shù)，并且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 時，根據(jù)劃分中是否包含 n，可以分為兩種情況：(a). 劃分中包含n的情況，只有一個即 n ；(b). 劃分中不包含n的情況，這時劃分中最大的數(shù)字也一定比 n 小，即 n 的所有 ( n - 1 ) 劃分。因此 f(n, n) = 1 + f(n, n-1);(4) 當 n m 時，根據(jù)劃分中是否包含最大值 m，可以分為兩種情況：(a). 劃分中包含m的情況，即m,*1,*2, .,*i,其中*1,*2, .,*i 的和為n-m，可能再次出現(xiàn)m，因此是n-m的m劃分，因此這種劃分個數(shù)為f(n-m, m);(b). 劃分中不包含m

14、的情況，則劃分中所有值都比m小，即n的(m-1)劃分個數(shù)為f(n, m - 1);因此 f(n, m) = f(n-m, m) + f(n, m-1);綜合以上情況，我們可以看出，上面的結(jié)論具有遞歸定義特征，其中1和2屬于回歸條件，3和4屬于特殊情況，將會轉(zhuǎn)換為情況5。而情況5為通用情況，屬于遞推的方法，其本質(zhì)主要是通過減小m以到達回歸條件，從而解決問題。其遞推表達式如下：f(n, m) =1; ( n = 1 or m = 1 )f(n, m) =f(n, n); ( n m )因此我們可以給出求出 f(n, m) 的遞歸函數(shù)代碼如下。/ 求整數(shù)n的全部劃分數(shù)，其中ma*代表最大加數(shù)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、用遞歸思想實現(xiàn)插入排序#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*);方法二：用循環(huán)代替遞歸/ 在a數(shù)組里查找是否存在*這個元素，如果存在，則返回元素所在下標，如果不存在/ 則返回-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、用分治法求兩個大整數(shù)的乘法最簡單的方法，這里沒有表達分治法的思想#include int main()char a100,b100,s202;int i,j,g,t=0,k=0,temp;printf(請輸入兩個大整數(shù)，空格分隔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位上所有數(shù)字之和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、用分治思想求一個數(shù)組的最大值與最小值#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(數(shù)組里的元素為: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(數(shù)組里的元素為:n);for(int i=0;iLEN;i+)ai = rand()%100;printf(%d ,ai);*/10、用分法思想實現(xiàn)合并排序#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(原始數(shù)據(jù)為:n);for(int i=0;i9;i+)printf(%dt,ai);mergesort(a,0,8);printf(n合并后的數(shù)據(jù)為:n);for(i=0;i9;i+)printf(%dt,ai);printf(n);11、用分治思想實現(xiàn)快速排序#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為基準，將數(shù)組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排序前的結(jié)果n);for(int i=0;i9;i+)printf(%dt,ai);quicksort(a,0,8);printf(n排序后的結(jié)果n);for( i=0;i9;i+)printf(%dt,ai);printf(n);如果每次劃分不以ap為基準，而是隨機從ap-ar里取一個數(shù)為基準，則可以設(shè)計如下隨機化快速排序算法。/ 隨機選擇策略的劃分算法,需要調(diào)用partition函數(shù)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、用分治法實現(xiàn)線性時間選擇問題本算法要用到上面快速排序的隨機劃分算法int RandomizedSelect(int a,int p,int r,int k)if(p=r)/ 如果只剩下一個數(shù)，則這個肯定就是第k小的數(shù)return ap;elseint i = RandomizedPartition(a,p,r);/ 經(jīng)過快速排序進展劃分int j = i-p+1;/ 計

27、算通過劃分后，從ap到ai有多少數(shù)if(k=j)/ 第k小的數(shù)在ai的前半段return RandomizedSelect(a,p,i,k);else/ 第k小的數(shù)在ai的后半段，并且從ap到ai這些數(shù)都小于第k小的數(shù)return RandomizedSelect(a,i+1,r,k-j);13、用分法思想實現(xiàn)殘缺棋盤問題王曉東版計算機算法設(shè)計與分析第四版 P20頁，例2.6注意：同一種形狀的骨牌，在填充時數(shù)字不一樣，關(guān)鍵看三個一樣數(shù)字擺放位置所構(gòu)成的形狀。#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);第三章 動態(tài)規(guī)劃法1、矩陣連乘問題#include #include / n 矩陣的個數(shù)/ p 記錄各矩陣的維數(shù)，n個矩陣有n+1個維數(shù)，Ai的維數(shù)為pi-1,pi/ mij 記錄從第i個矩陣到第j個矩陣連乘，最小的數(shù)乘次數(shù)/ sij 記錄從第i個矩陣到第j個矩陣連乘，取最小的數(shù)乘次數(shù)時，最后兩個矩陣相乘時的位置/ 如果sij = k,則代表從第i個矩陣到第k個矩陣連乘,得到一個結(jié)果矩陣，/ 從第k+1個矩陣到第j個矩陣連乘,得到另一個結(jié)果矩陣，然后這兩個結(jié)果矩陣做最后的乘法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個矩陣鏈需要求最小數(shù)乘/ 下面的循環(huán)用來從前往后求這n-len+1個矩陣鏈的最小數(shù)乘值for(int i=1;i=n-len+1;i+)/ 求從第i個矩陣到第i+len-1個矩陣的最小數(shù)乘值int j = i+len-1;mij = mii + mi+1j +pi-1*pi*pj;/ 假設(shè)從第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;/ 當矩陣鏈相乘取最小數(shù)乘時，輸出矩陣鏈加括號的格式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為*字符串里字符的個數(shù),n為Y字符串里字符的個數(shù)/ cij代表當*取前面連續(xù)i個字符，Y取前面連續(xù)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+) / *取前面連續(xù)i個字符for(int

36、j=1;j= cij-1)cij = ci-1j;bij = 2;elsecij = cij-1;bij = 3;/ 獲取最長公共子序列符號(遞歸實現(xiàn),書本上所用的方法)int k=0;void LCS(int i,int j,char * *,int * b,char * result)if(i=0 | j=0)/ 將result里的字符反轉(zhuǎn)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為兩個動態(tài)二維數(shù)組，這樣不浪費空間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);獲取最長公共子序列符號的非遞歸實現(xià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;/此處與教材有區(qū)別，因為教材是從下標為1的元素處保存有效字符 m-;n

40、-;else if(bmn=2)m-;elsen-;/ 將result數(shù)組里的數(shù)據(jù)平移for(int i=k,j=0;i=len;i+,j+)resultj = resulti;resultj = 0; / 設(shè)置完畢字符3、最大子段和問題1分治思路實現(xiàn)改良了書本上的算法，可以求出最大子段和的起始坐標和終止坐標#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);/ 設(shè)置隨機種子for(int i=1;i=N;i+)int flag = rand()%2;/ flag為1代表正數(shù)，flag為0代表負數(shù)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動態(tài)規(guī)劃思路實現(xiàn)補充了書本上不完美的地方：在求最大子段和，隨便可以求出最大子

44、段和的起始坐標和終止坐標；在求最大子矩陣和時，可以隨便求出子矩陣的左上角和右下角坐標。#include #include #include #define N 4/ 代表列#define M 4/ 代表行/ 求最大子段和的動態(tài)規(guī)劃算法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 代表數(shù)組的行數(shù)，下標為0的行沒有使用/ n 代表數(shù)組的列數(shù)，下標為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);/ 設(shè)置隨機種子for(int i=1;i=N;i+)int flag = rand()%2;/ flag為1代表正數(shù)，flag為0代表負數(shù)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);/ 設(shè)置隨機種子for( i=1;i=M;i+)for(int j=1;j=N;j+)int flag

48、 = rand()%2;/ flag為1代表正數(shù)，flag為0代表負數(shù)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、圖像壓縮問題王曉東版計算機算法設(shè)計與分析第四版 P65頁，例3.7書本上P67頁上第一

49、行bj = bsj行錯誤，本程序修正了這個錯誤，在求每段的最大位數(shù)時，只需要從頭到位掃描一次，時間復(fù)雜度為O(n)。小有成就感_#include int length(int i)int k=1;i = i/2;while(i0)k+;i = i/2;return k;/ n 像素總個數(shù)/ pi 第i個像素點的灰度值/ si 記錄前i個像素的最小存儲空間/ li 記錄前i個像素取最小存儲空間里，最后一個分段里元素的個數(shù)/ bi 存儲第i個像素的灰度值值需要多少位void press(int n,int p,int s,int l,int b)int Lma* = 256;/ 每個分段里像素個數(shù)

50、不超過256個int header = 11;/ 每個分段里像素的頭部信息為11位s0 = 0;for(int i=1;i=n;i+)bi = length(pi);int bma* = bi; / 記錄最后一段里，各像素的所需存儲位數(shù)的最大值/ 以最后一個像素單獨作為最后一段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數(shù)組賦值，用來存儲分段位置 */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;/ 段計數(shù)器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;/ 動態(tài)分配數(shù)組存儲赫夫樹typedef char * HuffmanCode;/ 動態(tài)分配數(shù)組存儲赫夫曼編碼表/ w數(shù)組存放n個字符的權(quán)值均0，構(gòu)造赫夫曼樹HT, 并求出n個字符的赫夫曼編碼HCvoid HuffmanCoding(HuffmanTree

54、 &HT, HuffmanCode &HC,int *w,int n)if(n=1)return;int m = 2*n-1; / 整棵樹結(jié)點的個數(shù)HT = (HuffmanTree)malloc(m+1)*sizeof(HTNode);/ 構(gòu)造一個動態(tài)數(shù)組用作赫夫曼樹，其中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值最小的兩個結(jié)點，其序號分別為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);/ =從葉子結(jié)

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+)/ 求每個字符編碼，循環(huán)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+)/ 如果到達葉子結(jié)點，代表找到*一個字符，輸出這個字符，/ 并且將inde*恢復(fù)到樹根處，方便查找下一個字符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*應(yīng)當回得赫夫曼樹的樹根處printf(明文為n);resultk = 0;puts(result);elseputs(密文不正確n);/ 主函數(shù)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權(quán)值:%dt編碼為:%sn,codei,wi,HCi);sum += wi*strlen(HCi);printf(n總長度：%dn,sum);char needDecode = 10;Decoding(HT,needDecode,code,8);4、Kruskal算法求最小生成樹設(shè)有如下無向圖，求這個圖的最小生成樹。判斷兩個節(jié)點是否連通，用并查集構(gòu)造來實現(xiàn)。#inc