算法設(shè)計(jì)與分析復(fù)習(xí)題

1、算法設(shè)計(jì)與分析復(fù)習(xí)題1一個(gè)算法應(yīng)有哪些主要特征？另附資料2分治法（Divide and Conquer）與動(dòng)態(tài)規(guī)劃（Dynamic Programming）有什么不同？另附資料3試舉例說(shuō)明貪心算法對(duì)有的問(wèn)題是有效的，而對(duì)一些問(wèn)題是無(wú)效的。另附資料4編寫(xiě)一個(gè)遞歸算法求解Hanoi 塔問(wèn)題。Void Hanoi(int n,int first,int second,int third) If(n=1)Move(first,third);Else Hanoi(n-1,first,third,second);Move(first,third);Hanoi(n-1,second,first,second

2、);5求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。6求解方程T(n)=2T(n/2)+1，T(1)=1，設(shè)n=2k。7求解方程T(n)=aT(n/b)+n，T(1)=1，設(shè)n=2k。另附資料8編寫(xiě)一個(gè)Quick Sorting 算法，并分析時(shí)間復(fù)雜性。9利用Quick Sorting的原理，編寫(xiě)一個(gè)查找第k小元素的算法。10編寫(xiě)一個(gè)Heap Sorting算法，并分析時(shí)間復(fù)雜性。另附資料上有部分具體實(shí)現(xiàn)代碼：11證明O(nlogn)是“比較”排序算法時(shí)間復(fù)雜性的下界。證明O(nlogn)是“比較”排序算法時(shí)間復(fù)雜性的下界。為了證明只用到比較的排序算法最低時(shí)間復(fù)雜度是O

3、(nlogn)，首先要引入決策樹(shù)。首先決策樹(shù)是一顆二叉樹(shù)，每個(gè)節(jié)點(diǎn)表示元素之間一組可能的排序，它予以京進(jìn)行的比較相一致，比較的結(jié)果是樹(shù)的邊。先來(lái)說(shuō)明一些二叉樹(shù)的性質(zhì)，令T是深度為d的二叉樹(shù)，則T最多有2片樹(shù)葉。具有L片樹(shù)葉的二叉樹(shù)的深度至少是logL。所以，對(duì)n個(gè)元素排序的決策樹(shù)必然有n!片樹(shù)葉（因?yàn)閚個(gè)數(shù)有n!種不同的大小關(guān)系），所以決策樹(shù)的深度至少是log(n!)，即至少需要log(n!)次比較。而log(n!)=logn+log(n-1)+log(n-2)+.+log2+log1=logn+log(n-1)+log(n-2)+.+log(n/2)=(n/2)log(n/2)=(n/2)l

4、ogn-n/2=O(nlogn)所以只用到比較的排序算法最低時(shí)間復(fù)雜度是O(nlogn)。贊12編寫(xiě)一個(gè)Radix算法對(duì)n個(gè)相同長(zhǎng)度的整數(shù)排序。int maxbit(int data,int n) /輔助函數(shù)，求數(shù)據(jù)的最大位數(shù) int d = 1; /保存最大的位數(shù) int p =10; for(int i = 0;i = p) p *= 10; +d; return d; void radixsort(int data,int n) /基數(shù)排序 int d = maxbit(data,n); int * tmp = new intn; int * count = new int10; /計(jì)數(shù)

5、器 int i,j,k; int radix = 1; for(i = 1; i= d;i+) /進(jìn)行d次排序 for(j = 0;j 10;j+) countj = 0; /每次分配前清空計(jì)數(shù)器 for(j = 0;j n; j+) k = (dataj/radix)%10; /統(tǒng)計(jì)每個(gè)桶中的記錄數(shù) countk+; for(j = 1;j = 0;j-) /將所有桶中記錄依次收集到tmp中 k = (dataj/radix)%10; tmpcountk-1 = dataj; countk-; for(j = 0;j n;j+) /將臨時(shí)數(shù)組的內(nèi)容復(fù)制到data中 dataj = tmpj;

6、 radix = radix*10; delete tmp; delete count; 13編寫(xiě)一個(gè)算法，可以檢測(cè)一個(gè)字符串是否回文（如：afaddafa，abwba等）。14如果是檢測(cè)一個(gè)字符串中是否包含一個(gè)回文子串，應(yīng)如何編寫(xiě)算法。如果是找最大的回文子串呢？15設(shè)n個(gè)不同的整數(shù)排好序后存在數(shù)組T1：n中。若存在一個(gè)下標(biāo)i，使得Ti=i，設(shè)計(jì)一個(gè)有效的算法找到該下標(biāo)。要求時(shí)間復(fù)雜性是O(logn)。16編寫(xiě)一個(gè)采用KMP的算法查找T的子串P，并判斷匹配失敗的字符是否在P中，以此確定可滑動(dòng)的最大距離。17編寫(xiě)一個(gè)算法找出2個(gè)正文中的最長(zhǎng)公共子序列，若要找出3個(gè)正文中的最長(zhǎng)公共子序列，應(yīng)如何編

