算法分析教(學(xué))案設(shè)計實驗報告

1、.*院系：計算機(jī)科學(xué)學(xué)院專業(yè)：計算機(jī)科學(xué)與技術(shù).專業(yè)學(xué)習(xí)資料.年級：課程名稱 ： 算法設(shè)計與分析基礎(chǔ)班號：組號：指導(dǎo)教師 ：年月日學(xué)號姓名組員實驗名稱算法實驗整體框架的構(gòu)建實驗室.專業(yè)學(xué)習(xí)資料.1.實驗題目算法實驗主菜單的設(shè)計。2 實驗?zāi)康?熟悉實驗環(huán)境VC 6.0； 復(fù)習(xí) C、 C+ 語言以及數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識，實現(xiàn)課程間的平滑過度；3.實驗要求1）設(shè)計的主菜單可以是圖形模式的，也可以是控制臺模式的。以控制臺為例，主菜單實大致如下 ：驗?zāi)克惴ㄔO(shè)計與分析 實驗的或1.算法分析基礎(chǔ) Fibonacci序列問題要2.分治法在數(shù)值問題中的應(yīng)用 最近點對問題求3.減治法在組合問題中的應(yīng)用 8 枚硬

2、幣問題4. 變治法在排序問題中的應(yīng)用 堆排序問題5. 動態(tài)規(guī)劃法在圖問題中的應(yīng)用 全源最短路徑問題99. 退出本實驗請輸入您所要執(zhí)行的操作 （ 1 ， 2， 3 ，4， 5， 99 ）：2）點擊操作后進(jìn)入相應(yīng)的實驗項目或是相應(yīng)項目的下一級菜單；3）可以反復(fù)執(zhí)行，直到退出實驗 。.專業(yè)學(xué)習(xí)資料.程序代碼.void Meun()printf("nttn");printf("ntt算法設(shè)計與分析 實驗 n");printf("nttn");printf("ntt1、算法分析基礎(chǔ) Fibonacci 序列問題 n");pr

3、intf("ntt2、分治法在數(shù)值問題中的應(yīng)用 矩陣相乘問題 n");printf("ntt3、減治法在組合問題中的應(yīng)用 枚硬幣問題 n");printf("ntt4、變治法在排序問題中的應(yīng)用 堆排序問題 n");Printf("ntt4、動態(tài)規(guī)劃法在圖問題中的應(yīng)用 全源最短路徑問題n");動態(tài)規(guī)劃法在圖問題中的應(yīng)用 全源最短路徑問題printf("ntt99、退出本實驗 n");printf("ntt");printf("ntt請輸入您所要執(zhí)行的操作（ 1， 2，

4、3 ，4，5 ，99 ）： ");void main()int a;while(1)Meun();/ 調(diào)用菜單函數(shù)顯示菜單scanf("%d",&a);switch(a)case 1:printf("nttFibonacci序列問題 ttn");fibonacci();break;case 2:printf("ntt 分治法在數(shù)值問題中的應(yīng)用 矩陣相乘問題 ttn"); matrix();break;case 3:printf("ntt 減治法在組合問題中的應(yīng)用 8 枚硬幣問題 ttn"); CO

5、INFAKE();break;case 4:.專業(yè)學(xué)習(xí)資料.printf("ntt 變治法在排序問題中的應(yīng)用 堆排序問題 ttn"); HEAP();break;case 5:printf("ntt 動態(tài)規(guī)劃法在圖問題中的應(yīng)用 全源最短路徑問題 ttn"); break;case 99:printf(" 你選擇退出本實驗n " );exit(0);實驗結(jié)果及分析.專業(yè)學(xué)習(xí)資料.算法分析基礎(chǔ) Fibonacci序列實驗名稱實驗室問題.專業(yè)學(xué)習(xí)資料.實驗題目給定一個非負(fù)整數(shù)n，計算第 n 個 Fibonacci數(shù)實驗?zāi)康? ）理解遞歸算法

