算法实验报告(共16页).doc

《算法实验报告(共16页).doc》由会员分享，可在线阅读，更多相关《算法实验报告(共16页).doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上华北电力大学实 验 报 告| 实验名称 算法设计与分析综合实验 课程名称 算法设计与分析 | 专业班级 软件12 学生姓名： 学 号： 成 绩：指导教师：胡朝举 实验日期：2014.12 实验一 分治策略归并排序一、实验要求（1）编写一个模板函数：template ，MergeSort(T *a, int n);以及相应的一系列函数，采用分治策略，对任意具有:bool operator(const T&x,const T&y);比较运算符的类型进行排序。（2）与STL库中的函数std:sort(.)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附

2、点数序列的排序列问题, 给出所用的时间比较。二、实验代码#include #include #include #include #define MAX 50 typedef struct int arrMAX+1; int length; SortArr; SortArr *CreateSortArr() int i = 0; char buf4*MAX = ; char *ptr = NULL; SortArr *sortArr = (SortArr *)malloc(sizeof(SortArr); memset(sortArr, 0, sizeof(SortArr); printf(请输

3、入待排序数据，以逗号分隔，以分号结束n input:); scanf(%s, buf); 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; i

4、nt n2 = 0; int *leftArr = NULL; int *rightArr = NULL; n1 = 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;

5、 rightArrn2+1 = INT_MAX; for(k = p; k = r; k+) if(leftArri = rightArrj) 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 = sortArr.l

6、ength; i+) printf(%d, sortArr.arri); printf(b;n); return 0; int main() SortArr *sortArr = NULL; sortArr = CreateSortArr(); printf(nBefore Sort：t); PrintArray(*sortArr); MergingSortRecursion(sortArr); printf(Sorted Array：t); PrintArray(*sortArr); free(sortArr); return 0; 实验二 贪心算法Huffman树及Huffman编码一、实

7、验要求 一个记录字符及出现频率的文件如下所示： Huffman.haf，7，a,45，b,13，c,12，d,16，e,89，f,34，g,20试编写一个读取此种格式文件类CHuffman, 内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：CHuffman hm(huffman.dat);hm.CreateTree();hm.OutputTree();hm.OutputCode(); /二进制形式的字符串对于输出树的形式可自行决定(如图形界面或字符界面)。二、 实验代码 #include #include using namespace std;

8、 const int MaxValue =10000;/初始设定的权值最大值 const int MaxBit =4;/初始设定的最大编码位数 const int MaxN=10;/初始设定的最大结点个数 struct HaffNode/哈夫曼树的结点结构 int weight;/权值 int flag;/标记 int parent;/双亲结点下标 int leftChild;/左孩子下标 int rightChild;/右孩子下标 ; struct Code/存放哈夫曼编码的数据元素结构 int bitMaxBit;/数组 int start;/编码的起始下标 int weight;/字符的

9、权值 ; /weight:由小到大排序 void Haffman(int weight, int n, HaffNode haffTree) /建立叶结点个数为n权值为weight的哈夫曼树haffTree int j,m1,m2,x1,x2; /哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点 for(int i=0;i2*n-1;i+) if(in) haffTreei.weight=weighti; else haffTreei.weight=0; /注意这里没打else那，故无论是n个叶子节点还是n-1个非叶子节点都会进行下面4步的初始化 haffTreei.pa

10、rent=0; haffTreei.flag=0; haffTreei.leftChild=-1; haffTreei.rightChild=-1; /构造哈夫曼树haffTree的n-1个非叶结点 for(int i=0;in-1;i+) m1=m2=MaxValue;/Maxvalue=10000;(就是一个相当大的数) x1=x2=0;/x1、x2是用来保存最小的两个值在数组对应的下标 for(j=i;jn+i;j+)/循环找出所有权重中，最小的二个值-morgan if(haffTreej.weightm1&haffTreej.flag=0) m2=m1; x2=x1; m1=haff

