計(jì)算機(jī)計(jì)科班算法設(shè)計(jì)與分析復(fù)習(xí)資料

1、1. 算法 ：是若干條指令組成的有窮序列2. 算法的三個(gè)要素1) 數(shù)據(jù) : 運(yùn)算序列中作為運(yùn)算對(duì)象和結(jié)果的數(shù)據(jù) .2) 運(yùn)算: 運(yùn)算序列中的各種運(yùn)算 :賦值 , 算術(shù)和邏輯運(yùn)算3) 控制和轉(zhuǎn)移 : 運(yùn)算序列中的控制和轉(zhuǎn)移 .四條性質(zhì) ：輸入、輸出、確定性、有窮性3. 四條性質(zhì) ：1) 輸入 ：有零個(gè)或多個(gè)由外部提供的量作為算法的輸入2) 輸出 ：算法產(chǎn)生至少一個(gè)量作為輸出3) 確定性 ：組成算法的每條指令是清晰的，無歧義的。4) 有限性 ：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。4. 程序 ：是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)5. 算法的復(fù)雜性 ：算法運(yùn)行所需要的計(jì)算機(jī)

2、資源的量時(shí)間復(fù)雜性 (算法運(yùn)行所需要的計(jì)算機(jī)時(shí)間資源的量)空間復(fù)雜性 (算法運(yùn)行所需空間資源的量) 時(shí)間復(fù)雜性的三種情況 ：最壞情況(可操作性最好且最優(yōu)實(shí)際價(jià)值) 、最好情況、平均情況6. 分治法的設(shè)計(jì)思想 ：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。7. 遞歸 ：直接或間接地調(diào)用自身的算法。 遞歸函數(shù) ：用函數(shù)自身給出定義的函數(shù)。8. 階乘函數(shù)可遞歸定義為 ：1 n 0n!n(n 1)! n 0遞歸定義式 ：int factorial( int n)if (n = 0) return 1;return n * factorial(n-1);9. Fib

3、onacci 數(shù)列 ：無窮數(shù)列 1，1，2，3，5，8，13 ，21 ，34 ，5，可遞歸定義為1 n 0F(n) 1 n 1F(n 1) F(n 2) n 1遞歸定義式 ：int fibonacci( int n)if (n = 1) return 1;return fibonacci(n-1)+fibonacci(n-2);10. Hanoi 塔定義式 ：void hanoi( int n, int a, int b, int c)if (n 0)hanoi (n - 1, a, c, b);move (a, b);hanoi (n - 1, c, b, a);11. 二分搜索算法的基本思

4、想： 是將 n 個(gè)過元素分成大致相同的兩半，取 an/2 與 x 作比較。12. 合并排序 ：用分治法策略實(shí)現(xiàn)對(duì) n 個(gè)元素進(jìn)行排序的算法?；舅枷胧牵簩⒋判蛟胤殖纱笮〈笾孪嗤膬蓚€(gè)子集， 分別對(duì)兩個(gè)子集合進(jìn)行排序，最終將排好序的子集合并成所要求的排好序的集合。13. 動(dòng)態(tài)規(guī)劃算法基本思想( 自底向上、全局最優(yōu) )：講帶求解的問題分解成若干個(gè)子問題，先求解子問題，然后從這些子 問題的解得到原問題的解。與分治法不同的是 ：適用于動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。 最優(yōu)子結(jié)構(gòu)性質(zhì) (問題的最優(yōu)解包含了其子問題的最優(yōu)解)子問題重疊性質(zhì) (在用遞歸算法自頂向下求解此問題時(shí)

5、，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多 次)備忘錄方法 （ 動(dòng)態(tài)規(guī)劃算法變形 ）：用表格保存已解決的子問題的答案，在下次需要解此子問題時(shí)，只要簡(jiǎn)單地查看該 子問題的解答，而不必重新計(jì)算。14. 最優(yōu)二叉搜索樹性質(zhì) ：存儲(chǔ)于每個(gè)結(jié)點(diǎn)中的元素 x 大于其左子樹中任一結(jié)點(diǎn)所存儲(chǔ)的元素，小于其右子樹中任一結(jié)點(diǎn)所 存儲(chǔ)的元素。15. 貪心算法（ 自頂向下、局部最優(yōu) ）：通過一系列的選擇來得到問題的解。它所做的每一個(gè)選擇都是當(dāng)前狀態(tài)下局部最好 選擇。貪心選擇性質(zhì) （所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇來達(dá)到， 是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別） 最有子結(jié)構(gòu)性質(zhì) （一個(gè)問題的

6、最優(yōu)解包含其子問題的最優(yōu)解）16. 哈夫曼編碼 ：是廣泛用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。17. 最短路徑 ：給定一個(gè) G （V,E） ，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。18. 最小生成樹性質(zhì) ：用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。19. 回溯法（ 盲人爬山、迷宮問題、 n 后問題 ）：在解問題的解空間樹中，按深度優(yōu)先策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹。20. 基本思想 ：從開始結(jié)點(diǎn)（根節(jié)點(diǎn)）出發(fā)，以深度有限方式搜索整個(gè)解空間。21. 分枝限界法基本思想 ：以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。分枝限界法 求解目標(biāo)是找出滿足約束條件的 一個(gè)解 ，或是滿足約

