算法分析教(學)案設計實驗報告

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

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

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

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

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

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

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

8、輸出第 n 個斐波那契數if(n=0)return 0;Else if(n=1)return 1;ElseF00;F11;for(i=2;i<n-2;i+)F2=f1+f0;/f1 表示當前的值F0F1.專業(yè)學習資料.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計算機最大可表示第%d 個斐波拉契數 n",i);end=clock();printf(" 運行時間為 %f秒 n",(end-start)/1000);void DieDai()long shu3,count;.專業(yè)學習資料.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計算機最大可表示第%d 個斐波拉契數 n",count);end=clock();printf(" 運行時間為 %f毫秒 n",end-start);void Fibonacci()printf("n迭代算法 ：n");DieDai();printf("n遞歸算法 ：n");DiGui();.專業(yè)學習資料.實驗結果通過比較兩種方法求Fibonacci 數列所用的時間 ，可以發(fā)現迭代法的效率明顯及高于遞歸法 。 同時也明白了不同的算法可以解決相同的問題，

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

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

13、法的方法求得解ElseDivide （A ） / 把 A 分成 4 塊Divide （B） / 把 B 分成 4 塊調用 7 次 strassen 算法求得解的4 塊合并這 4 塊得到解并返回.專業(yè)學習資料./ 矩陣相乘問題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 應重新賦值為零for(t=0;t<2;t+)Cij=Cij+Ait*Btj;void MATRIX_ADD(int n,float XN,float YN,float ZN) /矩陣加法函數 X+Y >Zint i,j;for(i=0;i<n;i+)for(j=0;j<n;j+).專業(yè)學習資料.Zij=Xij+Yij;void MATRIX_SUB(int n,float XN,f

16、loat YN,float ZN) /矩陣減法函數 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è)學習資料.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 數據：n"); for(i=0;i<n;i+) for(j=0;j<

21、;n;j+)scanf("%f",&Aij);printf(" 請輸入 B數據： n");.專業(yè)學習資料.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(" 數組 A 中數據為 ： 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(" 數組 B中數據為 ： 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è)學習資料.int i ,j;printf(" 結果數組 C中數據為 ：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(" 輸入矩陣階數 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è)學習資料.printf(" 按鍵錯誤 n");con:printf("-1用 BF方法 -n");printf("-2用 DAC 方法-n");printf("-3結束 -n");while(1)printf(" 請輸入選擇 nn");fflush(stdin);

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

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

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

29、2 份個數相等的If 這 2 份重量相等 ，假幣在第3 堆中 ，對第 3 堆使用該算法Else 在較重的那堆中，對該堆硬幣使用該算法.專業(yè)學習資料.程序代碼./ 假幣問題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è)學習資料.elseFakeCoin_1(coin,n,l,l+ps-1);void FakeCoin()int i=1,n, coin100;printf(" 請輸入硬幣的個數: ");scanf("%d",&n);printf(" 請輸入硬幣的重量:n");for(i=1;i<=

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

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

34、(參見二叉樹的順序存儲結構)，在當前無序區(qū)中選擇關鍵字最大(或最小 )的記錄堆排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。想）它是 不穩(wěn)定 的排序方法。.專業(yè)學習資料.程序代碼./ 堆排序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(" 輸入要排序的個數n： ");scanf("%d",&n);while(1)printf("n 1.自動生成2.手動輸入3.結束 n");scanf("%d",&choice);switch(choice)case 1:for(i=1;i<=n;i+)ai=rand();printf(" 產生的隨機數為:");fo