第一篇：《計算機算法》實驗報告范文(例文)

1.實驗名稱 本次實驗的名稱。

2.問題描述 對本次實驗要解決的問題的描述。

例子：處理漢諾塔問題時，描述什么是漢諾塔問題。

3.解決思路 采用什么方法；為什么可以采用這個方法； 例子：處理棋盤覆蓋問題時，采用什么方法：采用遞歸分治的方法處理； 為什么可以采用遞歸分治方法的原因（P21 頁圖 2-6 下面一段，理解之后用自己的話表述）：由于將棋盤橫、縱各一分為二之后，特殊方格必然位于四個小的棋盤之一，那么剩余的其余三個小棋盤是沒有方格的，如果采用某種 L 型骨牌覆蓋沒有特殊方格的三個小棋盤的中心相連部分（參見圖 2-6 的 b），則三個小棋盤都各有 1 個特殊方格所覆蓋。因此，這樣處理之后，原來大棋盤覆蓋的問題，就轉(zhuǎn)化為四個小棋盤覆蓋的問題，因此可以采用分治策略進行遞歸處理。

4.算法設(shè)計與分析 給出算法設(shè)計的基本思想，如：偽算法描述，遞歸方程等。并分析算法的時間復(fù)雜度（空間復(fù)雜度）。注意，一定要有文字說明。

例子：快速排序 偽算法描述 QuickSort(int a[], int p, int r){ 如果待排序數(shù)組 a[]中只有一個元素則直接返回； 如果待排序數(shù)組 a[]中不止一個元素，則進行如下處理 {

對數(shù)組 a[p:r]進行 Partition 劃分，使得 a[p:r]以 a[p]為標準，劃分為三個部分，即：

左半部分 a[p:q-1]；劃分基準 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)系”中的遞歸表達式，并給出文字說明。

注意：偽算法描述，或者遞歸方程不一定全部需要。根據(jù)問題的不同，只給出偽算法，或者只給出遞歸方程都可以。兩者同時給出也是可以的。

5.程序?qū)崿F(xiàn) 依據(jù)第 4 部分，給出 C 語言（其他語言亦可）的程序?qū)崿F(xiàn)，并進行算法時間（空間）復(fù)雜度分析。

