1、算法設計與分析課程教案課程編號：08051100課程名稱：算法設計與分析（The Design and Analysis of Computer Algorithms）學時：72學時，其中理論學時54，上機學時18學分：3.5開課部門：數學與計算機科學學院開課教研室：計算機科學開課教師：雷小園開課學期：第5學期授課班級：05計科先修課程：C+語言程序設計、數據結構考核要求：考試，平時10，實驗20，考試70使用教材：算法設計與分析基礎(第2版)，潘彥譯，清華大學出版社，2006年參考教材：算法設計與分析，呂國英主編，清華大學出版社，2005年計算機算法設計與分析(第二版)，王曉東主編，電子工業

2、出版社，2004年課程的性質和任務： 本課程是計算機科學與技術專業的專業必修課。本課程旨在培養學生分析問題和解決問題的能力，使學生掌握算法設計的基本方法，熟悉算法分析的基本技術，并能熟練運用一些常用算法，為學生進一步學習奠定良好的基礎。本課程著重于培養學生的算法設計與分析能力，程序設計和實現能力。教學目的與要求：學習掌握幾種基本的算法：減治法、分治法、動態規劃、貪心法、回溯法、分支限界法；掌握算法設計的基本思想和策略、算法優化的技巧、算法性能分析的方法；教學方法：主要板書講解算法、程序，輔助多媒體演示程序的運行，上機練習算法編程。第3章 蠻力法3.1 選擇排序和冒泡排序1、選擇排序void S

3、electSort(int a, int n) int i,j,k,m; for(i=0; i<n-1; i+) m = i; for(j=i+1; j<n; j+) if(aj <am) m = j; swap(ai, am); 2、冒泡排序void bubble(int a, int n) int i,j,t; for(i=0; i<n-1; i+) for(j=0; j<n-i-1; j+) if( aj>aj+1 ) swap(aj,aj+1);3.2 順序查找和蠻力字符串匹配1、順序查找int Search(int a, int n, int k)

4、 for(int i=0; i<n; i+) if(ai=k) return i; return -1;int Search(int a, int n, int key) int i=0; while(i<n && ai!=k) i+; if(i<n) return i; else return -1;2、蠻力字符串匹配給定一個n個字符組成的串，稱為文本，一個m個字符的串，稱為模式，從文本中尋找匹配模式的串。int StringMatch(char *t, char *p) int n=strlen(t), m=strlen(p); for(i=0; i<

5、;=n-m; i+) int j=0; while(j<m && pj=ti+j) j+; if(j=m) return i; return -1; 3.3 最近對和凸包問題的蠻力算法1、最近對問題最近對問題要求找出一個包含n個點的集合中距離最近的兩個點。2、凸包問題對于平面上n個點的集合，它的凸包就是包含所有這些點的最小凸多邊形。3.4 窮舉查找1、旅行商問題一個旅行商到n個城市去進行銷售，找出一條代價最小的周游路線。2、背包問題給定n個物品和一個背包，物品i的重量為wi,其價值為v1i，背包的承重為W，應如何選擇物品，使得裝入背包中物品的總價值最大。3、分配問題有n件

6、工作要分配給n個人去完成，將工作i分配給第j個人所需的費用為Cij，找出總成本最小的分配方案。補充例題1、數字全排列（直接的方法）int main() int a4=1,2,3,4,m4; for(int i1=0;i1<4;i1+) m0=ai1; for(int i2=0;i2<4;i2+) m1=ai2; if(m1=m0)continue; for(int i3=0;i3<4;i3+) m2=ai3; if(m2=m1 | m2=m0)continue; for(int i4=0;i4<4;i4+) m3=ai4; if(m3=m0 | m3=m1 | m3=m

7、2)continue; for(int k=0;k<4;k+) cout<<mk<<" " cout<<endl; 2、數字全排列（使用STL）#include<iostream>#include<algorithm>using namespace std;const int n=4;int main() int a4=2,4,3,1; sort(a,a+n); do for(int i=0; i<n; i+) cout<<ai<<" " cout<&l

