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