算法試驗報告

1、華北電力大學實驗報告|實驗名稱 算法設計與分析綜合實驗課程名稱 算法設計與分析| |專業(yè)班級軟件12學生姓名：學 號：成 績：指導教師：胡朝舉實驗日期:實驗一分治策略一歸并排序一、實驗要求(1)編寫一個模板函數(shù)：template MergeSort(T *a, int n);以及相應的一系列函數(shù)，采用分治策略，對任意具有：bool operator(constT&x,const T&y);比較運算符的類型進行排序。(2)與STL庫中的函數(shù)std:sort(.)進行運行時間上的比較，給出比較結(jié)果， 如：動態(tài)生成100萬個隨機生成的附點數(shù)序列的排序列問題，給出所用的時間比 較。二、實驗代碼#inc

2、lude #include #include #include #define MAX 50typedef struct int arrMAX+1;int length;SortArr;SortArr *CreateSortArr() int i = 0;char buf4*MAX=;char *ptr = NULL;SortArr *sortArr = (SortArr *)malloc(sizeof(SortArr);n input:);memset(sortArr, 0, sizeof(SortArr);printf(請輸入待排序數(shù)據(jù)，以逗號分隔，以分號結(jié)束scanf(%s, buf);

3、ptr = buf;sortArr-arri = 0;i = 1;while(*ptr != ;) sortArr-arri = atoi(ptr); i+;ptr = strstr(ptr, ,);if(!ptr) break; ptr+;sortArr-length = (i - 1);return sortArr; int merge(int arr, int p, int q, int r) int i = 0;int j = 0;int k = 0;int n1 = 0;int n2 = 0;int *leftArr = NULL;int *rightArr = NULL; n1 =

4、 q - p + 1;n2 = r - q;leftArr = (int *)malloc(n1 + 2) * sizeof(int);rightArr = (int *)malloc(n2 + 2) * sizeof(int);for(i = 1; i = n1; i+)(leftArri = arrp+i-1;)for(j = 0; j = n2; j+)(rightArrj = arrq+j;)i = 1;j = 1;leftArrn1+1 = INT_MAX;rightArrn2+1 = INT_MAX;for(k = p; k = r; k+)(if(leftArri = right

5、Arrj)(arrk = leftArri;i+;)else(arrk = rightArrj;j+;)free(leftArr);free(rightArr);return 0;)int mergeSort(int arr, int p, int r)(int q = 0;if p length);return 0;)int PrintArray(SortArr sortArr)(int i = 0;for(i = 1; i = ; i+) ( printf(%d, i); ) printf(b;n);return 0;) int main()(SortArr *sortArr = NULL

6、;IsortArr = CreateSortArr();printf(nBefore Sort : t);PrintArray(*sortArr);MergingSortRecursion(sortArr);printf(Sorted Array : t);PrintArray(*sortArr);free(sortArr);return 0;)實驗二貪心算法Huffman樹及Huffman編碼一、實驗要求一個記錄字符及出現(xiàn)頻率的文件如下所示：,7, a,45, b,13, c,12, d,16, e,89, f,34, g,20試編寫一個讀取此種格式文件類CHuffman,內(nèi)部機制采用優(yōu)先隊

7、列，用于建立 Huffman樹及進行Huffman編碼輸出，其用法可以如下所示：CHuffman hm();();();();eight=weighti;elsehaffTreei.weight=0;arent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1; )eightm1&haffTreej.flag=0)(m2=m1;x2=x1;m1=haffTreej.weight;x1=j;)else if(haffTreej.weightm2&haffTreej.flag=0) (m2=haffTreej.wei

8、ght;x2=j;)couti=i m1 m2bitcd-start=0;arent;)itcd-start-j-1=cd-bitj;haffCodei.start=cd-start;haffCodei.weight=cd-weight;eight Code=;tart+1;jn;j+)for(j=0;jmyHaffCodei.start;j+)coutmyHaffCodei.bitj;m=m+myHaffCodei.weight*myHaffCodei.start;cout長度：myHaffCodei.startendl;)couthuffmansWPLis:;coutm;coutendl;