7、束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的 解，即在某種意義下的最優(yōu)解?；厮莘?求解目標(biāo)是找出解空間中滿足約束條件的 所有解 。22. 批處理作業(yè)調(diào)度： 給定 n 個(gè)作業(yè)的集合 J = （J1,J2,Jn） 。每個(gè)作業(yè) Ji 都有兩項(xiàng)任務(wù)分別在兩臺(tái)機(jī)器上完成。每個(gè)作業(yè)必須先由機(jī)器 1 處理，然后再由機(jī)器 2 處理。23. 分支限界法與回溯法： 分支限界法與回溯法的求解目標(biāo)不同，回溯法的求解目標(biāo)是找出求解空間中滿足約束條件的所有 解，而分支限界法求解的目標(biāo)則是找出滿足約束條件的一個(gè)解?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間，而分支限界法則以廣 度優(yōu)先或最小耗費(fèi)優(yōu)先的方式搜索空間。24. 隨機(jī)化算

8、法基本特征 ：對(duì)所求解問題的同一實(shí)例用同一隨機(jī)化算法求解兩次可能得到完全不同的效果。 隨機(jī)數(shù)在隨機(jī)化算法設(shè)計(jì)中扮演著十分重要的角色。符號(hào)三角問題 ：#include #define M 13#define N 13 Triangle( char AMN) int i,j;printf(n 輸入第 1 行的數(shù)據(jù)： );for (j=0;jN;j+) / 輸入第 1行的數(shù)據(jù) scanf(%c,&A0j);for (i=1;iM;i+)/ Afor (j=0;jN;j+)Aij= ;i=0; j=0;while (iM-1) while (jN-1) if (Aij=Aij+2) / Ai+1j+1

9、=+; elseAi+1j+1=-; j=j+2;i+; j=i;void main() int i,j;數(shù)組的第 2 行以下清空如果上一行的相鄰兩符號(hào)相同/ 則下一行的符號(hào)為 +/ 否則下一行的符號(hào)為 -char AMN;Triangle(A);for (i=0;iM/2+1;i+) for (j=0;jN-i;j+) printf(%4c,Aij); printf(nn);矩陣相乘：/ 兩矩陣相乘#include #define M 2#define N 3MatrixMultiply( int AMN, int BNM, int CMM) int i,j,k,sum;for (i=0;i

10、M;i+)for (j=0;jM;j+) sum=0;for (k=0;kN;k+)sum=sum+Aik*Bkj; Cij=sum;void main() int AMN,BNM,CMM,i,j,k;for (i=0;iM;i+) / 輸入 6個(gè)整數(shù)給矩陣 A for (j=0;jN;j+)scanf(%d,&Aij);for (i=0;iN;i+) / 輸入 6個(gè)整數(shù)給矩陣 B for (j=0;jM;j+)scanf(%d,&Bij);MatrixMultiply(A, B, C);printf(n 兩矩陣相乘的的結(jié)果如下： nn); for (i=0;iM;i+) for (j=0;j

11、M;j+) printf(%4d,Cij);printf(nn);二分搜索算法： 是用分支策略的典型例子，需要先排序。# include # define MAXLEN 11 typedef struct int key; type_element;int key)在右半部繼續(xù)查找在右半部繼續(xù)查找int binary_search(type_element r, int left=1,right=MAXLEN,middle; while (leftkey)right=middle-1; /else left=middle+1; /return -1;void main() int i,j,ke

12、y;type_element temp,rMAXLEN+1=0,9,13,15,30,37,55,60,75,80,90,92;for (i=1;iMAXLEN;i+) / 對(duì)數(shù)組進(jìn)行排序for (j=i+1;jrj.key) temp=ri;ri=rj;rj=temp;for (i=1;i=MAXLEN;i+)printf(%3d,ri.key);printf(nn 輸入欲查找的數(shù)據(jù)： ); scanf(%d,&key);i=binary_search(r,key);if (i=-1)printf(n 已經(jīng)查找完，尚未找到該數(shù)！ nn); elseprintf(nn已找到，其序號(hào)是： %d

13、nn,i);int partition( int r,ints, int t)inti,j,rp;i=s;j=t;/一趟快速排序，將基準(zhǔn)記錄移到正確位置rp=rs;/基準(zhǔn)記錄暫存 rp 中while (ij)/從序列的兩端交替向中間掃描while (i=rp)/掃描比基準(zhǔn)記錄小的位置j-;ri=rj;/將比基準(zhǔn)記錄小的數(shù)據(jù)移到低端while (ij & ri=rp)/掃描比基準(zhǔn)記錄大的位置i+;rj=ri;/將比基準(zhǔn)記錄大的數(shù)據(jù)移到高端ri=rp;/基準(zhǔn)記錄到位return i; voidQuickSort( int r,ints, intt) / 快速排序遞歸算法intk;if(st)/長(zhǎng)度