6、和迭代算法的設(shè)計思想以及遞歸程序的調(diào)式技術(shù)2 ）掌握并應(yīng)用遞歸算法和迭代算法效率的理論分析(前驗分析 )和實際分析 (后驗分析 )實方法；驗3 ）理解這樣一個觀點：不同的算法可以解決相同的問題，這些算法的解題思路不目同，復(fù)雜程度不同，效率也不同 ；的或?qū)嶒炓笠? ）使用教材2.5 節(jié)中介紹的迭代算法Fib(n), 找出最大的n,使得第 n 個 Fibonacci求數(shù)不超過計算機(jī)所能表示的最大整數(shù)，并給出具體的執(zhí)行時間；2 ）對于要求1),使用教材2.5 節(jié)中介紹的遞歸算法F(n)進(jìn)行計算 ,同樣給出具體的執(zhí)行時間，并同 1)的執(zhí)行時間進(jìn)行比較；3 ）對于輸入同樣的非負(fù)整數(shù)n ，比較上述兩種算

7、法基本操作的執(zhí)行次數(shù)；4 ）對 1)中的迭代算法進(jìn)行改進(jìn)，使得改進(jìn)后的迭代算法其空間復(fù)雜度為(1)；5 ）設(shè)計可供用戶選擇算法的交互式菜單(放在相應(yīng)的主菜單下)。.專業(yè)學(xué)習(xí)資料.專業(yè)學(xué)習(xí)資料.實驗原理（算法基本思想）1 、遞歸法基本思想遞歸就是定義一個函數(shù)，讓它自己調(diào)用自己。Fib （int n ）/ 輸入整數(shù) n，輸出第 n 個斐波那契數(shù)if(n=0)return 0;Else if(n=1)return 1;Else return Fib(n-1)+Fib(n-2)2、迭代法這種方法相對于遞歸法來說在時間復(fù)雜度上減小了不少，但代碼相對就要復(fù)雜些了。Fib （int n ）/ 輸入整數(shù) n，

8、輸出第 n 個斐波那契數(shù)if(n=0)return 0;Else if(n=1)return 1;ElseF00;F11;for(i=2;i<n-2;i+)F2=f1+f0;/f1 表示當(dāng)前的值F0F1.專業(yè)學(xué)習(xí)資料.F1F2;Return F2;程序代碼int Fib(int i)if(i<2)return i;elsereturn Fib(i-1)+Fib(i-2);void DiGui()int f=0,i=0,t=0;double start,end;start=clock();while(2*t>=0)t=f;f=Fib(i);printf("%d&quo

9、t;,f);i+;printf("n計算機(jī)最大可表示第%d 個斐波拉契數(shù) n",i);end=clock();printf(" 運(yùn)行時間為 %f秒 n",(end-start)/1000);void DieDai()long shu3,count;.專業(yè)學(xué)習(xí)資料.double start,end;start=clock();shu0=0;shu1=1;printf("%ld",shu0);for(count=1;shu1>=shu0;count+)printf("%ld",shu1);shu2=shu1+sh

10、u0;shu0=shu1;shu1=shu2;printf("n計算機(jī)最大可表示第%d 個斐波拉契數(shù) n",count);end=clock();printf(" 運(yùn)行時間為 %f毫秒 n",end-start);void Fibonacci()printf("n迭代算法 ：n");DieDai();printf("n遞歸算法 ：n");DiGui();.專業(yè)學(xué)習(xí)資料.實驗結(jié)果通過比較兩種方法求Fibonacci 數(shù)列所用的時間 ，可以發(fā)現(xiàn)迭代法的效率明顯及高于遞歸法 。 同時也明白了不同的算法可以解決相同的問題，