11、Treej.weight; x1=j; else if(haffTreej.weightm2&haffTreej.flag=0) m2=haffTreej.weight; x2=j; couti=i m1 m2endl; /将找出的两棵权值最小的子树合并为一棵子树 haffTreex1.parent=n+i; haffTreex2.parent=n+i; haffTreex1.flag=1; haffTreex2.flag=1; haffTreen+i.weight=haffTreex1.weight+haffTreex2.weight; haffTreen+i.leftChild=x1; h

12、affTreen+i.rightChild=x2; void HaffmanCode(HaffNode haffTree,int n,Code haffCode) /由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode Code*cd=new Code; int child, parent; /求n个叶结点的哈夫曼编码 for(int i=0;istart=n-1;/不等长编码的最后一位为n-1, cd-start=0;/,-修改从0开始计数-morgan cd-weight=haffTreei.weight;/取得编码对应权值的字符 child=i; parent=haffTr

13、eechild.parent; /由叶结点向上直到根结点 while(parent!=0) if(haffTreeparent.leftChild=child) cd-bitcd-start=0;/左孩子结点编码0 else cd-bitcd-start=1;/右孩子结点编码1 /cd-start-; cd-start+;/改成编码自增-morgan child=parent; parent=haffTreechild.parent; /保存叶结点的编码和不等长编码的起始位 /for(intj=cd-start+1;jstart-1;j=0;j-)/重新修改编码，从根节点开始计数-morgan

14、 haffCodei.bitcd-start-j-1=cd-bitj; haffCodei.start=cd-start; haffCodei.weight=cd-weight;/保存编码对应的权值 int main() int i, j, n=4,m=0; int weight=2,4,5,7; /int weight=7,5,4,2; HaffNode*myHaffTree=new HaffNode2*n-1; Code*myHaffCode=new Coden; if(nMaxN) cout定义的n越界，修改MaxN!endl; exit(0); Haffman(weight,n,myH

15、affTree); HaffmanCode(myHaffTree,n,myHaffCode); /输出每个叶结点的哈夫曼编码 for(i=0;in;i+) coutWeight=myHaffCodei.weight Code=; /for(j=myHaffCodei.start+1;jn;j+) for(j=0;jmyHaffCodei.start;j+) coutmyHaffCodei.bitj; m=m+myHaffCodei.weight*myHaffCodei.start; cout 长度：myHaffCodei.startendl; couthuffmansWPLis:; coutm

16、; coutendl; return 0; 实验三 用回溯方法求解n后问题一、 实验要求问题：对任意给定的n求解n后问题。具体要求： 1封装n后问题为类，编写以下两种算法进行求解：（1）递归回溯方法；（2）迭代回溯方法。(选)2对任意给定的n，要求输出其解向量（所有解），并输出其解数；3构造n后问题的解数表格（由程序自动生成）:n 后数解数第一个解42(2,4,1,3)56参考类的封装如下：class CQueenpublic:CQueen(); /缺省构造函数CQueen(int n);CQueen();void IniQueen(int n);void ToPrintAll(); /求出所

17、有的解并输出void ToPrint(int m); /输出前m个解;void ToGetFirstAndSum(); /求出所有解的总和及第一个解; (为了生成以上所示的表格)private:int m_n; /皇后数long m_sum;/总解数;int *m_x; /解向量;int *m_FirstX; /第一个解向量;bool m_bPlace(int k); /当主生了x0.xk-1时，判断xk 能否放置void BackTrack(int t);/ BackTrack-Method/为了输出前m个解，可能需要增加其它的变量;二、 实验代码#include #include #inc

18、lude #include class Queenfriend int nQueen(int);private:bool Place(int k);void Backtrack(int t);void Output();int n,/皇后个数*x;/当前解long sum;/当前已找到的可行性方案数;bool Queen:Place(int k)for (int j=1;jn)sum+;Output();elsefor (int i=1;i=n;i+)xt = i;if (Place(t)Backtrack(t+1);int nQueen(int n)Queen X;X.n = n;X.sum

19、 = 0;int *p = new intn+1;for (int i=0;i=n;i+)pi = 0;X.x = p;X.Backtrack(1);delete p;return X.sum;void Queen:Output()coutn* 第sum图解 *n;cout;/head行for(int k=1;kn;k+)cout;coutn;for (int i=1;i=n;i+)cout;for (int j=1;j=xi-1;j+) cout ; cout,xi+1;cout; for (j=xi;j=n-1;j+) cout ; coutn; if(in) cout;/间行 for(k

20、=1;kn;k+) cout; coutn-1) cout;/end行 for(k=1;kn;k+) cout; coutn; coutendl;void main()int n;coutn;int iStart,iEnd;iStart = GetTickCount();/得到系统时间nQueen(n);iEnd = GetTickCount();/得到系统时间coutIt need iEnd-iStartms to solve the problem.nnul);实验四 最大子段和问题的求解一、实验要求 问题：对任意动态生成的n 个整数（可含负数），求最大子段及其和。具体要求：1采用至少三种

