算法分析與設(shè)計實驗報告

1、百度文庫- 讓每個人平等地提升自我*院系：計算機科學(xué)學(xué)院專業(yè)：計算機科學(xué)與技術(shù)年級：課程名稱：算法設(shè)計與分析基礎(chǔ)班號：組號：指導(dǎo)教師：年月日1百度文庫- 讓每個人平等地提升自我組員實驗名稱實驗?zāi)康幕蛞髮W(xué)號姓名算法實驗整體框架的構(gòu)建實驗室1. 實驗題目算法實驗主菜單的設(shè)計。2實驗?zāi)康氖煜嶒灜h(huán)境VC ； 復(fù)習(xí) C、 C+ 語言以及數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識，實現(xiàn)課程間的平滑過度；3. 實驗要求1）設(shè)計的主菜單可以是圖形模式的，也可以是控制臺模式的。以控制臺為例，主菜單大致如下：算法設(shè)計與分析實驗1. 算法分析基礎(chǔ) Fibonacci 序列問題2. 分治法在數(shù)值問題中的應(yīng)用 最近點對問題3. 減治法

2、在組合問題中的應(yīng)用 8 枚硬幣問題4. 變治法在排序問題中的應(yīng)用 堆排序問題5. 動態(tài)規(guī)劃法在圖問題中的應(yīng)用全源最短路徑問題99. 退出本實驗請輸入您所要執(zhí)行的操作（1， 2，3， 4， 5， 99）：2）點擊操作后進入相應(yīng)的實驗項目或是相應(yīng)項目的下一級菜單；3）可以反復(fù)執(zhí)行，直到退出實驗。2程序代碼百度文庫- 讓每個人平等地提升自我void Meun()printf("nttn");printf("ntt算法設(shè)計與分析實驗 n");printf("nttn");printf("ntt1、算法分析基礎(chǔ) Fibonacci 序

3、列問題 n");printf("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í)行的操作

4、（ 1，2， 3， 4， 5，99）： ");void main()int a;while(1)Meun();3百度文庫- 讓每個人平等地提升自我4百度文庫- 讓每個人平等地提升自我5百度文庫- 讓每個人平等地提升自我6百度文庫- 讓每個人平等地提升自我7百度文庫- 讓每個人平等地提升自我4f4f4f8百度文庫- 讓每個人平等地提升自我9百度文庫- 讓每個人平等地提升自我10百度文庫- 讓每個人平等地提升自我;elseif(l=h)printf("第%d枚硬幣是假的，它的重量是%d。 ",l,coinl);elseif(h-l=1)if(l>1)if(coi

5、nl=coin1)printf(" 第 %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<=

6、ps;i+)sum1+=coinl+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);elseFakeCoin_1(coin,n,l,l+ps-1);11百度文庫- 讓每個人平等地提升自我void FakeCoin()int i=1,n, coin100;printf("請輸入硬幣的個數(shù): ");scanf("%d",&n);printf("請輸入硬幣的重量:n

7、");for(i=1;i<=n;i+)scanf("%d",&coini);FakeCoin_1(coin,n,1,n);實驗結(jié)果及分析通過這個實驗，理解并掌握了減治法的設(shè)計思想并理解了它與分治法的區(qū)別。在寫這個算法前，一定要建立正確的求解模型。12百度文庫- 讓每個人平等地提升自我實驗名稱實驗?zāi)康幕蜃冎畏ㄔ谂判騿栴}中的應(yīng)用 堆排實驗室序問題實驗題目用基于變治法的堆排序算法對任意一組給定的數(shù)據(jù)進行排序?qū)嶒災(zāi)康?）深刻理解并掌握變治法的設(shè)計思想；2）掌握堆的概念以及如何用變治法把任意給定的一組數(shù)據(jù)改變成堆；3）提高應(yīng)用變治法設(shè)計算法的技能。實驗要求1）

8、設(shè)計與實現(xiàn)堆排序算法；要求2）待排序的數(shù)據(jù)可以手工輸入( 通常規(guī)模比較小，10 個數(shù)據(jù)左右），用以檢測程序的正確性；也可以計算機隨機生成（通常規(guī)模比較大，15003000 個數(shù)據(jù)左右），用以檢驗 ( 用計數(shù)法 ) 堆排序算法的時間效率。實堆排序利用了大根堆 ( 或小根堆 ) 堆頂記錄的關(guān)鍵字最大( 或最小 ) 這一特征， 使得在當前無序區(qū)中選取最大 ( 或最小 ) 關(guān)鍵字的記錄變得簡單。驗(1) 用大根堆排序的基本思想（ 2）大根堆排序算法的基本操作原理（算法基本思想）特點 :堆排序 (HeapSort) 是一樹形選擇排序。堆排序的特點是： 在排序過程中， 將 Rl.n看成是一棵完全二叉樹的順

9、序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系 ( 參見二叉樹的順序存儲結(jié)構(gòu)) ，在當前無序區(qū)中選擇關(guān)鍵字最大( 或最小 ) 的記錄堆排序的最壞時間復(fù)雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。它是 不穩(wěn)定 的排序方法。13程序代碼百度文庫- 讓每個人平等地提升自我動生成2.手動輸入3.結(jié)束 n");scanf("%d",&choice);switch(choice)case 1:for(i=1;i<=n;i+)ai=rand();printf("產(chǎn)生的隨機數(shù)為:");for(i=1;i<=n;i+

10、)printf("%d ",ai);printf("n");break;case 2:printf("輸入要排序的數(shù)：n");for(i=1;i<=n;i+)scanf("%d",&ai);break;case 3:return;default:printf("輸入錯誤！ n");return;m=n;while(m>1)Dui_1(a,m);for(i=1;i<=n;i+)printf("%d ",ai);printf("n")

11、;t=a1;a1=am;am=t;m=m-1;for(i=1;i<=n;i+)printf("%d ",ai);printf("n");printf("輸出排序的結(jié)果:");for(i=1;i<=n;i+)printf("%d ",ai);system("pause");14百度文庫- 讓每個人平等地提升自我實驗結(jié)果及分析經(jīng)過這次實驗，理解了變治法的設(shè)計思想，同時還掌握了堆的概念以及如何用變治法把任意給定的一組數(shù)據(jù)改變成堆。15百度文庫- 讓每個人平等地提升自我經(jīng)過這幾次的實驗，對算

12、法的分析能力有了較大的提高。算法分析對于設(shè)計出的每一個具體的算法，利用數(shù)字作為工具討論它的各種復(fù)雜度，就是算法分析的主要任務(wù)。復(fù)雜度分析的結(jié)果可以作為評價算法質(zhì)量的標準之一，有時也可以為改進算法的方向提供參考。分析算法的復(fù)雜度需要較強的數(shù)學(xué)技巧,針對不同的算法 ,采用不同的分析方法。說說Fibonacci心序列問題， 這個實驗讓我們更好的理解遞歸算法和迭代算法的設(shè)計思想以及遞歸程序的調(diào)式技術(shù)，并應(yīng)用遞歸算法和迭代算法效率的理論分析( 前驗分析 ) 和實際分析 ( 后驗分析 ) 方法。得這次實驗也讓我們理解了蠻力法、分治法、減治法、變治法的設(shè)計思想，提高應(yīng)用蠻力法、分治法、減治法、變治法設(shè)計算法的技能。并且理解了幾個重要觀點：不同的算法可體以解決相同的問題，這些算法的解題思路不同，復(fù)雜程度不