程序?qū)崿F(xià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 進行劃分的標準；

/* 以下循環(huán)將數(shù)組 a[p:r]以 a[p]為標準進行劃分，在劃分完畢之后，* 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]中的元素總是 * 小于基準元素的，則是符合劃分標準的，因此，不用額外處理，* 循環(huán)一直繼續(xù),直到第一個不滿足劃分標準的 a[++i]（即 a[++i]>=i）

* 出現(xiàn)，或者整個數(shù)組 a[p:r]掃描完畢（即 i

*/

while(a[++i]

…… 6.總結(jié) 不用每個實驗寫一個總結(jié)，可以在一次課作業(yè)的最后寫一個總結(jié)。當然，如果需要，在每一個實驗結(jié)尾都寫一個總結(jié)也是可以的?？偨Y(jié)的目的是自己知識學習的總結(jié)、解決問題的總結(jié)、編程的總結(jié)等等。

第二篇：《計算機算法》實驗報告

1.實驗名稱

本次實驗的名稱。

2.問題描述

對本次實驗要解決的問題的描述。

例子：處理漢諾塔問題時，描述什么是漢諾塔問題。

3.解決思路

采用什么方法；為什么可以采用這個方法； 例子：處理棋盤覆蓋問題時，采用什么方法：采用遞歸分治的方法處理；

為什么可以采用遞歸分治方法的原因（P21頁圖2-6下面一段，理解之后用自己的話表述）：由于將棋盤橫、縱各一分為二之后，特殊方格必然位于四個小的棋盤之一，那么剩余的其余三個小棋盤是沒有方格的，如果采用某種L型骨牌覆蓋沒有特殊方格的三個小棋盤的中心相連部分（參見圖2-6的b），則三個小棋盤都各有1個特殊方格所覆蓋。因此，這樣處理之后，原來大棋盤覆蓋的問題，就轉(zhuǎn)化為四個小棋盤覆蓋的問題，因此可以采用分治策略進行遞歸處理。

4.算法設(shè)計與分析

給出算法設(shè)計的基本思想，如：偽算法描述，遞歸方程等。并分析算法的時間復(fù)雜度（空間復(fù)雜度）。注意，一定要有文字說明。例子：快速排序 偽算法描述

QuickSort(int a[], int p, int r){ 如果待排序數(shù)組a[]中只有一個元素則直接返回； 如果待排序數(shù)組a[]中不止一個元素，則進行如下處理 {

對數(shù)組a[p:r]進行Partition劃分，使得a[p:r]以a[p]為標準，劃分為三個部分，即：

左半部分a[p:q-1]；劃分基準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)系”中的遞歸表達式，并給出文字說明。注意：偽算法描述，或者遞歸方程不一定全部需要。根據(jù)問題的不同，只給出偽算法，或者只給出遞歸方程都可以。兩者同時給出也是可以的。

5.程序?qū)崿F(xiàn)

依據(jù)第4部分，給出C語言（其他語言亦可）的程序?qū)崿F(xiàn)，并進行算法時間（空間）復(fù)雜度分析。

程序?qū)崿F(xià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進行劃分的標準；

/* 以下循環(huán)將數(shù)組a[p:r]以a[p]為標準進行劃分，在劃分完畢之后，* 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]中的元素總是 * 小于基準元素的，則是符合劃分標準的，因此，不用額外處理，* 循環(huán)一直繼續(xù),直到第一個不滿足劃分標準的a[++i]（即a[++i]>=i）* 出現(xiàn)，或者整個數(shù)組a[p:r]掃描完畢（即i

while(a[++i]

??

6.總結(jié)

不用每個實驗寫一個總結(jié)，可以在一次課作業(yè)的最后寫一個總結(jié)。當然，如果需要，在每一個實驗結(jié)尾都寫一個總結(jié)也是可以的?？偨Y(jié)的目的是自己知識學習的總結(jié)、解決問題的總結(jié)、編程的總結(jié)等等。

第三篇：算法實驗報告

《算法設(shè)計與分析》

實驗報告

班級

姓名

學號

****年**月**日

目錄

實驗一

二分查找程序?qū)崿F(xiàn)…………………………………………………………………03頁

實驗二

棋盤覆蓋問題（分治法）.…………………………………………………………08頁

實驗三

0-1背包問題的動態(tài)規(guī)劃算法設(shè)計……………………………………………….11頁

實驗四

背包問題的貪心算法………………………………………………………………14頁

實驗五

最小重量機器設(shè)計問題（回溯法）………………………………………………17頁

實驗六

最小重量機器設(shè)計問題（分支限界法）…………………………………………20頁

指導(dǎo)教師對實驗報告的評語

成績：

指導(dǎo)教師簽字：

****年**月**日

實驗一：二分查找程序?qū)崿F(xiàn)

一、實驗時間：2013年10月8日，星期二，第一、二節(jié)地點：J13#328

二、實驗?zāi)康募耙?/p>

目的：

建立算法復(fù)雜度的理論分析與實驗分析的聯(lián)系，深刻體會算法復(fù)雜度作為算法的好壞評價指標的本質(zhì)含義。要求：

1、用c/c++語言實現(xiàn)二分搜索算法。

2、通過隨機產(chǎn)生有序表的方法，測出在平均意義下算法比較次數(shù)隨問題規(guī)模的變化曲線，并作圖。

三、實驗環(huán)境

平臺：Win7 32位操作系統(tǒng) 開發(fā)工具：Codeblocks10.05

四、實驗內(nèi)容

對已經(jīng)排好序的n個元素a[0：n-1]，現(xiàn)在要在這n個元素中找出一特定元素x。

五、算法描述及實驗步驟

算法描述：

折半查找法也稱為二分查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務(wù)。它的基本思想是，將n個元素分成個數(shù)大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果xa[n/2]，則我們只要在數(shù)組a的右半部繼續(xù)搜索x。二分搜索法的應(yīng)用極其廣泛，而且它的思想易于理解。確定算法復(fù)雜度基本步驟：

1、首先設(shè)定問題規(guī)模n；

2、隨即產(chǎn)生遞增數(shù)列；

3、在n個有序數(shù)中隨機取一個作為待查找量，搜索之；

4、記錄查找過程中的比較次數(shù)，再次生成新的有序表并查找，記錄查找次數(shù)，每個數(shù)組重復(fù)10次；

5、改變問題規(guī)模n重復(fù)上述步驟2~4，n取100、200……1000；

6、依實驗數(shù)據(jù)作圖，并與理論圖作比較；

7、二分搜索算法平均查找次數(shù)： 問題規(guī)模為n時，平均查找次數(shù)為： A(n)=Int(logn)+ 1/2 // Int()函數(shù)為向下取整

即二分搜索算法對于含有n個數(shù)據(jù)的有序表L平均作了約Int(logn)+1/2次的查找操作。

實驗步驟：

1.初始化生成遞增隨機數(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[]左下標，hight為數(shù)組b[]右下標。該算法實現(xiàn)過程為：

將數(shù)組b[]的n個元素分成個數(shù)大致相同的兩半，取b[n/2]與searchKey作比較。如果searchKey=b[n/2]，則找到searchKey，算法終止；如果searchKeyb[n/2]，則只要在數(shù)組b的右半部繼續(xù)搜索searchKey。

3.實現(xiàn)主函數(shù)并完成所有代碼。4.算法復(fù)雜性分析：

容易看出，沒執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O（logn）次。循環(huán)體內(nèi)運算需要O（1）時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O（logn）。

六、調(diào)試過程及實驗結(jié)果

輸出結(jié)果為：

Every array repeat search times: 10 Number of Elements

理論平均查找次數(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é)

二分查找在搜索有序表時，效率比較高。通過這次實驗我對二分查找算法的認識又有了新的提高。本想寫個圖形界面，但由于種種原因，沒有實現(xiàn)，下次做加密算法時，要寫一個圖形化界面。

指導(dǎo)教師對實驗報告的評語

成績：

指導(dǎo)教師簽字：

****年**月**日

實驗二：分治法解決棋盤問題

一、實驗時間：2013年10月22日，星期二，第一、二節(jié)地點：J13#328

二、實驗?zāi)康募耙?/p>

1、用c/c++語言實現(xiàn)分治法解決棋盤問題算法。

2、實現(xiàn)棋盤化以及棋盤覆蓋

三、實驗環(huán)境

Windows 2007 操作系統(tǒng)

以及code blocks軟件

四、實驗內(nèi)容

在一個2^k*2^k的方格組成的棋盤中，若恰有一個方格與其他方格不同，則稱該方格為一個特殊方格。用分治法將整個棋盤除特殊方格以外的方格覆蓋。

五、算法描述及實驗步驟 將2^k x 2^k的棋盤，先分成相等的四塊子棋盤，其中特殊方格位于四個中的一個，構(gòu)造剩下沒特殊方格三個子棋盤，將他們中的也假一個方格設(shè)為特殊方格。如果是：

左上的子棋盤（若不存在特殊方格）----則將該子棋盤右下角的那個方格假設(shè)為特殊方格 右上的子棋盤（若不存在特殊方格）----則將該子棋盤左下角的那個方格假設(shè)為特殊方格 左下的子棋盤（若不存在特殊方格）----則將該子棋盤右上角的那個方格假設(shè)為特殊方格 右下的子棋盤（若不存在特殊方格）----則將該子棋盤左上角的那個方格假設(shè)為特殊方格 當然上面四種，只可能且必定只有三個成立，那三個假設(shè)的特殊方格剛好構(gòu)成一個L型骨架，我們可以給它們作上相同的標記。這樣四個子棋盤就分別都和原來的大棋盤類似，我們就可以用遞歸算法解決。

六、調(diào)試過程及實驗結(jié)果

七、總結(jié)

由于覆蓋一個2k*2k棋盤所需的L型骨牌個數(shù)為（4k-1）/3，故此算法是一個在漸近意義下最優(yōu)的算法。

指導(dǎo)教師對實驗報告的評語

成績：

指導(dǎo)教師簽字：

****年**月**日

實驗三：0-1背包問題的動態(tài)規(guī)劃算法設(shè)計

一、實驗?zāi)康募耙?/p>

1.了解并掌握動態(tài)規(guī)劃算法的設(shè)計思想。

2.利用動態(tài)規(guī)劃算法的設(shè)計思想實現(xiàn)0-1背包問題的算法設(shè)計。

二、實驗環(huán)境

使用C++語言；

在windows環(huán)境下使用CodeBlocks調(diào)試并運行。

三、實驗內(nèi)容

1.了解并掌握動態(tài)規(guī)劃的設(shè)計思想。

2.利用動態(tài)規(guī)劃算法的思想解決0-1背包問題。

四、算法描述及實驗步驟

每種物品一件，可以選擇放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)試過程及實驗結(jié)果

六、總結(jié)

0-1背包問題是最基本的背包問題，它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成0-1背包問題求解。通過這次實驗我對動態(tài)規(guī)劃算法的認識又有了新的提高。

指導(dǎo)教師對實驗報告的評語

成績：

指導(dǎo)教師簽字：

****年**月**日

實驗四：背包問題的貪心算法

一、實驗?zāi)康模?/p>

運用貪心算法思想，設(shè)計解決上述問題的算法，找出最大背包價值的裝法。

二、實驗要求

1.用c++語言實現(xiàn)背包問題的貪心算法。

2.掌握貪心思想的應(yīng)用。

三、實驗原理

在貪心算法中采用逐步構(gòu)造最優(yōu)解的辦法，在每個階段，都做出一個看上去最優(yōu)的決策（在一定的標準下），決策一旦做出就不可更改。

四、實驗過程(步驟)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)//計算物品的單位重量的價值，并進行排序 3.定義主函數(shù)并完成貪心選擇。4.分析算法復(fù)雜性分析：

該算法的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為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背包問題卻不能用貪心算法求解。

五、運行結(jié)果

六、實驗分析與討論 貪心法的基本思路：

——從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某算法中的某一步不能再繼續(xù)前進時，算法停止。該算法存在問題：

1.不能保證求得的最后解是最佳的； 2.不能用來求最大或最小解問題；

3.只能求滿足某些約束條件的可行解的范圍。實現(xiàn)該算法的過程：

1.Begin 從問題的某一初始解出發(fā)； 2．while 能朝給定總目標前進一步 do 3.求出可行解的一個解元素；

4.由所有解元素組合成問題的一個可行解

七、實驗心得

貪心算法通過一系列的選擇來得知問題的解，它所做的每一個選擇都是當前狀態(tài)下局部最好選擇，即貪心選擇。通過背包問題的解決，進一步掌握了貪心算法的思想，并能在解問題時靈活運用。

指導(dǎo)教師對實驗報告的評語

成績：

指導(dǎo)教師簽字：

****年**月**日

實驗五：最小重量機器設(shè)計問題（回溯法）

一、實驗?zāi)康?/p>

建立算法復(fù)雜度的理論分析與實驗分析的聯(lián)系，深刻體會算法復(fù)雜度作為算法的好壞評價指標的本質(zhì)含義。

二、實驗要求

1、用c++語言實現(xiàn)最小重量機器設(shè)計的回溯算法。

2、分析算法的計算復(fù)雜性

三、實驗原理

首先，應(yīng)該明確的確定問題的解空間。確定了解空間的組織結(jié)構(gòu)后，發(fā)從開始節(jié)點（根節(jié)點）出發(fā)，以深度優(yōu)先方式搜索整個解空間。這個開始結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點。在當前的擴展結(jié)點處，向縱深方向搜索移至一個新的結(jié)點。這個新結(jié)點成為新的活結(jié)點，并成為新的擴展結(jié)點。如果在當前的擴展結(jié)點處不能再向縱深方向移動，則當前擴展結(jié)點成為死結(jié)點。此時，應(yīng)往回移動（回溯）至最近的活結(jié)點，并使這個活結(jié)點成為當前的擴展結(jié)點?；厮菀赃@種工作方式遞歸的在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點為止。

四、實驗過程(步驟)由于題目已經(jīng)給出總價格的上限，因此算法通過使用回溯來選擇合適的機器使得在總價格不超過d時得到的機器重量最小。首先初始化當前價格cp=0,當前重量cw=0,此外，還要設(shè)置一個變量sum表示選擇機器的總重量，初始化其為每個部件從1號供應(yīng)商購買的重量。在循環(huán)選擇i號機器時，判斷從j號供應(yīng)商購買機器后的價格是否大于總價格，如果不大于則選擇，否則不選，繼續(xù)選擇下一供應(yīng)商進行判斷。在得到一個合適的供應(yīng)商后，繼續(xù)選擇下一機器的供應(yīng)商，從第一個選到最后一個供應(yīng)商。當所有機器選擇結(jié)束后，判斷得到的總重量是否比之前的sum小，如果小就賦給sum，然后從這一步開始，回溯到上一機器，選擇下一合適供應(yīng)商，繼續(xù)搜索可行解，直到將整個排列樹搜索完畢。這樣，最終得到的sum即為最優(yōu)解。

數(shù)據(jù)說明：

N：零件數(shù)量

m：不同的零件商

W[][]:是從供應(yīng)商j處購得的部件i的重量

c[][]：相應(yīng)的價值 算法設(shè)計：

a.部件有n個，供應(yīng)商有m個，分別用w[i][j]和c[i][j]存儲從供應(yīng)商j 處購得的部件i的重量和相應(yīng)價格，d為總價格的上限。

b.用遞歸函數(shù)backtrack(i)來實現(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é)點，用sum對最優(yōu)解進行記錄，返回到i-1層繼續(xù)執(zhí)行；

④ 用for循環(huán)對部件i從m個不同的供應(yīng)商購得的情況進行選擇(1≤j≤m）。

c.主函數(shù)調(diào)用一次Knapsack(1)即可完成整個回溯搜索過程，最終得到的sum即為所求最小總重量。

五、運行結(jié)果

六、實驗心得

通過這次試驗我明白了回溯法的思想，回溯法借助想象出來的樹的結(jié)構(gòu)，把問題簡單化，使得解問題更方便。通過剪枝函數(shù)和約束函數(shù)對于求問題的解有很大的幫助，但要把一些限制條件把剪枝函數(shù)抽象化。

指導(dǎo)教師對實驗報告的評語

成績：

指導(dǎo)教師簽字：

****年**月**日

實驗六：最小重量機器設(shè)計問題（分支限界法）

一、實驗時間：2013年11月12日，星期二，第一、二節(jié)地點：J13#328

二、實驗?zāi)康募耙?/p>

1、了解分支限界法的基本思想。

2、運用分支限界法解決最小重量機器設(shè)計問題。

三、實驗環(huán)境

平臺：win7操作系統(tǒng)

開發(fā)工具：codeblocks10.05

四、實驗內(nèi)容

最小重量機器設(shè)計問題：設(shè)某一機器由n個部件組成，每一種部件可以從m個不同的供應(yīng)商處購得。設(shè)wij是從供應(yīng)商j處購得的部件i的重量，cij是相應(yīng)的價格。試設(shè)計一個算法，給出總價格不超過c的最小重量機器設(shè)計

五、算法描述及實驗步驟

算法描述：

解空間為一棵排列樹，采用優(yōu)先隊列式分支限界法找出所給的最小重量機器設(shè)計，開始時，將排列樹的根節(jié)點置為當前擴展結(jié)點。在初始擴展結(jié)點處還設(shè)有選定部件是哪個供應(yīng)商提供的，故cv=0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]記錄供應(yīng)商的選擇while完成對排列樹內(nèi)部結(jié)點的有序擴展。循環(huán)體內(nèi)依次從活結(jié)點優(yōu)先隊列中取出具有最小重量的結(jié)點，依次為當前擴展結(jié)點。并且花費不超過c并加以擴展，隊列為空時則結(jié)束循環(huán)。當peer=n時，此時擴展結(jié)點是葉節(jié)點，得到當前的最小重量和最優(yōu)解數(shù)組x。若peer

實驗步驟：

1.定義一個優(yōu)先隊列LinkQueue：

void InitQueue(LinkQueue &Q);//創(chuàng)建一個隊列-----首尾結(jié)點 void DestroyQueue(LinkQueue &Q);//銷毀一個隊列 void ClearQueue(LinkQueue &Q);//清空隊列

int QueueEmpty(LinkQueue &Q);//判斷隊列是否為空，空則返回TURE，否則返回FLASE int QueueLength(LinkQueue &Q);//求隊列的長度

void EnQueue(LinkQueue &Q,QElemType &e);//拆入e為新的隊尾元素 void DeQueue(LinkQueue &Q,QElemType &e);//用e返回隊列的對頭元素 bool IsEmpty(LinkQueue &Q)//判斷隊列是否為空 2.定義類MinWeight，實現(xiàn)函數(shù)有：

void Add(int wt,int ct,int i);//往隊列插入節(jié)點 int FindBest();//實現(xiàn)最小重量機器的查找 void setMW();//函數(shù)初始化 void printMW();//打印輸出結(jié)果 3 實現(xiàn)主函數(shù)并完成所有代碼。

六、調(diào)試過程及實驗結(jié)果

七、總結(jié)

利用分支限界法解決最小重量機器問題，就是構(gòu)造一個優(yōu)先隊列，按照規(guī)定的優(yōu)先級按最大效益優(yōu)先的方式查找解空間樹，找出滿足要求的最優(yōu)解。通過利用分支限界法解決最小重量機器問題，熟練了對分支限界法的使用。

指導(dǎo)教師對實驗報告的評語

成績：

指導(dǎo)教師簽字：

****年**月**日

第四篇：PRIM算法實驗報告

篇一：prim算法實驗報告

算法實驗報告

學院：xxx 班級：xxx 學號：xxx 姓名：xxx prim 篇二：prim最小生成樹算法實驗報告 算法分析與設(shè)計之prim 學院：軟件學院 學號：201421031059 姓名：呂呂

一、問題描述 1.prim的定義

prim算法是貪心算法的一個實例，用于找出一個有權(quán)重連通圖中的最小生成樹，即：具有最小權(quán)重且連接到所有結(jié)點的樹。(強調(diào)的是樹，樹是沒有回路的)。2.實驗?zāi)康?/p>

選擇一門編程語言，根據(jù)prim算法實現(xiàn)最小生成樹，并打印最小生成樹權(quán)值。

二、算法分析與設(shè)計

1.prim算法的實現(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為頂點數(shù)，而看ruskal算法的時間復(fù)雜度為o(eloge)跟邊的數(shù)目有關(guān)，適合稀疏圖。

三、數(shù)據(jù)結(jié)構(gòu)的設(shè)計 圖采用類存儲，定義如下： 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é)點連接情況及權(quán)值使用二重指針表示，即二維數(shù)組實現(xiàn)鄰接矩陣。

四、代碼與運行結(jié)果 代碼運行結(jié)果：

源碼：

//普雷姆算法

#include using namespace std;const int maxweight=10000;const int defaultvertices=10000;const int maxedges=10000;const int maxint = 10000000;class graph{ private: int *verticeslist;2 };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();int numberofedges();void prim();void lvlv(graph &g);public: istream& operator>>(istream& in,graph &g);ostream& operator<<(ostream& out,graph &g);//默認構(gòu)造函數(shù) graph::graph(){ };graph::~graph(){ delete []verticeslist;delete []edge;3 maxvertices=defaultvertices;numvertices=0;numedges=0;int i,j;verticeslist=new int [maxvertices];edge=(int **)new int *[maxvertices];for(i=0;i

int graph::getvalue(int i){ };int graph::getweight(int v1,int v2){ };int graph::numberofvertices(){ };int graph::numberofedges(){ };//插入結(jié)點 bool graph::insertvertex(const int vertex){ };//插入邊，v1和v2為結(jié)點在數(shù)組的下標

bool graph::insertedge(int v1,int v2,int cost){

if(v1>-1&&v1-1&&v2=0&&i<=numvertices)?verticeslist[i]:null;return(v1!=-1&&v2!=-1)?edge[v1][v2]:0;return numvertices;return numedges;if(numvertices==maxvertices)return false;verticeslist[numvertices++]=vertex;return true;};} return true;else return false;//輸入圖信息

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>start>>end>>weight;j=g.getvertexpos(start);k=g.getvertexpos(end);if(j==-1||k==-1){} g.insertedge(j,k,weight);i++;cout<

黃岡師范學院 提高型實驗報告

實驗課題 最小生成樹的prim算法

（實驗類型：□綜合性 ■設(shè)計性 □應(yīng)用性）

實驗課程 算法程序設(shè)計 實驗時間2010年12月24日

學生姓名 周 媛鑫 專業(yè)班級 計科 0801 學 號 200826140110 一．實驗?zāi)康暮鸵?/p>

（1）根據(jù)算法設(shè)計需要, 掌握連通網(wǎng)的靈活表示方法;（2）掌握最小生成樹的prim算法;（3）熟練掌握貪心算法的設(shè)計方法;二．實驗條件

（1）硬件環(huán)境：實驗室電腦一臺（2）軟件環(huán)境：wintc 三．實驗原理分析

（1）最小生成樹的定義：

假設(shè)一個單位要在n個辦公地點之間建立通信網(wǎng)，則連通n個地點只需要n-1條線路。可以用連通的無向網(wǎng)來表示n個地點以及它們之間可能設(shè)置的通信線路，其中網(wǎng)的頂點表示城市，邊表示兩地間的線路，賦于邊的權(quán)值表示相應(yīng)的代價。對于n個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以表示一個通信網(wǎng)。其中一棵使總的耗費最少，即邊的權(quán)值之和最小的生成樹，稱為最小生成樹。

（2）構(gòu)造最小生成樹可以用多種算法。其中多數(shù)算法利用了最小生成樹的下面一種簡稱為mst的性質(zhì)：假設(shè)n=(v,{e})是一個連通網(wǎng)，u是頂點集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的最小生成樹。四．實驗步驟

（1）數(shù)據(jù)結(jié)構(gòu)的設(shè)計 ：

采用鄰接矩陣的存儲結(jié)構(gòu)來存儲無向帶權(quán)圖更利于實現(xiàn)及操作： 鄰接矩陣的抽象數(shù)據(jù)結(jié)構(gòu)定義： #defineinfinityint_max //最大值

#define max_ertex_num20 //最大頂點數(shù)

typedef enum {dg,dn,udg,udn}graphkind;//{有向圖,有向網(wǎng)，無向網(wǎng)，無向圖} typedef struct arc cell{ vrtype adj;// vrtype 是頂點關(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];//頂點向量adjmatrixarcs;// 鄰接矩陣 intvexnum , arcnum;//圖的當前頂點數(shù)和弧數(shù) graphkindkind;// 圖的種類標志 }mgraph;（2）函數(shù)設(shè)計

函數(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）實驗源代碼

#include #include #include #include #include #define maxvertexnum 50 #define inf 32767 typedef struct graphic {char vexs[maxvertexnum];int edges[maxvertexnum][maxvertexnum];int v,e;}graph;char tmp[10];void huitu()/*無向圖的圖形生成*/ {char buffer[100];int graphdriver = detect, graphmode;int i,xbefore,ybefore;int x1,y1;char c;/*registerbgidriver(egavga_driver);initgraph(&graphdriver, &graphmode,);cleardevice();printf(input pot(300v,&g->e);for(i=1;i<=g->v;i++)for(j=1;j<=g->v;j++)if(i==j)g->edges[i][j]=0;else{ g->edges[i][j]=inf;} for(k=1;k<=g->e;k++){printf(input %dth edge :,k);scanf(%d,%d,%d,&v1,&v2,&weight);g->edges[v1][v2]=g->edges[v2][v1]=weight;} for(i=1;i<=g->v;i++){printf(n);for(j=1;j<=g->v;j++)printf((g->edges[i][j]==inf)?∞t:%dt,g->edges[i][j]);} printf(n);system(pause);} /***************prim 算法生成最小生成樹***************/ void prim(graph *g){int lowcost[maxvertexnum],closest[maxvertexnum];int i,j,k,min;for(i=2;i<=g->v;i++)/*n個頂點，n-1條邊 */ {lowcost[i]=g->edges[1][i];closest[i]=1;} lowcost[1]=0;/*標志頂點1加入u集合*/ for(i=2;i<=g->v;i++)/*形成n-1條邊的生成樹 */ {min=inf;k=0;for(j=2;j<=g->v;j++)if((lowcost[j]v;j++)/*修改由頂點k到其他頂點邊的權(quán)值*/ if(g->edges[k][j]edges[k][j];closest[j]=k;}printf(n);} } setviewport(150,140,630,310,1);cleardevice();setcolor(green);rectangle(10,10,470,160);line(10,60,470,60);line(10,110,470,110);for(i=0;i