21、方法进行求解：(1)蛮力方法（枚举方法）;(2) 分治策略；（3）动态规划方法。2对算法和数据进行类的封装，编写好构造函数和析构函数；3对任意给定的n个整数，要求对以上的三种算法，都能够输出最大子段及其和。注：教材中，对于分治策略及动态规划方法，并没有给出最大子段，只是给出了最大子段和；请注意在编写算法程序时的实现。class CMaxSumprivate:int *m_a;/存储n个整数;int m_n;int m_i, m_j;/最大子段public:CMaxSum();CMaxSum();void ToIni();/初始化整数序列void BruteForce();/蛮力方法void D

22、ivideAndConquer(); /需要另一个递归算法void DynamicProg();/Dynamic Programming 动态规划算法void Output(); /输出解;二、实验代码#include #include #include using namespace std; #define MAX 10000 int BF_Sum(int a,int n) int max=0; int sum=0; int i,j; for (i=0;in-1;i+) sum=ai; for(j=i+1;j=max) max=sum; sum+=aj; return max; int m

23、axSum1(int a,int left, int right) int sum = 0; if(left = right) /如果序列长度为1，直接求解 if(aleft 0) sum = aleft; else sum = 0; else int center = (left + right) / 2; /划分 int leftsum = maxSum1(a,left,center); /对应情况1，递归求解 int rightsum = maxSum1(a, center + 1, right);/对应情况2， 递归求解 int s1 = 0; int lefts = 0; for(i

24、nt i = center; i = left; i-) /求解s1 lefts += ai; if(lefts s1) s1 = lefts; /左边最大值放在s1 int s2 = 0; int rights = 0; for(int j = center + 1; j s2) s2 =rights; sum = s1 + s2; /计算第3钟情况的最大子段和 if(sum leftsum) sum = leftsum; /合并，在sum、leftsum、rightsum中取最大值 if(sum rightsum) sum = rightsum; return sum; int DY_Su