8、t;endl; while(next_permutation(a,a+n);3、數字全排列（遞歸方法）template <class T>void Perm(T a,int k,int m) if(k=m) for(int i=0;i<=m;i+) cout<<ai<<" " cout<<endl; else for(int i=k;i<=m;i+) swap(ak,ai); Perm(a,k+1,m); swap(ak,ai); int main() int a4=1,2,3,4; Perm(a,0,3);第4章

9、 分治法4.1 合并排序void Merge(int a, int b, int l, int m, int n) /將alam和am+1an合并到blbn int i=l, j=m+1, k=l; while(i<=m && j<=n) if(ai<=aj) bk+ = ai+; else bk+ = aj+; while(i<=m) bk+ = ai+; while(j<=n) bk+ = aj+;void Msort( int a, int b, int s, int t ) / 將as.t進行2-路歸并排序，利用b數組。 if (s=t)

10、return; int m = (s+t)/2; / 將as.t平分為as.m和am+1.t Msort(a, b, s, m); Msort(a, b, m+1, t); Merge(a, b, s, m, t); / 將as.m和am+1.t歸并到bs.t for(int i=s; i<=t; i+) ai = bi; void MergeSort(int a, int n) int bn; Msort(a, b, 0, n-1);4.2 快速排序4.3 折半查找4.4 二叉樹遍歷及其相關特性4.5 大整數乘法和Strassen矩陣乘法4.6 用分治法解決最近對問題和凸包問題例：在n

11、個元素中找最大值template<class T>int Max(T a, int l, int r) if(l=r) return al; int m = (l+r)/2; T max1,max2; max1 = Max(a, l, m); max2 = Max(a, m+1, r); if(max1>max2) return max1; else return max2;例：在n個元素中找最大值和最小值template<class T>void MaxMin(T a, int l, int r, T &max, T &min) if(l=r)

12、max = min = al; return; if(l=r-1) if(al>ar) max=al; min=ar; else max=ar; min=al; return; int m = (l+r)/2; T max1,max2,min1,min2; MaxMin(a, l, m, max1, min1); MaxMin(a, m+1, r, max2, min2); max = max1>max2 ? max1 : max2; min = min1<min2 ? min1 : min2;int main() const int N=20; int aN, i, max

13、, min; srand(time(0); for(i=0; i<N; i+) ai = rand() % 1000; for(i=0; i<N; i+) cout<<ai<<" " cout<<endl; MaxMin(a,0,N-1,max,min); cout<<"max="<<max<<", min="<<min<<endl;例：在n個元素中找最大值和最小值（非遞歸程序）template<class T>vo

14、id MaxMin(T a, int n, T& max, T&min) if(n=1) max=min=a0; return; if(a0>a1) max=a0; min=a1; else max=a1; min=a0; int i; for(i=2; i<n-1; i+=2) if(ai>ai+1) if(ai>max) max=ai; if(ai+1<min) min=ai+1; else if(ai+1>max) max=ai+1; if(ai<min) min=ai; if(i<n) if(ai>max) max=

15、ai; if(ai<min) min=ai; 例：棋盤覆蓋問題#include <iostream>#include <iomanip>using namespace std;int tile; /L型骨牌編號int *Board;void Cover(int tr,int tc,int dr,int dc,int size) /棋盤覆蓋函數 if(size=1) return; /如果棋盤規模=1，返回 int s=size/2; /分割棋盤 int t=+tile; /L型骨牌編號加1 /處理左上角子棋盤 if(dr < tr+s &&

16、dc < tc+s) Cover(tr,tc,dr,dc,s); else Boardtr+s-1tc+s-1=t; Cover(tr,tc,tr+s-1,tc+s-1,s); /處理右上角子棋盤 if(dr < tr+s && dc >= tc+s) Cover(tr,tc+s,dr,dc,s); else Boardtr+s-1tc+s=t; Cover(tr,tc+s,tr+s-1,tc+s,s); /處理左下角子棋盤 if(dr >= tr+s && dc < tc+s) Cover(tr+s,tc,dr,dc,s); el

17、se Boardtr+stc+s-1=t; Cover(tr+s,tc,tr+s,tc+s-1,s); /處理右下角子棋盤 if(dr >= tr+s && dc >= tc+s) Cover(tr+s,tc+s,dr,dc,s); else Boardtr+stc+s=t; Cover(tr+s,tc+s,tr+s,tc+s,s); int main() int x,y; /階數及特殊點位置 int i,j,n; /棋盤規模為 n*n cin>>n>>x>>y; /讀入階數k和特殊方格位置 /在堆內存中建立棋盤數組，填充特殊方格

18、 Board=new int*n; for (i=0;i<n;i+ ) Boardi=new intn; Boardx-1y-1=0; tile=0; Cover(0,0,x-1,y-1,n); /進行棋盤覆蓋,左上角位置0,0; 棋盤寬度n; 特殊點x,y /輸出到屏幕 for (i=0;i<n;i+) for (j=0;j<n;j+ ) cout << setw(4) << Boardij; cout << endl; /釋放內存 for(i=0;i<n;i+) delete Boardi; delete Board;第5章 減治

19、法5.1 插入排序5.2 深度優先查找和廣度優先查找5.3 拓撲排序5.4 生成組合對象的算法例：數字全排列#include<iostream>using namespace std;template <class T>void Perm(T a,int n) for(int i=0; i<n; i+) cout<<ai<<" " cout<<endl; for(;) int m=n-2; while(m>=0 && am>am+1) m-; /從右向左找到2個相鄰數滿足am<

20、;am+1 if(m<0) return; int k=n-1; while(am>ak) k-; /從右向左找到第一個大于am的數ak swap(am,ak); int p=m+1, q=n-1; while(p<q) /將am以后的數顛倒 swap(ap+,aq-); for(int i=0; i<n; i+) cout<<ai<<" " cout<<endl; int main() int a4=1,2,3,4; Perm(a,4);5.5 減常因子算法5.6 減可變規模算法例：求第K小的數int Parti

21、tion(int a, int low, int high) int i=low, j=high+1, x=alow, t; while(i < j) do i+; while(ai<x); do j-; while(aj>x); if(i<j) t=ai; ai=aj; aj=t; alow = aj; aj = x; return j;int Select(int a, int low, int high, int k) int i=Partition(a, low, high); int j=i-low+1; if(k=j) return ai; else if(

22、k<j) return Select(a, low, i-1, k); else return Select(a, i+1, high, k-j);例：組合，按字典順序列舉1,2,n的所有r組合int a4;void Combination(int r, int n) for(int i=0; i<r; i+) ai=i+1; /打印第一個r組合 for(int i=0; i<r; i+) cout<<ai<<" " cout<<endl; for(;) int m=r-1, max=n; while(m>=0 &

23、amp;& am=max) /從右向左找到第一個非該位置最大值的元素 m-; max-; if(m<0) return; am+; for(int i=m+1; i<r; i+) ai = ai-1+1; for(int i=0; i<r; i+) cout<<ai<<" " cout<<endl; int main() Combination(4,6); 例：組合，列舉1,2,n的所有r組合，遞歸算法，反字典順序const int N=5,R=3;int aR; void comb(int r,int n) f

24、or (int i=n;i>=r;i-) ar-1=i; if (r>1) comb(r-1,i-1); else for (int j=R-1;j>=0;j-) cout<<aj<<" " cout<<endl; int main() comb(R,N); 第6章 變治法6.1 預排序6.2 高斯消去法6.3 平衡查找樹6.4 堆和堆排序6.5 霍納法則和二進制冪例：計算anint Power(int a, int n) / 計算a的n次方 int k = 1; / k用來計算“剩下的”乘積 while ( n >

25、; 1 ) / 一直計算到指數小于或等于1 if ( ( n & 1 ) != 0 ) k *= a;/ 若n是奇數，則把“剩下的”乘起來 a *= a; / 主體乘方 n /= 2; / 指數除以2 return a * k; / 最后把主體和“剩下的”乘起來作為結果6.6 問題化簡例：計算最小公倍數int lcm(int m, int n) int t,s; if(m<n) t=m; m=n; n=t; s=m; while(s%n != 0) s=s+m; int lcm(int m, int n) return m*n/gcd(m,n); 第7章 時空權衡7.1 計數排序

26、例：比較計數法排序void ComparisonCountingSort(int a, int n) int *count = new intn; int *b = new intn; for(int i=0; i<n; i+) counti=0; for(int i=0; i<n-1; i+) for(int j=i+1; j<n; j+) if(ai>aj) counti+; else countj+; for(int i=0; i<n; i+) bcounti=ai; for(int i=0; i<n; i+) ai=bi;例：分布排序void Dis

27、tributionCountingSort (int a, int n, int l, int u) /分布計數法排序，對n個值為lu的數進行排序 int i, j; int *d = new intu-l+1; int *b = new intn; for(j=0; j<=u-l; j+) dj = 0; for(i=0; i<n; i+) dai-l+; for(j=1; j<=u-l; j+) dj = dj-1 + dj; for(i=n-1; i>=0; i-) j = ai - l; bdj-1 = ai; dj-; for(int i=0; i<n;

28、 i+) ai = bi;7.2 字符串匹配中的輸入增強技術7.2.1 Horspool算法例：7.3 散列法7.4 B樹第8章 動態規劃Fibonacci數列問題求Fibonacci數列的第n項。(1) 遞歸法int Fib(int n) if(n=1 | n=2) return 1; return Fib(n-1) + Fib(n-2);(2) 遞推法int Fib(int n) int f,f1,f2; f1 = f2 = 1; for(int i=3; i<=n; i+) f = f1 + f2; f1 = f2; f2 = f; return f;(3) 動態規劃方法int f

29、100;int Fib(int n) f1=f2=1; for(int i=3; i<=n; i+) fi = fi-1 +fi-2; return fn;(4) 備忘錄方法int f100;int Fib(int n) if(fn>0) return fn; if(n=1 | n=2) return 1; fn = Fib(n-1) + Fib(n-2); return fn;8.1 計算二項式系數二項式公式為 (a+b)n = C(n,0)an + + C(n,k)an-kbk + + C(n,n)bn其中C(n,k)為二項式系數 (a+b)n-1 = C(n-1,0)an-1

30、 + + C(n-1,k-1)an-kbk-1 + C(n-1,k)an-k-1bk + + C(n-1,n-1)bn-1由(a+b)n = (a+b)(a+b)n-1 可得：(1)計算二項式系數的遞歸函數為int C(int n,int k) if(k=0|n=k) return 1; return C(n-1,k-1)+C(n-1,k);但用這種遞歸方法效率非常低（計算C(32,20)都用了好幾秒鐘）。(2)用動態規劃來求二項式系數int m100100;int C(int n,int k) for(int i=0; i<=n; i+) mi0 = mii = 1; for(int

31、i=1; i<=n; i+) for(int j=1; j<i; j+) mij = mi-1j-1 + mij-1; return mnk;(3)用備忘錄方法來求二項式系數int m100100=0;int C(int n,int k) if(mnk=0) if(k=0|n=k) mnk = 1; else mnk = C(n-1,k-1)+C(n-1,k); return mnk;8.2 Warsgall算法和Floyd算法8.2.1 Warsgall算法8.2.2 計算完全最短路徑的Floyd算法8.3 最優二叉查找樹8.4 背包問題和記憶功能8.4.1 背包問題0-1背包問

32、題：給定n種物品和一個背包，物品i的重量為wi，其價值為vi，背包的容量為c。問如果選擇物品裝入背包，使得物品的總價值最大。物品的重量為：w= w1,w2,wi,wn，價值為：v= v1,v2,vi,vn，背包容量為c。設f(i,j)表示剩余容量為j，剩余物品為i,i+1,n時的最優解的值，則有fn,j= vn, jwn 0, 0j<wnfi, j= max fi+1, j, fi+1, j-wi +vi jwi fi+1, j 0j<wi例：設n=5，c=10，w=2,2,6,5,4，v=6,3,5,4,6，問題求解過程示意圖如下：(2,10)f(1,10)(2,8)(3,10)

33、(3,6)(4,10)(4,4)(5,10)(4,6)(4,2)(5,5)(5,4)(5,2)(5,3)(3,8)(4,8)(5,8)(4,2)(5,3)(4,2)(3,8)(4,8)(4,0)(5,8)(5,6)(5,1)(5,0)例：0/1背包問題的遞歸解法#include<iostream> using namespace std; int n=5,w=0,2,2,6,5,4,v=0,6,3,5,4,6;int f(int i, int j) if(i=n) return j<wn ? 0 : vn; if(j<wi) return f(i+1, j); retu

34、rn max( f(i+1,j), f(i+1,j-wi)+vi );例：用動態規劃解決0/1背包問題012345678910115200336699910113000066666101140000666661010500006666666#include<iostream> using namespace std; float m100100;void Knapsack(float v,int w,int c,int n) int i,j,jmax; jmax = min(wn-1, c); for(j=0;j<=jmax;j+) mnj=0; for(j=wn;j<

35、=c;j+) mnj=vn; for(i=n-1;i>1;i-) jmax = min(wi-1, c); for(j=0;j<=jmax;j+) mij=mi+1j; for(j=wi;j<=c;j+) mij=max(mi+1j, mi+1j-wi+vi); m1c=m2c; if(c>=w1) m1c=max(m1c, m2c-w1+v1);void traceback(int w,int c,int n,int x) for(int i=1;i<n;i+) if(mic=mi+1c) xi=0; else xi=1; c-=wi; xn=mnc?1:0;i