7、寫(xiě)算法。18編寫(xiě)一個(gè)求解8后問(wèn)題的算法，并作出時(shí)間復(fù)雜性分析。19試分析回溯法與分支定界法的異同之處。20采用分支定界法編寫(xiě)一個(gè)求解貨郎擔(dān)問(wèn)題的算法，并作出算法時(shí)間復(fù)雜性分析。21假設(shè)有k種不同面值的硬幣（以元為單位，每種的個(gè)數(shù)不限）。編寫(xiě)一個(gè)用最少的硬幣數(shù)找出n元錢(qián)的算法，并分析算法的時(shí)間復(fù)雜性。#include int main()int change;coutchange;cout找給顧客的五角硬幣個(gè)數(shù)為：change/50endl;change=change%50;cout找給顧客的壹角硬幣個(gè)數(shù)為：change/10endl;change=change%10;cout找給顧客的伍分硬幣

8、個(gè)數(shù)為：change/5endl;change=change%5;cout找給顧客的貳分硬幣個(gè)數(shù)為：change/2endl;change=change%2;cout找給顧客的壹分硬幣個(gè)數(shù)為：changeendl;return 0;22考慮一個(gè)“模糊”的算法查找T的子串P，先快速找到與P相似的子串，再進(jìn)一步確認(rèn)之。23設(shè)計(jì)一個(gè)算法確定K個(gè)矩陣相乘的最優(yōu)次序，并分析該算法的時(shí)間復(fù)雜性。方法一：動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，動(dòng)態(tài)規(guī)劃法經(jīng)分解得到的子問(wèn)題往往不是相互獨(dú)立的，前一子問(wèn)題的解為后一子問(wèn)題的解提供有

9、用的信息，可以用一個(gè)表來(lái)記錄所有已解決的子問(wèn)題的答案，不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。 本實(shí)驗(yàn)的算法思路是： 1、計(jì)算最優(yōu)值算法MatrixChain()：建立兩張表（即程序中的*m和*s，利用二維指針存放），一張表存儲(chǔ)矩陣相乘的最小運(yùn)算量，主對(duì)角線上的值為0，依次求2個(gè)矩陣、3個(gè)矩陣、直到n個(gè)矩陣相乘的最小運(yùn)算量，其中每次矩陣相乘的最小運(yùn)算量都在上一次矩陣相乘的最小運(yùn)算量的基礎(chǔ)上求得，最后一次求得的值即為n個(gè)矩陣相乘的最小運(yùn)算量；另一張表存儲(chǔ)最優(yōu)斷開(kāi)位置。 2、輸出矩陣結(jié)合方式算法Traceback()：矩陣結(jié)合即是給矩陣加括號(hào)，打印出矩陣結(jié)合方式，由遞歸過(guò)程

10、Traceback()完成。分三種情況： （1）只有一個(gè)矩陣，則只需打印出A1； （2）有兩個(gè)矩陣，則需打印出（A1A2）； （3）對(duì)于矩陣數(shù)目大于2，則應(yīng)該調(diào)用遞歸過(guò)程Traceback()兩次，構(gòu)造出最優(yōu)加括號(hào)方式。 三、實(shí)驗(yàn)源程序 建立一個(gè)矩陣的類Matrix。 Matrix.h代碼#ifndef MATRIX_H #define MATRIX_H class Matrix public: Matrix(); /構(gòu)造函數(shù) Matrix(); /析構(gòu)函數(shù) bool Run(); /運(yùn)行接口函數(shù) private: int W; /記錄矩陣的個(gè)數(shù) int *m; /存放最優(yōu)值，即最小運(yùn)算量 i

11、nt *s; /斷開(kāi)位置 int *p; /存放 bool Input(); /處理輸入 bool MatrixChain();/計(jì)算最優(yōu)值算法 void Traceback(int i,int j,int *s); /輸出矩陣加括號(hào)的方式 ; #endif Matrix.cpp代碼#define N 50 #include #include #include Matrix.h /構(gòu)造函數(shù)，作變量初始化工作，為指針?lè)峙鋬?nèi)存空間 Matrix:Matrix() W=0; m = new int*N; s = new int*N; for(int i=0; iN ; i+) mi = new in

