算法試驗(yàn)報(bào)告

1、華北電力大學(xué)實(shí)驗(yàn)報(bào)告|實(shí)驗(yàn)名稱 算法設(shè)計(jì)與分析綜合實(shí)驗(yàn)課程名稱 算法設(shè)計(jì)與分析| |專業(yè)班級(jí)軟件12學(xué)生姓名：學(xué) 號(hào)：成 績(jī)：指導(dǎo)教師：胡朝舉實(shí)驗(yàn)日期:實(shí)驗(yàn)一分治策略一歸并排序一、實(shí)驗(yàn)要求(1)編寫(xiě)一個(gè)模板函數(shù)：template MergeSort(T *a, int n);以及相應(yīng)的一系列函數(shù)，采用分治策略，對(duì)任意具有：bool operator(constT&x,const T&y);比較運(yùn)算符的類型進(jìn)行排序。(2)與STL庫(kù)中的函數(shù)std:sort(.)進(jìn)行運(yùn)行時(shí)間上的比較，給出比較結(jié)果， 如：動(dòng)態(tài)生成100萬(wàn)個(gè)隨機(jī)生成的附點(diǎn)數(shù)序列的排序列問(wèn)題，給出所用的時(shí)間比 較。二、實(shí)驗(yàn)代碼#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(請(qǐng)輸入待排序數(shù)據(jù)，以逗號(hào)分隔，以分號(hào)結(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;)實(shí)驗(yàn)二貪心算法Huffman樹(shù)及Huffman編碼一、實(shí)驗(yàn)要求一個(gè)記錄字符及出現(xiàn)頻率的文件如下所示：,7, a,45, b,13, c,12, d,16, e,89, f,34, g,20試編寫(xiě)一個(gè)讀取此種格式文件類CHuffman,內(nèi)部機(jī)制采用優(yōu)先隊(duì)

7、列，用于建立 Huffman樹(shù)及進(jìn)行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長(zhǎng)度：myHaffCodei.startendl;)couthuffmansWPLis:;coutm;coutendl;

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

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

11、法數(shù)據(jù)進(jìn)行排序。二、實(shí)驗(yàn)代碼#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|運(yùn)用貪心法解背包問(wèn)題 |endl;int j;int n;flo

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

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