算法实验报告14004.pdf
华北电力大学 实 验 报 告|实验名称 算法设计与分析综合实验 课程名称 算法设计与分析|专业班级 软件 12 学生姓名：学 号：成 绩：指导教师：胡朝举 实验日期：实验一 分治策略归并排序 一、实验要求（1）编写一个模板函数：template，MergeSort(T*a,int n);以及相应的一系列函数，采用分治策略，对任意具有:bool operator(const T&x,const T&y);比较运算符的类型进行排序。（2）与 STL库中的函数 std:sort(.)进行运行时间上的比较，给出比较结果,如：动态生成 100万个随机生成的附点数序列的排序列问题,给出所用的时间比较。二、实验代码#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(请输入待排序数据，以逗号分隔，以分号结束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;int 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;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=;i+)printf(%d,i);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，a,45，b,13，c,12，d,16，e,89，f,34，g,20 试编写一个读取此种格式文件类 CHuffman,内部机制采用优先队列，用于建立 Huffman 树及进行 Huffman 编码输出，其用法可以如下所示：CHuffman hm();();();();eight=weighti;else haffTreei.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.weight;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;return 0;实验三 用回溯方法求解 n 后问题 一、实验要求 问题：对任意给定的 n求解 n后问题。具体要求：1封装 n后问题为类，编写以下两种算法进行求解：（1）递归回溯方法；（2）迭代回溯方法。(选)2对任意给定的 n，要求输出其解向量（所有解），并输出其解数；3构造 n 后问题的解数表格（由程序自动生成）:n 后数 解数 第一个解 4 2(2,4,1,3)5 6 参考类的封装如下：class CQueen public:CQueen();xk-1时，判断xk 能否放置 void BackTrack(int t);nnul);实验四 最大子段和问题的求解 一、实验要求 问题：对任意动态生成的 n 个整数（可含负数），求最大子段及其和。具体要求：1采用至少三种方法进行求解：(1)蛮力方法（枚举方法）;(2)分治策略；（3）动态规划方法。2对算法和数据进行类的封装，编写好构造函数和析构函数；3对任意给定的 n 个整数，要求对以上的三种算法，都能够输出最大子段及其和。注：教材中，对于分治策略及动态规划方法，并没有给出最大子段，只是给出了最大子段和；请注意在编写算法程序时的实现。class CMaxSum private:int*m_a;wn 价值 v1 v2 vn 具体要求：1 将背包问题进行类的封装；2 能对任意给定的 n种物品的重量、价值及背包限重，输出以上表格(或纵向输出)；3 输出背包问题的解；4 本题要求采用 STL库中的排序算法数据进行排序。二、实验代码#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最优解为:endl;for(i=1;i=n;i+)cout第i件物品要放:;coutgoodsi.Xendl;void main()cout|-运用贪心法解背包问题-|endl;int j;int n;float 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;三、实验总结 本次算法综合实验要求的综合能力较高，需要对所学算法思想知识做到基本的融会贯通。另外，还要具备编程的思想和能力，能灵活运用 C+等高级语言来为自己服务。在两次实验课堂上，我们应努力抓紧时间，当然这时间还是不够，所以正如老师所建议的，需要同学在课下进行思考，提前做好准备，积极的投入到这场综合实验编程中来，而不是光想着在两堂实验课上做出什么一鸣惊人的东西来。但是，在课程结束后，我似乎忘了这茬，忘了提前做准备，所以只能在实验课上手忙脚乱，对此感到非常后悔。希望自己能充分认识到算法的重要性，不要随着课程的结束就把它抛之脑后，而应该在平时的课下多进行思考，对基本的算法思考进行思考和研究。另外，不得不提的是对语言掌握的太差，编程基础太差。刚开始上算法课时，老师就强调了 C+语言的重要性，要好好掌握这门语言，用处很大。但我当时没有多当回事，并没有像其他同学那样借来 C+的相关书籍进行温习和研究。后来到了做实验的时间，才发现书到用时方恨少的遗憾。应该早早听老师的话，及时的捡起已经开始遗忘的 C+语言，把它理解透彻，弄熟，能灵活运用。还有，老师的开明态度也给了我们很大安慰。第二堂实验课时，我们都很着急，既后悔自己没有提前做准备，又为验收担忧。老师让我们根据自己的能力做出亮点的来验收，这一方面给了我们喘息的时间，另一方面又让我们认识到了不足。同样的学习时间，同样的知识来源，最后出现了这样的差距。最后，感谢老师这一学期的辛苦教导，带我们认识了是程序设计灵魂的算法，并纠正了我们上课玩手机，宅在宿舍不去上课的不良习惯，带动我们积极思考，解决实际问题，带我们感受了算法的神奇之处，看到了一些实用性强并且让人感到不可思议的程序作品。更让我们明白了，作为一名计算机系的学生，我们有强烈的使命，我们要具备基本的编程素质，要有基本的算法思想，要有解决问题的能力，要一点一点培养自己，充实自己，而不是浑浑噩噩的一天天混日子。