12、tN; si = new intN; p = new intN; /析構(gòu)函數(shù)，釋放內(nèi)存 Matrix:Matrix() for(int i=0; iN ; i+) delete mi; delete si; delete m; delete s; delete p; /處理鍵盤(pán)輸入 bool Matrix:Input() int w; coutw; W = w; cout輸入矩陣A1維數(shù)p0p1; for(int i=2 ; i=W ; i+) int m = pi-1; cout輸入矩陣Aipi-1pi; if(pi-1 != m) coutendl維數(shù)不對(duì)，矩陣不可乘！endl; exit

13、(1); /coutendl; if(p!=NULL) return true; else return false; /計(jì)算最優(yōu)值算法 bool Matrix:MatrixChain() if(NULL = p) return false; for(int i=1;i=W;i+) mii=0; for(int r=2;r=W;r+) for(int i=1;i=W-r+1;i+) int j=i+r-1; mij = mi+1j + pi-1*pi*pj; sij = i; for(int k=i+1;kj;k+) int t = mik + mk+1j + pi-1*pk*pj; if(t

14、mij) mij = t; sij = k; return true; /輸出矩陣結(jié)合方式，加括號(hào) void Matrix:Traceback(int i,int j,int *s) if(i = j) coutAi; else if(i+1 = j) cout(AiAj); else cout(; Traceback(i,sij,s); Traceback(sij+1,j,s); cout); bool Matrix:Run() if(Matrix:Input() if(Matrix:MatrixChain() Matrix:Traceback(1,W,s); cout=j) return

15、i; else return j;int Min(int i,int j)if(i=j)return j;else return i;struct point fun1(int offset,int end,int n)/傳入?yún)?shù)為查找下限，上限，注意上限下標(biāo)不在查找范圍內(nèi)struct point temp, temp1,temp2;if(n=2) temp.max=Max(arrayoffset,arrayend-1);temp.min=Min(arrayoffset,arrayend-1);return temp;elsetemp1=fun1(offset,(offset+end)/2,n

16、/2);/每次規(guī)模減半temp2=fun1(offset+end)/2,end,n/2); temp.max=Max(temp1.max,temp2.max);temp.min=Min(temp1.min,temp2.min);return temp;void main() struct point a1,a2;int i,n;for(i=0;i50;i+) arrayi=0;printf(Input the total n=:n);scanf(%d,&n);printf(Input the numbers:n);for(i=0;in;i+)scanf(%d,&arrayi);a1=fun1(

17、0,n,n);printf(Max=%dnMin=%dn,a1.max,a1.min);方法二：25用分治法一個(gè)算法從數(shù)A1：n中同時(shí)找出最大元素，分析算法的時(shí)間復(fù)雜性，并思考為什么是這樣的結(jié)果。同上26在一個(gè)數(shù)組中出現(xiàn)次數(shù)最多的元素稱為“眾數(shù)”，編寫(xiě)一個(gè)找出眾數(shù)的算法，并分析算法時(shí)間復(fù)雜性。int most(int a,int length) /length數(shù)組長(zhǎng)度int i,j,k;int max,value;int num100100;num00=a0;num01=1;j=0;for(i=1;ilength;i+)for(k=0;kj)j+;numj0=ai;numj1=1;max=0;

18、for(k=;kmax)max=numk1;value=numk0;return value; /出現(xiàn)次數(shù)最多的數(shù)字27設(shè)計(jì)一個(gè)使用Hash法的算法在數(shù)組中找出“眾數(shù)”，并分析時(shí)間復(fù)雜性。#include #include #define N 100010 using namespace std; int aN; int main() int test; scanf(%d,&test); while(test-) int n; scanf(%d,&n); int i,t; for(i=0;iN;i+) ai=0; for(i=0;in;i+) scanf(%d,&t); at+; int p,

19、ans=0; for(i=0;ians) p=i; ans=ai; printf(%d %dn,p,ans); return 0; 28設(shè)計(jì)一個(gè)時(shí)間復(fù)雜性不超過(guò)O(n2)的算法，找出n個(gè)數(shù)組成的序列中最長(zhǎng)的單調(diào)遞增序列?！驹O(shè)計(jì)原理】將數(shù)組a復(fù)制到數(shù)組x,先用排序算法將數(shù)組x排序，在調(diào)用查找最長(zhǎng)公共子序列的算法求出數(shù)組a和數(shù)組x中的最長(zhǎng)公共子序列，因?yàn)閿?shù)組x是單調(diào)遞增的，所以由此求出來(lái)的最長(zhǎng)公共子序列就是題設(shè)所求的最長(zhǎng)單調(diào)遞增子序列?！靖乓O(shè)計(jì)】數(shù)據(jù)：N：數(shù)組元素個(gè)數(shù)。aN：用于存放數(shù)組。XN：復(fù)制數(shù)組aN，并排序。cij：存儲(chǔ)a和x的最長(zhǎng)公共子序列的長(zhǎng)度。bij：記錄cij的值是由哪一個(gè)資問(wèn)題