36、nt main() float v=0,6,3,5,4,6; int c=10,n=5,w=0,2,2,6,5,4, x6; Knapsack(v,w,c,n); traceback(w,c,n,x); cout<<"the max value is: " << m1c << endl; for(int i=1;i<=n;i+) cout << xi <<" " return 0;8.4.2 記憶功能例：0/1背包問題的備忘錄解法#include<iostream> using

37、 namespace std; float m100100=-1;int n=5,w=0,2,2,6,5,4,v=0,6,3,5,4,6;int f(int i, int j) if(mij=-1) if(i=n) mij = j<wn ? 0 : vn; else if(j<wi) mij = f(i+1, j);else mij = max( f(i+1,j), f(i+1,j-wi)+vi );return mij;8.4.3 找零錢問題有n種不同面值的硬幣，各種硬幣的面值存于數組an中，要求用最少的硬幣來找零錢。設C(i)為找錢數為i時的最少硬幣個數，則有：C(i) = m

38、in C(i-aj) + 1 i>0, 1jn, i-aj0C(0) = 0設有4種硬幣：面值分別為1、5、10、25，要找的錢為62，則有01234567891011121314151617181920012341234512345234562212223242526272829303132333435363738394041345612345345672345634424344454647484950515253545556575859606162567345672345634567345例：找零錢問題的動態規劃解法#include<iostream> using nam