25、m(int a,int n) int sum = 0; int *b = (int *) malloc(n * sizeof(int); /动态为数组分配空间 b0 = a0; for(int i = 1; i 0) bi = bi - 1 + ai; else bi = ai; for(int j = 0; j sum) sum = bj; delete b; /释放内存 return sum; int main() int numMAX; int i; const int n = 40; LARGE_INTEGER begin,end,frequency; QueryPerformance

26、Frequency(&frequency); /生成随机序列 cout生成随机序列：; srand(time(0); for(i = 0; i n; i+) if(rand() % 2 = 0) numi = rand(); else numi = (-1) * rand(); if(n 100) coutnumi ; coutendl; /蛮力法/ coutn蛮力法:endl; cout最大字段和：; QueryPerformanceCounter(&begin); coutBF_Sum(num,n)endl; QueryPerformanceCounter(&end); cout时间: (

27、double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart sendl; coutn分治法:endl; cout最大字段和：; QueryPerformanceCounter(&begin); coutmaxSum1(num,0,n)endl; QueryPerformanceCounter(&end); cout时间: (double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart sendl; coutn动态规划法:endl; cout最大字段和：; QueryPerfor

28、manceCounter(&begin); coutDY_Sum(num,n)endl; QueryPerformanceCounter(&end); cout时间: (double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart sendl; system(pause); return 0; 实验五 背包问题的贪心算法一、实验要求问题: 给定如下n种物品的编号，及其价值；背包重量为c, 求最佳装包方案，才能使其装入背包的价值最大。物品编号12n重量w1w2.wn价值v1v2vn具体要求：1 将背包问题进行类的封装；2 能对任意给定的n

29、种物品的重量、价值及背包限重，输出以上表格( 或纵向输出)；3 输出背包问题的解；4 本题要求采用STL库中的排序算法数据进行排序。二、 实验代码#include struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号;/物品信息结构体void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列void ba

30、g(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i=n;i+) goodsi.X=0; cu=M; /背包剩余容量 for(i=1;icu)/当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/确定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/该物品所要放的量/*按物品编号做降序排列*/ for(j=2;j=n;j+) goods0=goodsj; i=j-1; while (goods0.flaggoodsi.flag) goodsi+1=go

31、odsi; i-; goodsi+1=goods0; cout最优解为:endl; for(i=1;i=n;i+) cout第i件物品要放:; coutgoodsi.Xendl; void main() cout|-运用贪心法解背包问题-|endl; int j; int n; float M; goodinfo *goods;/定义一个指针 while(j) coutn; goods=new struct goodinfo n+1;/ coutM; coutendl; int i; for(i=1;i=n;i+) goodsi.flag=i; cout请输入第igoodsi.w; cout请

32、输入第igoodsi.p; goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n); coutpress to run agianendl; coutpress to exitj; 三、 实验总结 本次算法综合实验要求的综合能力较高，需要对所学算法思想知识做到基本的融会贯通。另外，还要具备编程的思想和能力，能灵活运用C+等高级语言来为自己服务。 在两次实验课堂上，我们应努力抓紧时间，当然这时间还是不够，所以正如老师所建议的，需要同学在课下进行思考，提前做好准备，积极的投入到

33、这场综合实验编程中来，而不是光想着在两堂实验课上做出什么一鸣惊人的东西来。 但是，在课程结束后，我似乎忘了这茬，忘了提前做准备，所以只能在实验课上手忙脚乱，对此感到非常后悔。希望自己能充分认识到算法的重要性，不要随着课程的结束就把它抛之脑后，而应该在平时的课下多进行思考，对基本的算法思考进行思考和研究。 另外，不得不提的是对语言掌握的太差，编程基础太差。刚开始上算法课时，老师就强调了C+语言的重要性，要好好掌握这门语言，用处很大。但我当时没有多当回事，并没有像其他同学那样借来C+的相关书籍进行温习和研究。后来到了做实验的时间，才发现书到用时方恨少的遗憾。应该早早听老师的话，及时的捡起已经开始遗

34、忘的C+语言，把它理解透彻，弄熟，能灵活运用。 还有，老师的开明态度也给了我们很大安慰。第二堂实验课时，我们都很着急，既后悔自己没有提前做准备，又为验收担忧。老师让我们根据自己的能力做出亮点的来验收，这一方面给了我们喘息的时间，另一方面又让我们认识到了不足。同样的学习时间，同样的知识来源，最后出现了这样的差距。 最后，感谢老师这一学期的辛苦教导，带我们认识了是程序设计灵魂的算法，并纠正了我们上课玩手机，宅在宿舍不去上课的不良习惯，带动我们积极思考，解决实际问题，带我们感受了算法的神奇之处，看到了一些实用性强并且让人感到不可思议的程序作品。更让我们明白了，作为一名计算机系的学生，我们有强烈的使命，我们要具备基本的编程素质，要有基本的算法思想，要有解决问题的能力，要一点一点培养自己，充实自己，而不是浑浑噩噩的一天天混日子。 专心-专注-专业