9、return 0;)實驗三用回溯方法求解n后問題、實驗要求問題：對任意給定的n求解n后問題。具體要求：1 .封裝n后問題為類，編寫以下兩種算法進行求解：(1)遞歸回溯方法；(2)迭代回溯方法。(選).對任意給定的n,要求輸出其解向量(所有解)，并輸出其解數(shù);.構(gòu)造n后問題的解數(shù)表格(由程序自動生成)：n后數(shù)解數(shù)A個解42(2,4,1,3)56參考類的封裝如下：class CQueen(public:CQueen(); xk-1時，判斷xk能否放置void BackTrack(int t);nnul);實驗四 最大子段和問題的求解一、實驗要求問題：對任意動態(tài)生成的n個整數(shù)(可含負數(shù))，求最大子段

10、及其和。具體要求：.采用至少三種方法進行求解：(1)蠻力方法(枚舉方法)；(2)分治策略；(3)動態(tài)規(guī)劃方法。.對算法和數(shù)據(jù)進行類的封裝，編寫好構(gòu)造函數(shù)和析構(gòu)函數(shù)；.對任意給定的n個整數(shù)，要求對以上的三種算法，都能夠輸出最大子段及其和。 注：教材中，對于分治策略及動態(tài)規(guī)劃方法，并沒有給出最大子段，只是給出了最大 子段和；請注意在編寫算法程序時的實現(xiàn)。class CMaxSum(private:int *m_a;wn價值v1v2vn具體要求：.將背包問題進行類的封裝；.能對任意給定的n種物品的重量、價值及背包限重，輸出以上表格 (或縱向輸出);.輸出背包問題的解；.本題要求采用STL庫中的排序算

11、法數(shù)據(jù)進行排序。二、實驗代碼#include struct goodinfo(float p; goodsi.p)(goodsi+1=goodsi;i-;goodsi+1=goods0;)=0；cu=M; cu)=1;cu=cu-goodsi.w;=cu/goodsi.w;laggoodsi.flag)(goodsi+1=goodsi;i-;)goodsi+1=goods0;)cout最優(yōu)解為:endl;for(i=1;i=n;i+)(cout第i件物品要放：；coutgoodsi.Xendl;)void main()(cout|運用貪心法解背包問題 |endl;int j;int n;flo

12、at M;goodinfo *goods;lag=i;cout請輸入第igoodsi.w;cout請輸入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;/ 得出物品的效益，重量比coutendl;)Insertionsort(goods,n);bag(goods,M,n);coutpress to run agianendl;coutpress to exitj;)三、實驗總結(jié)本次算法綜合實驗要求的綜合能力較高，需要對所學算法思想知識做到基本的 融會貫通。另外，還要具備編程的思想和能力，能靈活運用C+等高級語言來為 自己服務。在兩次實驗課堂上，我們應努力抓緊時間，當

13、然這時間還是不夠，所以正如老 師所建議的，需要同學在課下進行思考，提前做好準備，積極的投入到這場綜合 實驗編程中來，而不是光想著在兩堂實驗課上做出什么一鳴驚人的東西來但是，在課程結(jié)束后，我似乎忘了這荏，忘了提前做準備，所以只能在實驗課 上手忙腳亂，對此感到非常后悔。希望自己能充分認識到算法的重要性， 不要隨 著課程的結(jié)束就把它拋之腦后，而應該在平時的課下多進行思考， 對基本的算法 思考進行思考和研究。另外，不得不提的是對語言掌握的太差，編程基礎太差。剛開始上算法課時， 老師就強調(diào)了 C+語言的重要性，要好好掌握這門語言，用處很大。但我當時沒 有多當回事，并沒有像其他同學那樣借來 C+的相關書籍進行溫習和研究。后來 到了做實驗的時間，才發(fā)現(xiàn)書到用時方恨少的遺憾。 應該早早聽老師的話，及時 的撿起已經(jīng)開始遺忘的C+語言，把它理解透徹，弄熟，能靈活運用。還有，老師的開明態(tài)度也給了我們很大安慰。 第二堂實驗課時，我們都很著急， 既后悔自己沒有提前做準備，又為驗收擔憂。老師讓我們根據(jù)自己的能力做出亮 點的來驗收，這一方面給了我們喘息的時間，另一方面又讓我們認識到了不足。 同樣的學習時間，同樣的知識來源，最后出現(xiàn)了這樣