39、espace std; void coin(int n, int m, int a, int c) c0=0; for(int i=1;i<=m;i+) int min=m; for(int j=1;j<=n;j+) if( i>=aj && ci-aj<min ) min=ci-aj; ci=min+1; int main() int m=63; int a=0,25,10,5,1, cm+1; coin(4,m,a,c); cout<<cm; return 0;找零錢問題的另一解法設C(i,j)表示可用硬幣為i,i+1,n、找錢數為j時的

40、所兌換的最少硬幣個數，則有：C(i,0) = 0;設有4種硬幣：面值分別為1、5、10、25，要找的錢為62，則有012345678910115200336699910113000066666101140000666661010500006666666第9章 貪婪技術1、找零錢問題：例：找零錢問題的貪婪算法#include<iostream> using namespace std; int Coins(int n, int m, int a, int x) int i, k=0, c=m; for(i=1; i<=n; i+) xi=0; i=1; while(i<=

41、n && c>0) if(c>=ai) c-=ai; k+; xi+; else i+; if(c=0) return k; else return 0;其中while循環可改為： while(i<=n && c>0) xi = c / ai; c -= xi*ai; k += xi; i+; int main() int a=0,25,10,5,1, x5; cout<<Coins(4,63,a,x)<<endl; for(int i=1; i<=4; i+) cout<<xi<<&