11、這些算法的解分題思路不同 ，復(fù)雜程度不同 ，效率也不同 。析分治法在數(shù)值問題中的應(yīng)用實驗名稱實驗室 矩陣相乘問題.專業(yè)學(xué)習(xí)資料.實驗題目設(shè) M 1 和 M 2 是兩個 n×n 的矩陣 ，設(shè)計算法計算 M 1×M 2 的乘積 。實驗?zāi)康? ）提高應(yīng)用蠻力法設(shè)計算法的技能；實2 ）深刻理解并掌握分治法的設(shè)計思想；驗3 ）理解這樣一個觀點：用蠻力法設(shè)計的算法，一般來說 ，經(jīng)過適度的努力后，都可目以對其進(jìn)行改進(jìn)，以提高算法的效率。的實驗要求或1）設(shè)計并實現(xiàn)用BF 方法求解矩陣相乘問題的算法；要2）設(shè)計并實現(xiàn)用DAC 方法求解矩陣相乘問題的算法；求3）以上兩種算法的輸入既可以手動輸入

12、，也可以自動生成 ；4）對上述兩個算法進(jìn)行時間復(fù)雜性分析，并設(shè)計實驗程序驗證分析結(jié)果 ；5）設(shè)計可供用戶選擇算法的交互式菜單(放在相應(yīng)的主菜單下 )。.專業(yè)學(xué)習(xí)資料.實驗原理（算1）蠻力法求解蠻力法比較簡單，直接使用矩陣相乘公式計算矩陣的每行每列的值，很容易就能得出答案2）分治法求解分治法思想法將問題實例劃分為同一問題的幾個較小的實例。對這些較小實例求解，通常使基用遞歸方法，但在問題規(guī)模足夠小時，也會使用另一種算法。如果有必要，合并這些問本思想）題的解 ，以得到原始問題的解。求解矩陣相乘的DAC 算法 ，使用了 strassen 算法 。DAC （ A ， B，n ）If n=2使用 7 次乘

13、法的方法求得解ElseDivide （A ） / 把 A 分成 4 塊Divide （B） / 把 B 分成 4 塊調(diào)用 7 次 strassen 算法求得解的4 塊合并這 4 塊得到解并返回.專業(yè)學(xué)習(xí)資料./ 矩陣相乘問題void matric(int n,float ANN,float BNN,float CNN)LARGE_INTEGER startTime;LARGE_INTEGER endTime;QueryPerformanceCounter(&startTime);int i,j,k;for(i=0;i<n;i+)for(j=0;j<n;j+)Cij=0;fo

14、r(i=0;i<n;i+)for(j=0;j<n;j+)for(k=0;k<n;k+)Cij+=Aik*Bkj;QueryPerformanceCounter(&endTime);LARGE_INTEGER totalTime;程totalTime.QuadPart = endTime.QuadPart - startTime.QuadPart; printf("%ldn", totalTime.QuadPart);序代碼void MATRIX_MULTIPLY(float AN,float BN,float CN)/ 按通常的矩陣乘法計算C=AB

15、 的子算法(僅做 2階)int i,j,t;for(i=0;i<2;i+)/ 計算 A*B->Cfor(j=0;j<2;j+)Cij=0;/ 計算完一個 Cij ， Cij 應(yīng)重新賦值為零for(t=0;t<2;t+)Cij=Cij+Ait*Btj;void MATRIX_ADD(int n,float XN,float YN,float ZN) /矩陣加法函數(shù) X+Y >Zint i,j;for(i=0;i<n;i+)for(j=0;j<n;j+).專業(yè)學(xué)習(xí)資料.Zij=Xij+Yij;void MATRIX_SUB(int n,float XN,f

16、loat YN,float ZN) /矩陣減法函數(shù) X-Y >Zint i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)Zij=Xij-Yij;void STRASSEN(int n, float AN, float BN, float CN)float A11NN, A12NN, A21NN, A22NN;float B11NN, B12NN, B21NN, B22NN;float C11NN, C12NN, C21NN, C22NN;float m1NN, m2NN,m3NN, m4NN, m5NN, m6NN,m7NN; float AANN, BB

