第一篇：《計(jì)算機(jī)算法》實(shí)驗(yàn)報(bào)告范文(例文)
1.實(shí)驗(yàn)名稱 本次實(shí)驗(yàn)的名稱。
2.問(wèn)題描述 對(duì)本次實(shí)驗(yàn)要解決的問(wèn)題的描述。
例子：處理漢諾塔問(wèn)題時(shí)，描述什么是漢諾塔問(wèn)題。
3.解決思路 采用什么方法；為什么可以采用這個(gè)方法； 例子：處理棋盤覆蓋問(wèn)題時(shí)，采用什么方法：采用遞歸分治的方法處理； 為什么可以采用遞歸分治方法的原因（P21 頁(yè)圖 2-6 下面一段，理解之后用自己的話表述）：由于將棋盤橫、縱各一分為二之后，特殊方格必然位于四個(gè)小的棋盤之一，那么剩余的其余三個(gè)小棋盤是沒(méi)有方格的，如果采用某種 L 型骨牌覆蓋沒(méi)有特殊方格的三個(gè)小棋盤的中心相連部分（參見(jiàn)圖 2-6 的 b），則三個(gè)小棋盤都各有 1 個(gè)特殊方格所覆蓋。因此，這樣處理之后，原來(lái)大棋盤覆蓋的問(wèn)題，就轉(zhuǎn)化為四個(gè)小棋盤覆蓋的問(wèn)題，因此可以采用分治策略進(jìn)行遞歸處理。
4.算法設(shè)計(jì)與分析 給出算法設(shè)計(jì)的基本思想，如：偽算法描述，遞歸方程等。并分析算法的時(shí)間復(fù)雜度（空間復(fù)雜度）。注意，一定要有文字說(shuō)明。
例子：快速排序 偽算法描述 QuickSort(int a[], int p, int r){ 如果待排序數(shù)組 a[]中只有一個(gè)元素則直接返回； 如果待排序數(shù)組 a[]中不止一個(gè)元素，則進(jìn)行如下處理 {
對(duì)數(shù)組 a[p:r]進(jìn)行 Partition 劃分，使得 a[p:r]以 a[p]為標(biāo)準(zhǔn)，劃分為三個(gè)部分，即：
左半部分 a[p:q-1]；劃分基準(zhǔn) a[q]=a[p]；右半部分 a[q+1:r]；
對(duì)左半部分快速排序 QuickSort(a, p, q-1);
對(duì)右半部分快速排序 QuickSort(a, q+1, r)； } }
例子：0-1 背包問(wèn)題 遞歸關(guān)系或者遞歸方程。
給出 P72 頁(yè)“2.遞歸關(guān)系”中的遞歸表達(dá)式，并給出文字說(shuō)明。
注意：偽算法描述，或者遞歸方程不一定全部需要。根據(jù)問(wèn)題的不同，只給出偽算法，或者只給出遞歸方程都可以。兩者同時(shí)給出也是可以的。
5.程序?qū)崿F(xiàn) 依據(jù)第 4 部分，給出 C 語(yǔ)言（其他語(yǔ)言亦可）的程序?qū)崿F(xiàn)，并進(jìn)行算法時(shí)間（空間）復(fù)雜度分析。
程序?qū)崿F(xiàn)部分要包括：程序代碼、程序注釋、程序運(yùn)行結(jié)果（或者截圖）。
例子：快速排序的 partition 函數(shù) int Partition(Type a[], int p, int r){
int i=p, j= r+1;
int x = a[p];
//x=a[p]是對(duì)數(shù)組 a 進(jìn)行劃分的標(biāo)準(zhǔn)；
/* 以下循環(huán)將數(shù)組 a[p:r]以 a[p]為標(biāo)準(zhǔn)進(jìn)行劃分，在劃分完畢之后，* a[p]調(diào)整到數(shù)組 a[p:r]的中間位置 q，有 a[q]=a[p]；q 左邊所有的* 元素均小于 a[p]，即 a[p:q-1]中的任意元素都小于 a[p]；q 右邊
* 所有的元素均大于 a[p]，即 a[q+1:r]中的元素都大于 a[p]。
* /
while(true){ /* i 用來(lái)從數(shù)組 a[p:r]的左邊向右邊掃描，如果 a[++i]中的元素總是 * 小于基準(zhǔn)元素的，則是符合劃分標(biāo)準(zhǔn)的，因此，不用額外處理，* 循環(huán)一直繼續(xù),直到第一個(gè)不滿足劃分標(biāo)準(zhǔn)的 a[++i]（即 a[++i]>=i）
* 出現(xiàn)，或者整個(gè)數(shù)組 a[p:r]掃描完畢（即 i */ while(a[++i] …… 6.總結(jié) 不用每個(gè)實(shí)驗(yàn)寫(xiě)一個(gè)總結(jié)，可以在一次課作業(yè)的最后寫(xiě)一個(gè)總結(jié)。當(dāng)然，如果需要，在每一個(gè)實(shí)驗(yàn)結(jié)尾都寫(xiě)一個(gè)總結(jié)也是可以的?？偨Y(jié)的目的是自己知識(shí)學(xué)習(xí)的總結(jié)、解決問(wèn)題的總結(jié)、編程的總結(jié)等等。 1.實(shí)驗(yàn)名稱 本次實(shí)驗(yàn)的名稱。 2.問(wèn)題描述 對(duì)本次實(shí)驗(yàn)要解決的問(wèn)題的描述。 例子：處理漢諾塔問(wèn)題時(shí)，描述什么是漢諾塔問(wèn)題。 3.解決思路 采用什么方法；為什么可以采用這個(gè)方法； 例子：處理棋盤覆蓋問(wèn)題時(shí)，采用什么方法：采用遞歸分治的方法處理； 為什么可以采用遞歸分治方法的原因（P21頁(yè)圖2-6下面一段，理解之后用自己的話表述）：由于將棋盤橫、縱各一分為二之后，特殊方格必然位于四個(gè)小的棋盤之一，那么剩余的其余三個(gè)小棋盤是沒(méi)有方格的，如果采用某種L型骨牌覆蓋沒(méi)有特殊方格的三個(gè)小棋盤的中心相連部分（參見(jiàn)圖2-6的b），則三個(gè)小棋盤都各有1個(gè)特殊方格所覆蓋。因此，這樣處理之后，原來(lái)大棋盤覆蓋的問(wèn)題，就轉(zhuǎn)化為四個(gè)小棋盤覆蓋的問(wèn)題，因此可以采用分治策略進(jìn)行遞歸處理。 4.算法設(shè)計(jì)與分析 給出算法設(shè)計(jì)的基本思想，如：偽算法描述，遞歸方程等。并分析算法的時(shí)間復(fù)雜度（空間復(fù)雜度）。注意，一定要有文字說(shuō)明。例子：快速排序 偽算法描述 QuickSort(int a[], int p, int r){ 如果待排序數(shù)組a[]中只有一個(gè)元素則直接返回； 如果待排序數(shù)組a[]中不止一個(gè)元素，則進(jìn)行如下處理 { 對(duì)數(shù)組a[p:r]進(jìn)行Partition劃分，使得a[p:r]以a[p]為標(biāo)準(zhǔn)，劃分為三個(gè)部分，即： 左半部分a[p:q-1]；劃分基準(zhǔn)a[q]=a[p]；右半部分a[q+1:r]； 對(duì)左半部分快速排序QuickSort(a, p, q-1); 對(duì)右半部分快速排序QuickSort(a, q+1, r)； } } 例子：0-1背包問(wèn)題 遞歸關(guān)系或者遞歸方程。 給出P72頁(yè)“2.遞歸關(guān)系”中的遞歸表達(dá)式，并給出文字說(shuō)明。注意：偽算法描述，或者遞歸方程不一定全部需要。根據(jù)問(wèn)題的不同，只給出偽算法，或者只給出遞歸方程都可以。兩者同時(shí)給出也是可以的。 5.程序?qū)崿F(xiàn) 依據(jù)第4部分，給出C語(yǔ)言（其他語(yǔ)言亦可）的程序?qū)崿F(xiàn)，并進(jìn)行算法時(shí)間（空間）復(fù)雜度分析。 程序?qū)崿F(xiàn)部分要包括：程序代碼、程序注釋、程序運(yùn)行結(jié)果（或者截圖）。 例子：快速排序的partition函數(shù) int Partition(Type a[], int p, int r){ int i=p, j= r+1; int x = a[p];//x=a[p]是對(duì)數(shù)組a進(jìn)行劃分的標(biāo)準(zhǔn)； /* 以下循環(huán)將數(shù)組a[p:r]以a[p]為標(biāo)準(zhǔn)進(jìn)行劃分，在劃分完畢之后，* a[p]調(diào)整到數(shù)組a[p:r]的中間位置q，有a[q]=a[p]；q左邊所有的* 元素均小于a[p]，即a[p:q-1]中的任意元素都小于a[p]；q右邊 * 所有的元素均大于a[p]，即a[q+1:r]中的元素都大于a[p]。 * / while(true){ /* i用來(lái)從數(shù)組a[p:r]的左邊向右邊掃描，如果a[++i]中的元素總是 * 小于基準(zhǔn)元素的，則是符合劃分標(biāo)準(zhǔn)的，因此，不用額外處理，* 循環(huán)一直繼續(xù),直到第一個(gè)不滿足劃分標(biāo)準(zhǔn)的a[++i]（即a[++i]>=i）* 出現(xiàn)，或者整個(gè)數(shù)組a[p:r]掃描完畢（即i while(a[++i] ?? 6.總結(jié) 不用每個(gè)實(shí)驗(yàn)寫(xiě)一個(gè)總結(jié)，可以在一次課作業(yè)的最后寫(xiě)一個(gè)總結(jié)。當(dāng)然，如果需要，在每一個(gè)實(shí)驗(yàn)結(jié)尾都寫(xiě)一個(gè)總結(jié)也是可以的?？偨Y(jié)的目的是自己知識(shí)學(xué)習(xí)的總結(jié)、解決問(wèn)題的總結(jié)、編程的總結(jié)等等。 《算法設(shè)計(jì)與分析》 實(shí)驗(yàn)報(bào)告 班級(jí) 姓名 學(xué)號(hào) ****年**月**日 目錄 實(shí)驗(yàn)一 二分查找程序?qū)崿F(xiàn)…………………………………………………………………03頁(yè) 實(shí)驗(yàn)二 棋盤覆蓋問(wèn)題（分治法）.…………………………………………………………08頁(yè) 實(shí)驗(yàn)三 0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)……………………………………………….11頁(yè) 實(shí)驗(yàn)四 背包問(wèn)題的貪心算法………………………………………………………………14頁(yè) 實(shí)驗(yàn)五 最小重量機(jī)器設(shè)計(jì)問(wèn)題（回溯法）………………………………………………17頁(yè) 實(shí)驗(yàn)六 最小重量機(jī)器設(shè)計(jì)問(wèn)題（分支限界法）…………………………………………20頁(yè) 指導(dǎo)教師對(duì)實(shí)驗(yàn)報(bào)告的評(píng)語(yǔ) 成績(jī)： 指導(dǎo)教師簽字： ****年**月**日 實(shí)驗(yàn)一：二分查找程序?qū)崿F(xiàn) 一、實(shí)驗(yàn)時(shí)間：2013年10月8日，星期二，第一、二節(jié)地點(diǎn)：J13#328 二、實(shí)驗(yàn)?zāi)康募耙?/p> 目的： 建立算法復(fù)雜度的理論分析與實(shí)驗(yàn)分析的聯(lián)系，深刻體會(huì)算法復(fù)雜度作為算法的好壞評(píng)價(jià)指標(biāo)的本質(zhì)含義。要求： 1、用c/c++語(yǔ)言實(shí)現(xiàn)二分搜索算法。 2、通過(guò)隨機(jī)產(chǎn)生有序表的方法，測(cè)出在平均意義下算法比較次數(shù)隨問(wèn)題規(guī)模的變化曲線，并作圖。 三、實(shí)驗(yàn)環(huán)境 平臺(tái)：Win7 32位操作系統(tǒng) 開(kāi)發(fā)工具：Codeblocks10.05 四、實(shí)驗(yàn)內(nèi)容 對(duì)已經(jīng)排好序的n個(gè)元素a[0：n-1]，現(xiàn)在要在這n個(gè)元素中找出一特定元素x。 五、算法描述及實(shí)驗(yàn)步驟 算法描述： 折半查找法也稱為二分查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務(wù)。它的基本思想是，將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果x 1、首先設(shè)定問(wèn)題規(guī)模n； 2、隨即產(chǎn)生遞增數(shù)列； 3、在n個(gè)有序數(shù)中隨機(jī)取一個(gè)作為待查找量，搜索之； 4、記錄查找過(guò)程中的比較次數(shù)，再次生成新的有序表并查找，記錄查找次數(shù)，每個(gè)數(shù)組重復(fù)10次； 5、改變問(wèn)題規(guī)模n重復(fù)上述步驟2~4，n取100、200……1000； 6、依實(shí)驗(yàn)數(shù)據(jù)作圖，并與理論圖作比較； 7、二分搜索算法平均查找次數(shù)： 問(wèn)題規(guī)模為n時(shí)，平均查找次數(shù)為： A(n)=Int(logn)+ 1/2 // Int()函數(shù)為向下取整 即二分搜索算法對(duì)于含有n個(gè)數(shù)據(jù)的有序表L平均作了約Int(logn)+1/2次的查找操作。 實(shí)驗(yàn)步驟： 1.初始化生成遞增隨機(jī)數(shù)列： for(int j=100;j <=1000;j+=100){ array[0]=10+rand()%15; for(int i=1;i array[i]=array[i-1]+1+rand()%3+rand()%10; } } 2.定義二分查找算法： int BinarySearch(const int b[], int searchKey, int low, int high);其中，返回值為int類型，數(shù)組b[]為待查遞增序列，searchKey為所查數(shù)據(jù)，low為數(shù)組b[]左下標(biāo)，hight為數(shù)組b[]右下標(biāo)。該算法實(shí)現(xiàn)過(guò)程為： 將數(shù)組b[]的n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取b[n/2]與searchKey作比較。如果searchKey=b[n/2]，則找到searchKey，算法終止；如果searchKey 3.實(shí)現(xiàn)主函數(shù)并完成所有代碼。4.算法復(fù)雜性分析： 容易看出，沒(méi)執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O（logn）次。循環(huán)體內(nèi)運(yùn)算需要O（1）時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O（logn）。 六、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果 輸出結(jié)果為： Every array repeat search times: 10 Number of Elements 理論平均查找次數(shù) 實(shí)際平均查找次數(shù) 6.5 6.1 200 7.5 7.3 300 8.5 7.4 400 8.5 7.4 500 8.5 7.5 600 9.5 8.2 700 9.5 8.8 800 9.5 8.7 900 9.5 8.8 1000 9.5 9.4 七、總結(jié) 二分查找在搜索有序表時(shí)，效率比較高。通過(guò)這次實(shí)驗(yàn)我對(duì)二分查找算法的認(rèn)識(shí)又有了新的提高。本想寫(xiě)個(gè)圖形界面，但由于種種原因，沒(méi)有實(shí)現(xiàn)，下次做加密算法時(shí)，要寫(xiě)一個(gè)圖形化界面。 指導(dǎo)教師對(duì)實(shí)驗(yàn)報(bào)告的評(píng)語(yǔ) 成績(jī)： 指導(dǎo)教師簽字： ****年**月**日 實(shí)驗(yàn)二：分治法解決棋盤問(wèn)題 一、實(shí)驗(yàn)時(shí)間：2013年10月22日，星期二，第一、二節(jié)地點(diǎn)：J13#328 二、實(shí)驗(yàn)?zāi)康募耙?/p> 1、用c/c++語(yǔ)言實(shí)現(xiàn)分治法解決棋盤問(wèn)題算法。 2、實(shí)現(xiàn)棋盤化以及棋盤覆蓋 三、實(shí)驗(yàn)環(huán)境 Windows 2007 操作系統(tǒng) 以及code blocks軟件 四、實(shí)驗(yàn)內(nèi)容 在一個(gè)2^k*2^k的方格組成的棋盤中，若恰有一個(gè)方格與其他方格不同，則稱該方格為一個(gè)特殊方格。用分治法將整個(gè)棋盤除特殊方格以外的方格覆蓋。 五、算法描述及實(shí)驗(yàn)步驟 將2^k x 2^k的棋盤，先分成相等的四塊子棋盤，其中特殊方格位于四個(gè)中的一個(gè)，構(gòu)造剩下沒(méi)特殊方格三個(gè)子棋盤，將他們中的也假一個(gè)方格設(shè)為特殊方格。如果是： 左上的子棋盤（若不存在特殊方格）----則將該子棋盤右下角的那個(gè)方格假設(shè)為特殊方格 右上的子棋盤（若不存在特殊方格）----則將該子棋盤左下角的那個(gè)方格假設(shè)為特殊方格 左下的子棋盤（若不存在特殊方格）----則將該子棋盤右上角的那個(gè)方格假設(shè)為特殊方格 右下的子棋盤（若不存在特殊方格）----則將該子棋盤左上角的那個(gè)方格假設(shè)為特殊方格 當(dāng)然上面四種，只可能且必定只有三個(gè)成立，那三個(gè)假設(shè)的特殊方格剛好構(gòu)成一個(gè)L型骨架，我們可以給它們作上相同的標(biāo)記。這樣四個(gè)子棋盤就分別都和原來(lái)的大棋盤類似，我們就可以用遞歸算法解決。 六、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果 七、總結(jié) 由于覆蓋一個(gè)2k*2k棋盤所需的L型骨牌個(gè)數(shù)為（4k-1）/3，故此算法是一個(gè)在漸近意義下最優(yōu)的算法。 指導(dǎo)教師對(duì)實(shí)驗(yàn)報(bào)告的評(píng)語(yǔ) 成績(jī)： 指導(dǎo)教師簽字： ****年**月**日 實(shí)驗(yàn)三：0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法設(shè)計(jì) 一、實(shí)驗(yàn)?zāi)康募耙?/p> 1.了解并掌握動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想。 2.利用動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想實(shí)現(xiàn)0-1背包問(wèn)題的算法設(shè)計(jì)。 二、實(shí)驗(yàn)環(huán)境 使用C++語(yǔ)言； 在windows環(huán)境下使用CodeBlocks調(diào)試并運(yùn)行。 三、實(shí)驗(yàn)內(nèi)容 1.了解并掌握動(dòng)態(tài)規(guī)劃的設(shè)計(jì)思想。 2.利用動(dòng)態(tài)規(guī)劃算法的思想解決0-1背包問(wèn)題。 四、算法描述及實(shí)驗(yàn)步驟 每種物品一件，可以選擇放1或不放0。 用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} “將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價(jià)值為f[i-1][v]；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i]。 五、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果 六、總結(jié) 0-1背包問(wèn)題是最基本的背包問(wèn)題，它包含了背包問(wèn)題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類型的背包問(wèn)題往往也可以轉(zhuǎn)換成0-1背包問(wèn)題求解。通過(guò)這次實(shí)驗(yàn)我對(duì)動(dòng)態(tài)規(guī)劃算法的認(rèn)識(shí)又有了新的提高。 指導(dǎo)教師對(duì)實(shí)驗(yàn)報(bào)告的評(píng)語(yǔ) 成績(jī)： 指導(dǎo)教師簽字： ****年**月**日 實(shí)驗(yàn)四：背包問(wèn)題的貪心算法 一、實(shí)驗(yàn)?zāi)康模?/p> 運(yùn)用貪心算法思想，設(shè)計(jì)解決上述問(wèn)題的算法，找出最大背包價(jià)值的裝法。 二、實(shí)驗(yàn)要求 1.用c++語(yǔ)言實(shí)現(xiàn)背包問(wèn)題的貪心算法。 2.掌握貪心思想的應(yīng)用。 三、實(shí)驗(yàn)原理 在貪心算法中采用逐步構(gòu)造最優(yōu)解的辦法，在每個(gè)階段，都做出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下），決策一旦做出就不可更改。 四、實(shí)驗(yàn)過(guò)程(步驟)1.定義背包結(jié)構(gòu)體： struct stone { int name;int weight;//物品的剩余重量 int weight_t;//物品的重量 float benefit;//物品的價(jià)值 //float b;};2.定義函數(shù)void sort(stone *data,int num)//計(jì)算物品的單位重量的價(jià)值，并進(jìn)行排序 3.定義主函數(shù)并完成貪心選擇。4.分析算法復(fù)雜性分析： 該算法的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（n*logn）。 與0-1背包問(wèn)題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，可以選擇物品i 可以選擇物品 的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問(wèn)題都具有最優(yōu)子結(jié)構(gòu)，最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但 最優(yōu)子結(jié)構(gòu) 背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。 五、運(yùn)行結(jié)果 六、實(shí)驗(yàn)分析與討論 貪心法的基本思路： ——從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。該算法存在問(wèn)題： 1.不能保證求得的最后解是最佳的； 2.不能用來(lái)求最大或最小解問(wèn)題； 3.只能求滿足某些約束條件的可行解的范圍。實(shí)現(xiàn)該算法的過(guò)程： 1.Begin 從問(wèn)題的某一初始解出發(fā)； 2．while 能朝給定總目標(biāo)前進(jìn)一步 do 3.求出可行解的一個(gè)解元素； 4.由所有解元素組合成問(wèn)題的一個(gè)可行解 七、實(shí)驗(yàn)心得 貪心算法通過(guò)一系列的選擇來(lái)得知問(wèn)題的解，它所做的每一個(gè)選擇都是當(dāng)前狀態(tài)下局部最好選擇，即貪心選擇。通過(guò)背包問(wèn)題的解決，進(jìn)一步掌握了貪心算法的思想，并能在解問(wèn)題時(shí)靈活運(yùn)用。 指導(dǎo)教師對(duì)實(shí)驗(yàn)報(bào)告的評(píng)語(yǔ) 成績(jī)： 指導(dǎo)教師簽字： ****年**月**日 實(shí)驗(yàn)五：最小重量機(jī)器設(shè)計(jì)問(wèn)題（回溯法） 一、實(shí)驗(yàn)?zāi)康?/p> 建立算法復(fù)雜度的理論分析與實(shí)驗(yàn)分析的聯(lián)系，深刻體會(huì)算法復(fù)雜度作為算法的好壞評(píng)價(jià)指標(biāo)的本質(zhì)含義。 二、實(shí)驗(yàn)要求 1、用c++語(yǔ)言實(shí)現(xiàn)最小重量機(jī)器設(shè)計(jì)的回溯算法。 2、分析算法的計(jì)算復(fù)雜性 三、實(shí)驗(yàn)原理 首先，應(yīng)該明確的確定問(wèn)題的解空間。確定了解空間的組織結(jié)構(gòu)后，發(fā)從開(kāi)始節(jié)點(diǎn)（根節(jié)點(diǎn)）出發(fā)，以深度優(yōu)先方式搜索整個(gè)解空間。這個(gè)開(kāi)始結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，向縱深方向搜索移至一個(gè)新的結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為新的擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的活結(jié)點(diǎn)，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮菀赃@種工作方式遞歸的在解空間中搜索，直至找到所要求的解或解空間中已無(wú)活結(jié)點(diǎn)為止。 四、實(shí)驗(yàn)過(guò)程(步驟)由于題目已經(jīng)給出總價(jià)格的上限，因此算法通過(guò)使用回溯來(lái)選擇合適的機(jī)器使得在總價(jià)格不超過(guò)d時(shí)得到的機(jī)器重量最小。首先初始化當(dāng)前價(jià)格cp=0,當(dāng)前重量cw=0,此外，還要設(shè)置一個(gè)變量sum表示選擇機(jī)器的總重量，初始化其為每個(gè)部件從1號(hào)供應(yīng)商購(gòu)買的重量。在循環(huán)選擇i號(hào)機(jī)器時(shí)，判斷從j號(hào)供應(yīng)商購(gòu)買機(jī)器后的價(jià)格是否大于總價(jià)格，如果不大于則選擇，否則不選，繼續(xù)選擇下一供應(yīng)商進(jìn)行判斷。在得到一個(gè)合適的供應(yīng)商后，繼續(xù)選擇下一機(jī)器的供應(yīng)商，從第一個(gè)選到最后一個(gè)供應(yīng)商。當(dāng)所有機(jī)器選擇結(jié)束后，判斷得到的總重量是否比之前的sum小，如果小就賦給sum，然后從這一步開(kāi)始，回溯到上一機(jī)器，選擇下一合適供應(yīng)商，繼續(xù)搜索可行解，直到將整個(gè)排列樹(shù)搜索完畢。這樣，最終得到的sum即為最優(yōu)解。 數(shù)據(jù)說(shuō)明： N：零件數(shù)量 m：不同的零件商 W[][]:是從供應(yīng)商j處購(gòu)得的部件i的重量 c[][]：相應(yīng)的價(jià)值 算法設(shè)計(jì)： a.部件有n個(gè)，供應(yīng)商有m個(gè)，分別用w[i][j]和c[i][j]存儲(chǔ)從供應(yīng)商j 處購(gòu)得的部件i的重量和相應(yīng)價(jià)格，d為總價(jià)格的上限。 b.用遞歸函數(shù)backtrack(i)來(lái)實(shí)現(xiàn)回溯法搜索排列樹(shù)（形式參數(shù)i表示遞歸深度）。 ① 若cp>d，則為不可行解，剪去相應(yīng)子樹(shù)，返回到i-1層繼續(xù)執(zhí)行。 ② 若cw>=sum，則不是最優(yōu)解，剪去相應(yīng)子樹(shù)，返回到i-1層繼續(xù)執(zhí)行。 ③ 若i>n，則算法搜索到一個(gè)葉結(jié)點(diǎn)，用sum對(duì)最優(yōu)解進(jìn)行記錄，返回到i-1層繼續(xù)執(zhí)行； ④ 用for循環(huán)對(duì)部件i從m個(gè)不同的供應(yīng)商購(gòu)得的情況進(jìn)行選擇(1≤j≤m）。 c.主函數(shù)調(diào)用一次Knapsack(1)即可完成整個(gè)回溯搜索過(guò)程，最終得到的sum即為所求最小總重量。 五、運(yùn)行結(jié)果 六、實(shí)驗(yàn)心得 通過(guò)這次試驗(yàn)我明白了回溯法的思想，回溯法借助想象出來(lái)的樹(shù)的結(jié)構(gòu)，把問(wèn)題簡(jiǎn)單化，使得解問(wèn)題更方便。通過(guò)剪枝函數(shù)和約束函數(shù)對(duì)于求問(wèn)題的解有很大的幫助，但要把一些限制條件把剪枝函數(shù)抽象化。 指導(dǎo)教師對(duì)實(shí)驗(yàn)報(bào)告的評(píng)語(yǔ) 成績(jī)： 指導(dǎo)教師簽字： ****年**月**日 實(shí)驗(yàn)六：最小重量機(jī)器設(shè)計(jì)問(wèn)題（分支限界法） 一、實(shí)驗(yàn)時(shí)間：2013年11月12日，星期二，第一、二節(jié)地點(diǎn)：J13#328 二、實(shí)驗(yàn)?zāi)康募耙?/p> 1、了解分支限界法的基本思想。 2、運(yùn)用分支限界法解決最小重量機(jī)器設(shè)計(jì)問(wèn)題。 三、實(shí)驗(yàn)環(huán)境 平臺(tái)：win7操作系統(tǒng) 開(kāi)發(fā)工具：codeblocks10.05 四、實(shí)驗(yàn)內(nèi)容 最小重量機(jī)器設(shè)計(jì)問(wèn)題：設(shè)某一機(jī)器由n個(gè)部件組成，每一種部件可以從m個(gè)不同的供應(yīng)商處購(gòu)得。設(shè)wij是從供應(yīng)商j處購(gòu)得的部件i的重量，cij是相應(yīng)的價(jià)格。試設(shè)計(jì)一個(gè)算法，給出總價(jià)格不超過(guò)c的最小重量機(jī)器設(shè)計(jì) 五、算法描述及實(shí)驗(yàn)步驟 算法描述： 解空間為一棵排列樹(shù)，采用優(yōu)先隊(duì)列式分支限界法找出所給的最小重量機(jī)器設(shè)計(jì)，開(kāi)始時(shí)，將排列樹(shù)的根節(jié)點(diǎn)置為當(dāng)前擴(kuò)展結(jié)點(diǎn)。在初始擴(kuò)展結(jié)點(diǎn)處還設(shè)有選定部件是哪個(gè)供應(yīng)商提供的，故cv=0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]記錄供應(yīng)商的選擇while完成對(duì)排列樹(shù)內(nèi)部結(jié)點(diǎn)的有序擴(kuò)展。循環(huán)體內(nèi)依次從活結(jié)點(diǎn)優(yōu)先隊(duì)列中取出具有最小重量的結(jié)點(diǎn)，依次為當(dāng)前擴(kuò)展結(jié)點(diǎn)。并且花費(fèi)不超過(guò)c并加以擴(kuò)展，隊(duì)列為空時(shí)則結(jié)束循環(huán)。當(dāng)peer=n時(shí)，此時(shí)擴(kuò)展結(jié)點(diǎn)是葉節(jié)點(diǎn)，得到當(dāng)前的最小重量和最優(yōu)解數(shù)組x。若peer 實(shí)驗(yàn)步驟： 1.定義一個(gè)優(yōu)先隊(duì)列LinkQueue： void InitQueue(LinkQueue &Q);//創(chuàng)建一個(gè)隊(duì)列-----首尾結(jié)點(diǎn) void DestroyQueue(LinkQueue &Q);//銷毀一個(gè)隊(duì)列 void ClearQueue(LinkQueue &Q);//清空隊(duì)列 int QueueEmpty(LinkQueue &Q);//判斷隊(duì)列是否為空，空則返回TURE，否則返回FLASE int QueueLength(LinkQueue &Q);//求隊(duì)列的長(zhǎng)度 void EnQueue(LinkQueue &Q,QElemType &e);//拆入e為新的隊(duì)尾元素 void DeQueue(LinkQueue &Q,QElemType &e);//用e返回隊(duì)列的對(duì)頭元素 bool IsEmpty(LinkQueue &Q)//判斷隊(duì)列是否為空 2.定義類MinWeight，實(shí)現(xiàn)函數(shù)有： void Add(int wt,int ct,int i);//往隊(duì)列插入節(jié)點(diǎn) int FindBest();//實(shí)現(xiàn)最小重量機(jī)器的查找 void setMW();//函數(shù)初始化 void printMW();//打印輸出結(jié)果 3 實(shí)現(xiàn)主函數(shù)并完成所有代碼。 六、調(diào)試過(guò)程及實(shí)驗(yàn)結(jié)果 七、總結(jié) 利用分支限界法解決最小重量機(jī)器問(wèn)題，就是構(gòu)造一個(gè)優(yōu)先隊(duì)列，按照規(guī)定的優(yōu)先級(jí)按最大效益優(yōu)先的方式查找解空間樹(shù)，找出滿足要求的最優(yōu)解。通過(guò)利用分支限界法解決最小重量機(jī)器問(wèn)題，熟練了對(duì)分支限界法的使用。 指導(dǎo)教師對(duì)實(shí)驗(yàn)報(bào)告的評(píng)語(yǔ) 成績(jī)： 指導(dǎo)教師簽字： ****年**月**日 篇一：prim算法實(shí)驗(yàn)報(bào)告 算法實(shí)驗(yàn)報(bào)告 學(xué)院：xxx 班級(jí)：xxx 學(xué)號(hào)：xxx 姓名：xxx prim 篇二：prim最小生成樹(shù)算法實(shí)驗(yàn)報(bào)告 算法分析與設(shè)計(jì)之prim 學(xué)院：軟件學(xué)院 學(xué)號(hào)：201421031059 姓名：呂呂 一、問(wèn)題描述 1.prim的定義 prim算法是貪心算法的一個(gè)實(shí)例，用于找出一個(gè)有權(quán)重連通圖中的最小生成樹(shù)，即：具有最小權(quán)重且連接到所有結(jié)點(diǎn)的樹(shù)。(強(qiáng)調(diào)的是樹(shù)，樹(shù)是沒(méi)有回路的)。2.實(shí)驗(yàn)?zāi)康?/p> 選擇一門編程語(yǔ)言，根據(jù)prim算法實(shí)現(xiàn)最小生成樹(shù)，并打印最小生成樹(shù)權(quán)值。 二、算法分析與設(shè)計(jì) 1.prim算法的實(shí)現(xiàn)過(guò)程 基本思想：假設(shè)g＝(v，e)是連通的，te是g上最小生成樹(shù)中邊的集合。算法從u＝{u0}（u0∈v）、te＝{}開(kāi)始。重復(fù)執(zhí)行下列操作： 在所有u∈u，v∈v－u的邊(u，v)∈e中找一條權(quán)值最小的邊(u0,v0)并入集合te中，同時(shí)v0并入u，直到v＝u為止。 此時(shí)，te中必有n-1條邊，t=(v，te)為g的最小生成樹(shù)。prim算法的核心:始終保持te中的邊集構(gòu)成一棵生成樹(shù)。2.時(shí)間復(fù)雜度 prim算法適合稠密圖，其時(shí)間復(fù)雜度為o(n^2)，其時(shí)間復(fù)雜度與邊得數(shù)目無(wú)關(guān)，n為頂點(diǎn)數(shù)，而看ruskal算法的時(shí)間復(fù)雜度為o(eloge)跟邊的數(shù)目有關(guān)，適合稀疏圖。 三、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) 圖采用類存儲(chǔ)，定義如下： class graph { private: int *verticeslist;int **edge;int numvertices;int numedges;int maxvertices;graph();~graph();bool insertvertex(const int vertex);bool insertedge(int v1,int v2,int cost);int getvertexpos(int vertex);int getvalue(int i);int getweight(int v1,int v2);int numberofvertices();1 public: } void prim();其中，圖中結(jié)點(diǎn)連接情況及權(quán)值使用二重指針表示，即二維數(shù)組實(shí)現(xiàn)鄰接矩陣。 四、代碼與運(yùn)行結(jié)果 代碼運(yùn)行結(jié)果： 源碼： //普雷姆算法 #include int graph::getvalue(int i){ };int graph::getweight(int v1,int v2){ };int graph::numberofvertices(){ };int graph::numberofedges(){ };//插入結(jié)點(diǎn) bool graph::insertvertex(const int vertex){ };//插入邊，v1和v2為結(jié)點(diǎn)在數(shù)組的下標(biāo) bool graph::insertedge(int v1,int v2,int cost){ if(v1>-1&&v1 istream& operator>>(istream &in ,graph &g){ };//輸出圖對(duì)象 ostream& operator<<(ostream &out,graph &g){ int i,j,vertices,edges;int start,end,weight;vertices=g.numberofvertices();edges=g.numberofedges();out< in>>vertices>>edges;for(i=1;i<=vertices;i++){ } i=0;while(i 黃岡師范學(xué)院 提高型實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)課題 最小生成樹(shù)的prim算法 （實(shí)驗(yàn)類型：□綜合性 ■設(shè)計(jì)性 □應(yīng)用性） 實(shí)驗(yàn)課程 算法程序設(shè)計(jì) 實(shí)驗(yàn)時(shí)間2010年12月24日 學(xué)生姓名 周 媛鑫 專業(yè)班級(jí) 計(jì)科 0801 學(xué) 號(hào) 200826140110 一．實(shí)驗(yàn)?zāi)康暮鸵?/p> （1）根據(jù)算法設(shè)計(jì)需要, 掌握連通網(wǎng)的靈活表示方法;（2）掌握最小生成樹(shù)的prim算法;（3）熟練掌握貪心算法的設(shè)計(jì)方法;二．實(shí)驗(yàn)條件 （1）硬件環(huán)境：實(shí)驗(yàn)室電腦一臺(tái)（2）軟件環(huán)境：wintc 三．實(shí)驗(yàn)原理分析 （1）最小生成樹(shù)的定義： 假設(shè)一個(gè)單位要在n個(gè)辦公地點(diǎn)之間建立通信網(wǎng)，則連通n個(gè)地點(diǎn)只需要n-1條線路?？梢杂眠B通的無(wú)向網(wǎng)來(lái)表示n個(gè)地點(diǎn)以及它們之間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩地間的線路，賦于邊的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹(shù)，每一棵生成樹(shù)都可以表示一個(gè)通信網(wǎng)。其中一棵使總的耗費(fèi)最少，即邊的權(quán)值之和最小的生成樹(shù)，稱為最小生成樹(shù)。 （2）構(gòu)造最小生成樹(shù)可以用多種算法。其中多數(shù)算法利用了最小生成樹(shù)的下面一種簡(jiǎn)稱為mst的性質(zhì)：假設(shè)n=(v,{e})是一個(gè)連通網(wǎng)，u是頂點(diǎn)集v的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值（代價(jià)）的邊，其中u∈u，v∈v-u，則必存在一棵包含邊(u.v)的最小生成樹(shù)。（3）普里姆（prim）算法即是利用mst性質(zhì)構(gòu)造最小生成樹(shù)的算法。算法思想如下： 假設(shè)n=(v,{e})和是連通網(wǎng)，te是n上最小生成樹(shù)中邊的集合。算法從u={u0}(u0∈v)，te={}開(kāi)始，重復(fù)執(zhí)行下述操作：在所有u∈u，v∈v-u的邊(u, v)∈e中找一條代價(jià)最小的邊(u0, v0)并入集合te，同時(shí)v0并入u，直到u=v為止。此時(shí)te中必有n-1條邊，則t=(v,{te})為n的最小生成樹(shù)。四．實(shí)驗(yàn)步驟 （1）數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) ： 采用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)無(wú)向帶權(quán)圖更利于實(shí)現(xiàn)及操作： 鄰接矩陣的抽象數(shù)據(jù)結(jié)構(gòu)定義： #defineinfinityint_max //最大值 #define max_ertex_num20 //最大頂點(diǎn)數(shù) typedef enum {dg,dn,udg,udn}graphkind;//{有向圖,有向網(wǎng)，無(wú)向網(wǎng)，無(wú)向圖} typedef struct arc cell{ vrtype adj;// vrtype 是頂點(diǎn)關(guān)系的類型。對(duì)無(wú)權(quán)圖用1和0表示相鄰否； infotype * info;//該弧相關(guān)信息的指針 }arccell，adjmatrix [ max_vertex_num][max_vertex_num]； typedef struct { vertextype vexs [ max_vertex_num];//頂點(diǎn)向量adjmatrixarcs;// 鄰接矩陣 intvexnum , arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) graphkindkind;// 圖的種類標(biāo)志 }mgraph;（2）函數(shù)設(shè)計(jì) 函數(shù)名稱 函數(shù)原型 功能描述 main()int main(void)系統(tǒng)調(diào)用主函數(shù) huiru()void huitu()繪制無(wú)向圖 graphicver()void graphicver(graph *g)輸出鄰接矩陣 prim()void prim(graph *g)prim算法演示（3）實(shí)驗(yàn)源代碼 #include第二篇：《計(jì)算機(jī)算法》實(shí)驗(yàn)報(bào)告
第三篇：算法實(shí)驗(yàn)報(bào)告
第四篇：PRIM算法實(shí)驗(yàn)報(bào)告