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