17、NN, MM1NN,MM2NN;int i, j;if (n=2)MATRIX_MULTIPLY(A, B, C);elsefor (i=0; i<n/2; i+)for (j=0; j<n/2; j+)A11ij = Aij;A12ij = Aij+n/2;A21ij = Ai+n/2j;A22ij = Ai+n/2j+n/2;B11ij = Bij;B12ij = Bij+n/2;B21ij = Bi+n/2j;B22ij = Bi+n/2j+n/2;MATRIX_ADD(n/2, A11, A22, AA);MATRIX_ADD(n/2, B11, B22, BB);STRA

18、SSEN(n/2, AA, BB, m1);MATRIX_ADD(n/2, A21, A22, AA);STRASSEN(n/2, AA, B11, m2);MATRIX_SUB(n/2, B12, B22, BB);STRASSEN(n/2, A11, BB, m3);.專業(yè)學(xué)習(xí)資料.MATRIX_SUB(n/2, B21, B11, BB);STRASSEN(n/2, A22, BB, m4);MATRIX_ADD(n/2, A11,A12, AA);STRASSEN(n/2, AA, B22, m5);MATRIX_SUB(n/2, A21, A11, AA);MATRIX_ADD(n/

19、2, B11, B12, BB);STRASSEN(n/2, AA, BB, m6);MATRIX_SUB(n/2, A12, A22, AA);MATRIX_ADD(n/2, B21, B22, BB);STRASSEN(n/2, AA, BB, m7);MATRIX_ADD(n/2, m1, m4, MM1);MATRIX_SUB(n/2, m5, m7, MM2);MATRIX_SUB(n/2, MM1, MM2, C11);MATRIX_ADD(n/2, m3, m5, C12);MATRIX_ADD(n/2, m2, m4, C21);MATRIX_ADD(n/2, m1, m3,

20、MM1);MATRIX_SUB(n/2, m2, m6, MM2);MATRIX_SUB(n/2, MM1, MM2, C22);for (i=0; i<n/2; i+)for (j=0; j<n/2; j+)Cij = C11ij;Cij+n/2 = C12ij;Ci+n/2j = C21ij;Ci+n/2j+n/2 = C22ij; / else finishedvoid SHUru(int n,float ANN,float BNN)int i,j;printf(" 請輸入 A 數(shù)據(jù)：n"); for(i=0;i<n;i+) for(j=0;j<

21、;n;j+)scanf("%f",&Aij);printf(" 請輸入 B數(shù)據(jù)： n");.專業(yè)學(xué)習(xí)資料.for(i=0;i<n;i+)for(j=0;j<n;j+)scanf("%f",&Bij);void SHUIji(int n,float ANN,float BNN)int i,j; for(i=0;i<n;i+) for(j=0;j<n;j+)Aij=(float)(n*rand()/(RAND_MAX+1.0) ;printf(" 數(shù)組 A 中數(shù)據(jù)為 ： n");

22、for(i=0;i<n;i+)for(j=0;j<n;j+)printf("%4f",Aij);printf("n");for(i=0;i<n;i+)for(j=0;j<n;j+)Bij=(float)(n*rand()/(RAND_MAX+1.0) ;printf(" 數(shù)組 B中數(shù)據(jù)為 ： n");for(i=0;i<n;i+)for(j=0;j<n;j+)printf("%4f",Bij);printf("n");void print1(int n,flo

23、at CNN).專業(yè)學(xué)習(xí)資料.int i ,j;printf(" 結(jié)果數(shù)組 C中數(shù)據(jù)為 ：n");for(i=0;i<n;i+)for(j=0;j<n;j+)printf("%4f",Cij);printf("n");void Jz() int n;float ANN,BNN,CNN;int i,j;printf(" 本程序用于計算M1 ×M2的乘積 n");printf(" 輸入矩陣階數(shù) n:n");scanf("%d",&n);char fl

24、ag;for(i=0;i<n;i+)for(j=0;j<n;j+)Cij=0;printf("-1手動輸入 -n");printf("-2自動生成 -n");printf("-3確定-n");while(1)printf(" 請輸入選擇 nn");fflush(stdin);flag=getch();switch(flag) case '1':printf(" 手動輸入n");SHUru(n,A,B);printf("n");break;case

25、'2':printf(" 自動生成n");SHUIji(n,A,B);printf("n");break;case '3':goto con;default:.專業(yè)學(xué)習(xí)資料.printf(" 按鍵錯誤 n");con:printf("-1用 BF方法 -n");printf("-2用 DAC 方法-n");printf("-3結(jié)束 -n");while(1)printf(" 請輸入選擇 nn");fflush(stdin);

26、flag=getch();switch(flag) case '1':matric(n,A,B,C);printf(" 用 BF方法得出的結(jié)果n");print1(n,C);printf("n");break;case '2':STRASSEN(n,A,B,C);printf(" 用DAC 方法得出的結(jié)果n");print1(n,C);printf("n");break;case '3':return;default:printf(" 按鍵錯誤 n"

27、;);.專業(yè)學(xué)習(xí)資料.實驗結(jié)果及分析經(jīng)過這個實驗 ，我明白了蠻力法幾乎可以解決所有的問題，但是算法的效率不高。對蠻力法進(jìn)行改進(jìn) ，經(jīng)過適當(dāng)?shù)呐?，算法的效率可以得到提高。.專業(yè)學(xué)習(xí)資料.減治法在組合問題中的應(yīng)用8枚實驗名稱實驗室硬幣問題實驗題目在 8 枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣與真幣的重量不同，但不知道假幣與真幣相比較輕還是較重?？梢酝ㄟ^一架天平來任意比較兩組硬幣，設(shè)計一個高效的算法來檢測這枚假幣。實驗實驗?zāi)康哪? ）深刻理解并掌握減治法的設(shè)計思想并理解它與分治法的區(qū)別；的2 ）提高應(yīng)用減治法設(shè)計算法的技能?；? ）理解這樣一個觀點：建立正角的模型對于問題的求解是非常重