14、達(dá)于 1k=partition(r,s,t);/調(diào)用一趟快速排序算法將 rs.rtQuickSort(r,s,k-1);/對(duì)低端子序列遞歸排序， k 是支點(diǎn)位置QuickSort(r,k+1,t);/對(duì)高端子序列遞歸排序快速排序：#include #include #define MAXLEN 10一分為二void main() int i;int rMAXLEN;printf(n請(qǐng)輸入 %d個(gè)整數(shù)： ,MAXLEN);for (i=0;iMAXLEN;i+)scanf(%d,&ri);QuickSort(r,0,MAXLEN-1);printf(n 快速排序的結(jié)果如下： nn); for (

15、i=0;iMAXLEN;i+)printf(%3d,ri);printf(nn);循環(huán)賽日程表：#include #define MAXLEN 8void main() int i,j;int xMAXLEN+1MAXLEN+1=0; / for (i=1;i=MAXLEN;i+)/xi1=i;for (i=1;i=MAXLEN;i+)/if (i % 2 !=0) xi2=xi+11;else xi2=xi-11;for (i=1;i=8;i+) / for (j=1;j=2;j+)數(shù)組清零產(chǎn)生第 1列數(shù)據(jù)產(chǎn)生第 2列數(shù)據(jù)/ 產(chǎn)生奇數(shù)行的第 2列的數(shù)據(jù)/ 產(chǎn)生偶數(shù)行的第 2列的數(shù)據(jù) 產(chǎn)生左半

16、部表中的右半部分 if (i=1 | i=2 | i=5 | i=6) xi+2j+2=xij;elsexi-2j+2=xij;for (i=1;i=8;i+) / 產(chǎn)生右半部表的數(shù)據(jù) for (j=1;j=4;j+) if (i=4) xi+4j+4=xij;elsexi-4j+4=xij;printf(n 循環(huán)賽日程表如下： nn);for (i=1;i=MAXLEN;i+) / 輸出該表 for (j=1;j=MAXLEN;j+) printf(%6d,xij);printf(nn);最大公約數(shù)：int gcd( int m, int n)int r;while (n!=0)r = m

17、% n; m = n; n = r; return m;最小公倍數(shù)：int gcm( int m, int n) int i,k,f;if (mn) /交換 m與 n i=m;m=n;n=i;f=1;if (m%n=0) f=f*m;return f;i=2;k=( int )(sqrt(n);/求 n 的平方根取整數(shù)while (i=k) if (m%i=0)&(n%i=0) f=f*i;m=m/i;n=n/i;i=2;else i+;f=f*m*n;return f;冒泡排序：/ 交換排序中的冒泡排序法# include # define LENGTH 10 void main() int

18、 i,j,k,temp; int rLENGTH;for (i=0;iLENGTH;i+)說明該趟沒有發(fā)生交換scanf(%d,&ri);for (i=1;i=LENGTH-1;i+)/ k=0;for (j=0;jrj+1)/ k+;temp=rj;rj=rj+1; rj+1=temp;if (k=0) / 輸入 10 個(gè)整數(shù)共進(jìn)行 LENGTH-1 趟排序 第 i 趟排序比較的次數(shù) 若相鄰兩記錄的關(guān)鍵字逆序，/ 則互相交換break ; / 跳出該層循環(huán)for (i=0;iLENGTH;i+)printf(%3d,ri); / 輸出排序結(jié)果 素?cái)?shù)判斷：int number;bool pri

19、me( int x) int i,k;k=sqrt(x);for (i=2;i=k;i+)if (x%i=0) return false retrun true;素?cái)?shù)因子分解：#include #include #define N 100/ number 為全局變量/ 如果 X能被 2 sqrt(x)中的任何一個(gè)整數(shù)整除，/ 則 X不是素?cái)?shù)，因此應(yīng)跳出該層循環(huán)/ 表示X未被 2 sqrt(x)中的任何一個(gè)整數(shù)整除void main() int i,j,k,x,y,sieve_AN+1,sieve_BN+1,sieve_CN+1; scanf(%d,&x); / 輸入一個(gè) 100 以內(nèi)的非負(fù)整數(shù) y = x;sieve_Ai=i;k=(int )sqrt(x);for(i=2;i=k;i+)j=i*i;while (j=x) if (sieve_Aj!=0)/定位i 的倍數(shù)處sieve_Aj=0;/篩去 i 的倍數(shù)即將其變?yōu)?0j=j+i;/求出i 的下一個(gè)倍數(shù) j=0;for(i=2;i=x;i+)/將 sieve_A 篩中的素?cái)?shù)賦給 sieve_Bif (sieve