42、quot; " return 0;2、背包問題：與0-1背包問題類似，所不同的是，可以選擇物品i的一部分裝入背包。void Knapsack(float w, float v,float x,float c,int n) sort(w,v,n); int i; for(i=1; i<=n; i+) xi=0; for(i=1; i<=n; i+) if(wi>c) break; xi = 1; c -= wi; if(i<=n) xi = c / wi;其中for循環也可改為：i = 1while(i<=n && wi<=c) xi

43、 = 1; c -= wi; i+;程序設計練習：撲克牌發牌一副撲克牌有52張牌（去掉大小鬼），發給4個人，打印出每個人得到的牌。先來看一個簡單問題：從52個數里選13個數。算法1： for(i=0; i<13; i+) k = rand() % 52; bi = ak; 這個算法是錯誤的，會導致抽取同一個數。 算法2： for(i=0; i<13; i+) do k = rand() % 52; dup = 0; for(j=0; j<i; j+) if(ak=bj) dup = 1; break; while( dup = 1 ); bi = ak; 這個算法，每抽取一個

44、數，就檢查前面是否抽過這個數，如果抽過則重抽。這算法效率很低。算法3： for(i=0; i<13; i+) do k = rand() % 52; while(ak=0); bi = ak; ak = 0; 這個算法，每抽取一個數，就將此數做個標志，下次如果再抽到這個數，就馬上再去重抽，避免了上例的檢查。比上面的大大改進了，但還是效率很低。算法4： for(i=0; i<13; i+) k = rand() % (52 - i); bi = ak; for(j=k; j<51-i; j+) aj = aj+1; 這個算法，每抽一個數，就將后面的數往前移一位，這樣就避免了重復

45、抽數，比前面的效率高，但需要大量移動數，也導致效率不高。算法5： for(i=0; i<13; i+) k = rand() % (52-i); bi = ak; swap(ak,a51-i); 這個算法，既不檢查重復情況，也不重復抽數，又不需要移動數據，是最好的算法。例：撲克牌發牌程序#include <iostream>using namespace std;void show(int k) switch (k-1)/13) case 0: cout<<char(5);break; case 1: cout<<char(4);break; case

46、 2: cout<<char(3);break; case 3: cout<<char(6);break; if(k%13=11) cout<<"J" else if(k%13=12) cout<<"Q" else if(k%13=0) cout<<"K" else if(k%13=1) cout<<"A" else cout<<k%13; int main() int i, k, a52; for(i=0; i<52; i+

47、) ai=i+1; srand(time(0); for(i=0; i<52 ; i+) k=rand()%(52-i); swap(ak,a51-i); for(i=0; i<52; i+) show(ai); cout<<" " if(i+1)%13=0) cout<<endl; 例：撲克牌發牌程序（C+面向對象解法）#include <iostream>using namespace std;enum Suit club, diamond, heart, spade;/enum Rank two = 2, three, four, five, six, seven, eight, nine, ten