28、要的。要求實驗要求1 ）設(shè)計減治算法實現(xiàn)8 枚硬幣問題 ；2 ）設(shè)計實驗程序，考察用減治技術(shù)設(shè)計的算法是否高效；3 ）擴(kuò)展算法 ，使之能處理n 枚硬幣中有一枚假幣的問題。.專業(yè)學(xué)習(xí)資料.實驗原理（算法基本思想）.減治法主要有三種變種減去一個常量減去一個常量因子減可變規(guī)模與分治法的區(qū)別：分治法把實例分為幾部分分別求解減治法把實例的規(guī)模減為一個更小的實例求解A（ n ） / 輸入硬幣個數(shù)n，要求必須有假幣且已知假幣只有1 個（假設(shè)更重 ）if n=1, 這枚就是假幣Else if n=2 ，較重的那枚是假幣Else把 n 個硬幣分為 3 份， 2 份相等 ，另一份與這 2 份的相差個數(shù)盡可能小稱

29、2 份個數(shù)相等的If 這 2 份重量相等 ，假幣在第3 堆中 ，對第 3 堆使用該算法Else 在較重的那堆中，對該堆硬幣使用該算法.專業(yè)學(xué)習(xí)資料.程序代碼./ 假幣問題void FakeCoin_1(int coin,int n,int l,int h)int i,ps,sum1,sum2;if(n=2)printf(" 不能判斷真假 。.");elseif(l=h)printf(" 第%d 枚硬幣是假的 ，它的重量是 %d。 ",l,coinl);elseif(h-l=1)if(l>1)if(coinl=coin1)printf("

30、第%d 枚硬幣是假的 ，它的重量是 %d 。 ",h,coinh);elseprintf(" 第%d 枚硬幣是假的 ，它的重量是 %d。 ",l,coinl);elseif(h<n)if(coinh=coinn)printf(" 第 %d枚硬幣是假的 ，它的重量是 %d 。",l,coinl);elseprintf(" 第 %d枚硬幣是假的 ，它的重量是 %d 。",h,coinh);elseif(l<h)ps=(h-l+1)/3;sum1=0;sum2=0;for(i=1;i<=ps;i+)sum1+=c

31、oinl+i-1;sum2+=coinh-i+1;if(sum1=sum2)FakeCoin_1(coin,n,l+ps,h-ps);elseif(sum1=coinl+ps*ps)FakeCoin_1(coin,n,h-ps+1,h);.專業(yè)學(xué)習(xí)資料.elseFakeCoin_1(coin,n,l,l+ps-1);void FakeCoin()int i=1,n, coin100;printf(" 請輸入硬幣的個數(shù): ");scanf("%d",&n);printf(" 請輸入硬幣的重量:n");for(i=1;i<=

32、n;i+)scanf("%d",&coini);FakeCoin_1(coin,n,1,n);實驗結(jié)果及分析通過這個實驗，理解并掌握了減治法的設(shè)計思想并理解了它與分治法的區(qū)別。在寫這個算法前 ，一定要建立正確的求解模型。.專業(yè)學(xué)習(xí)資料.變治法在排序問題中的應(yīng)用 堆排實驗名稱實驗室序問題實驗?zāi)康幕蛞髮嶒烆}目用基于變治法的堆排序算法對任意一組給定的數(shù)據(jù)進(jìn)行排序?qū)嶒災(zāi)康?）深刻理解并掌握變治法的設(shè)計思想；2）掌握堆的概念以及如何用變治法把任意給定的一組數(shù)據(jù)改變成堆；3）提高應(yīng)用變治法設(shè)計算法的技能。實驗要求1）設(shè)計與實現(xiàn)堆排序算法；2）待排序的數(shù)據(jù)可以手工輸入(通常規(guī)模

33、比較小， 10 個數(shù)據(jù)左右 ）， 用以檢測程序的正確性 ；也可以計算機(jī)隨機(jī)生成（通常規(guī)模比較大， 1500 3000 個數(shù)據(jù)左右 ）， 用以檢驗(用計數(shù)法 )堆排序算法的時間效率。.專業(yè)學(xué)習(xí)資料.實堆排序利用了大根堆(或小根堆 )堆頂記錄的關(guān)鍵字最大(或最小 )這一特征 ，使得在當(dāng)前驗無序區(qū)中選取最大(或最小 )關(guān)鍵字的記錄變得簡單。原(1)用大根堆排序的基本思想理（ 2 ）大根堆排序算法的基本操作（算法基本思特點 :堆排序 (HeapSort) 是一樹形選擇排序。堆排序的特點是：在排序過程中 ，將 Rl.n看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系

34、(參見二叉樹的順序存儲結(jié)構(gòu))，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大(或最小 )的記錄堆排序的最壞時間復(fù)雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。想）它是 不穩(wěn)定 的排序方法。.專業(yè)學(xué)習(xí)資料.程序代碼./ 堆排序void Dui_1(int h,int n) int heap,i,k,v,j;for(i=(n/2);i>0;i-) k=i;v=hk;heap=0;while(heap=0)&&(2*k<=n) j=2*k; if(j<n) if(hj<hj+1) j=j+1;if(v>hj)heap=1;else hk=hj;k=j;hk=v;void Dui() int aM,i,n,m,t,choice;printf(" 輸入要排序的個數(shù)n： ");scanf("%d",&n);while(1)printf("n 1.自動生成2.手動輸入3.結(jié)束 n");scanf("%d",&choice);switch(choice)case 1:for(i=1;i<=n;i+)ai=rand();printf(" 產(chǎn)生的隨機(jī)數(shù)為:");fo