20、的解得到的。函數(shù)：int Partition(int a,int p,int t,int x);/數(shù)組劃分，將小于等于x的元素移到x左邊，大于x的元素移到x右邊。void Swap(int &x,int &y);/交換元素x和yvoid QuickSort(int a,int p,int r);/快速排序。void LCSL(int m,int n,int *x,int *y,int *c,int *b);/計(jì)算最長(zhǎng)公共子序列長(zhǎng)度。void LCS(int i,int j,int *x,int *b);根據(jù)bij的內(nèi)容打印a,x數(shù)組的最長(zhǎng)公共子序列?！驹敿?xì)設(shè)計(jì)】#include#include

21、using namespace std; #define N 10void LCSL(int m,int n,int *x,int *y,int *c,int *b);/計(jì)算最長(zhǎng)公共子序列長(zhǎng)度。void LCS(int i,int j,int *x,int *b);/根據(jù)bij的內(nèi)容打印a,x數(shù)組的最長(zhǎng)公共子序列。void QuickSort(int a,int p,int r);/快速排序。int Partition(int a,int p,int t);/數(shù)組劃分，將小于等于x的元素移到x左邊，大于x的元素移到x右邊。void Swap(int &x,int &y);/交換元素x和y。/計(jì)

22、算最長(zhǎng)公共子序列長(zhǎng)度void LCSL(int m,int n,int *x,int *y,int cN,int bN)c00=0;int i,j;for(i=1;i=m;i+) ci0=0;for(i=1;i=n;i+) c0i=0; for(i=1;i=m;i+) for(j=1;j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; coutcmmendl;/根據(jù)bij的內(nèi)容打印a,x數(shù)組的最長(zhǎng)公共子序列void LCS(int i,int j,int *x,int bN) if(i=0|j=0) return; if(bij=1) LCS(i

23、-1,j-1,x,b); for(int y=1;yi;y+) if(xy=xi) return; coutxi ;else if(bij=2) LCS(i-1,j,x,b);else LCS(i,j-1,x,b);void QuickSort(int a,int p,int r)if(pr) int q=Partition(a,p,r); QuickSort(a,p,q-1);/對(duì)左半段排序 QuickSort(a,q+1,r);/對(duì)右半段排序int Partition(int a,int p,int r)int i=p, j=r+1;int x=ap;/將x的元素交換到右邊區(qū)域while(

24、true) while(a-jx); while(ij)&a+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(void) int *a,*x; a=new intN; x=new intN; int bNN; int cNN; cout請(qǐng)輸入十個(gè)數(shù)：endl; for(int i=1;iai; xi=ai; QuickSort(x,1,N-1); LCSL(N-1,N-1,a,x,c,b); LCS(N-1,N-1,a,b);此方法的算法復(fù)雜性應(yīng)為

25、O(nlogn)29從1，2，n中找出所有質(zhì)數(shù)，設(shè)計(jì)一個(gè)較優(yōu)的算法。方法一：由于一個(gè)合數(shù)總是可以分解成若干個(gè)質(zhì)數(shù)的乘積，那么如果把質(zhì)數(shù)（最初只知道2是質(zhì)數(shù)）的倍數(shù)都去掉，那么剩下的就是質(zhì)數(shù)了。例如要查找100以內(nèi)的質(zhì)數(shù)，首先2是質(zhì)數(shù)，把2的倍數(shù)去掉；此時(shí)3沒(méi)有被去掉，可認(rèn)為是質(zhì)數(shù)，所以把3的倍數(shù)去掉；再到5，再到7，7之后呢，因?yàn)?，9，10剛才都被去掉了，而100以內(nèi)的任意合數(shù)肯定都有一個(gè)因子小于10（100的開(kāi)方），所以，去掉，2，3，5，7的倍數(shù)后剩下的都是質(zhì)數(shù)了。用程序可以這樣解決，引入布爾類型數(shù)組ai，如果i是質(zhì)數(shù)，ai=true，否則ai=false。那么劃掉i可以表示成ai=false。 /找出n以內(nèi)質(zhì)數(shù)void Sieve(int n) boo