算法设计与分析实验报告

华北电力大学实验报告||实验名称算法设计与分析综合实验课程名称算法设计与分析设计实验||专业班级：软件1101学生姓名：学号：成绩：指导教师：胡朝举实验日期：2013.11华北电力大学实验报告第页共页分治策略—归并排序一、设计要求：归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求：（1）编写一个模板函数：templatetypenameTMergeSort(T*a,intn);以及相应的一系列函数，采用分治策略，对任意具有:booloperator(constT&x,constT&y);比较运算符的类型进行排序。（2）与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的整数序列的排序列问题,给出所用的时间比较。二、选择的方案：（1）分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。（2）将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。三、所用仪器、设备：计算机、VisualC++软件。四、实验方法与步骤：合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做排序，引入一个辅助过程merger(A,p,q,r)，其中A是个数组，pqr是下标，满足p=qr。该过程假设A[p..q]和A[q+1..r]都已排序，并将它们合并成一个已经排好序的子数组代替当前子数组A[p..r]。函数模板的声明是在关键字template后跟随一个或多个模板在尖括弧内的参数和原型。与普通函数相对，它通常是在一个转换单元里声明，而在另一个单元中定义，你可以在某个头文件中定义模板。template＜classT＞Tmax(Tt1,Tt2){return(t1＞t2)?t1:t2;}＜classT＞定义T作为模板参数，或者是占位符，当实例化max()时，它将替代具体的数据类型。max是函数名，t1和t2是其参数，返回值的类型为T。你可以像使用普通的函数那样使用这个max()。proceduremergesort(varr,r1:listtype;s,t:integer){r,r1：均为链表，存储排序数据；过程mergesort(r,r1,s,t)完成把链表r中的关键字进行归并排序、并存放到链表r1中，其中s是下界t是上界}BR{过程merge(r2,s,m,t,r1)把链表r2中排好序的子链r2[s..m]和子链r2[m+1..t]合并到r1中}。实现时间计量：#define_CLOCK_T_DEFINEDsrand((unsigned)time(0));华北电力大学实验报告第页共页//定义一数组a[n];对每一个赋予一值。a[i]=rand();得到随即数。duration=(double)(finish-start)/CLOCKS_PER_SEC;start=clock();将系统时间赋予Start。以便以后进行比较。std::sort(b,b+1000);系统执行1000个数据。Finish-Start为最终结果。五、实验结果：六、实验心得：通过本次实验，我们了解了归并算法的基本思想。并且通过具体的编程实现。在查找资料的情况下，了解了有关时间计算的方法。同时了解了库函数的有关知识，为以后的学习有了一个好开头。算法附件：#includeiostream.h#includetime.h#includealgorithm#ifndef_CLOCK_T_DEFINED#definelongclock_t;#define_CLOCK_T_DEFINED#endiftemplatetypenameTvoidMSort(Tr[],Tr1[],ints,intt){if(s=t)r1[s]=r[s];else{intm=(s+t)/2;MSort(r,r1,s,m);MSort(r,r1,m+1,t);Merge(r,r1,s,m,t);for(inti=1;i=t;i++)华北电力大学实验报告第页共页r1[i]=r[i];}}templatetypenameTvoidMerge_sort(Tr[],Tr1[],intn){MSort(r,r1,1,n);}templatetypenameTvoidMerge(Tr[],Tr1[],ints,intm,intt){inti=s;intk=s;intj=m+1;while((i=m)&&(j=t)){if(r[i]=r[j]){r1[k]=r[j];j=j+1;}if(im)for(intq=j;q=t;q++)r[q]=r1[q];elsefor(intq=i;q=m;q++)r1[q]=r[q];}}voidmain(){int*r=newint[1000000];int*a=newint[1000000];int*r1=newint[1000000];for(inti=1;i=1000000;i++){r[i]=rand();a[i]=r[i];}longstart,finish;doubleduration;Merge_sort(r,r1,1000000);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;华北电力大学实验报告第页共页cout算法时间：durationsendl;start=clock();std::sort(a,a+1000000);finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;coutsort函数时间：durationsendl;}动态规划--格路问题一、设计要求：格路问题有多种方法求解，可采用多种方法求解，如：(1)动态规划方法;(2)备忘录方法；(3)递归方法。基本要求：(1)清晰地描述此问题；(2)采用动态规划方法求解；(3)给出相应类的封装及数据结构；(4)输出运算后的二维表格，或输出最短路径(如:写入一个文件)；(5)格路的数据文件采用以下形式的格式：griddata.txt5,4//代表m+1,n+11,-12,-11,-14,-1-1,-1//最右边点为终点E4,113,272,97,6-1,21,153,192,597,16-1,187,103,202,317,12-1,47//最左边点为起点O这里：第1行数据为逗号隔开的两个整数值，分别代表m+1,n+1即格路的列数与行数；每行数据代表格路上的一行数据，每组数据代表相应的点向右，向上的距离(均为整数)。二、选择的方案：动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。格路问题是求一起点到终点的最短路径。采用递归算法可以解决，而且程序的代码教为简单，但是它的时间复杂度是很大的，因为每次求当前的最短路径的时候要不断地利用其子问题的比较来实现。而采用动态规划的基本要素便是最优子结构性质和重叠子问题性质。在算法的具体实现中试递归的定义最优值而且采用自底向上的方式计算最优值。这样的方法在格路问题中的优势是很明显的，因此它的效率要比纯递归算法的高。华北电力大学实验报告第页共页三、所用仪器、设备：计算机、VisualC++软件。四、实验方法与步骤：用(x,y)来表示坐标,用坐标来指示格路问题的解。五、实验结果：六、实验心得：虽然最后没能成功输出结果。但是通过对代码的编写基本了解了格路问题的基本思想。以及动态规划这一重要解决问题的方法。同时学习如何引入文件。算法附件：数据结构：structTPoint{intnUp,nRight;intnShortest;intnFrom;TPoint():nUp(1),nRight(1),nFrom(-1){}TPoint(intu,intr):nUp(u),nRight(r),nFrom(-1){}};classCGridRoad{private:intm,n;TPoint**g;public:CGridRoad();CGridRoad(char*sFileName);~CGridRoad();//voidCreateGridFromKeyBoard();voidCreateGridFromFile(charfile[]);voidCalculate();voidOutputShortest();};华北电力大学实验报告第页共页贪心算法—Huffman树及Huffman编码一、设计要求：一个记录字符及出现频率的文件如下所示：huffman.haf7a,45b,13c,12d,16e,89f,34g,20试编写一个读取此种格式文件类CHuffman,内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：CHuffmanhm(huffman.dat);hm.CreateTree();hm.OutputTree();hm.OutputCode();对于输出树的形式可自行决定(如图形界面或字符界面)。二、选择的方案：贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择。哈夫曼提出了一种构造哈夫曼前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以个叶结点开始，执行次的“合并”运算后产生最终所要求的树T。给定编码字符集C及其频率分布f，即C中任一字符c以频率f（c）在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为。也是字符c的前缀码长。该编码方案的平均码长定义为：B（T）使平均码长达到最小的前缀码编码方案称为C的一个最优前缀码。三、所用仪器、设备：计算机、VisualC++软件。四、实验方法与步骤：哈弗曼算法是自底向上的方式构造表示最优前缀码的二叉树。以每个字符出现的频率作为键值的优先队列用在贪心算法选择中有效地确定当前要合并的两颗具有最小频率的树。一旦两棵具有最小频率的树合并后，产生的一颗新的树，起频率为合并的两棵树的频率之和，并将新树插入优先队列中。五、实验结果：华北电力大学实验报告第页共页六、实验心得：通过本次实验了解了贪心算法的基本思想，以及构建哈夫曼树的方法。通过对优先队列的构建方法解决问题。算法附件：基本算法：structHTNode{intl,r,pcharc;floatf;HTNode():l(-1),p(-1),p(-1),f(0){}intidx;};booloperator(ConstHTNode&x,constHTNode&y){returnx.fy.f;}THNode*t=newHTNode[2*n-1];for(inti=0;in;i++){t[i].c=N;t[i].f=N;t[i].idx=i;}priority-queueHTNode,vectorHTNode,greaterTHNodePQ;for(inti=0;in;i++)华北电力大学实验报告第页共页PQ.push(t[i]);//以下生成N-1个内节点的标注，即左右父节点标注for（inti=n;i2*n-1;i++）{THNodel=PQ.top();PQ.pop();THNoder=PQ.top();PQ.pop();THNodep;p.idx=i;p.l=l.idx;p.r=r.idx;p.f=l.f+r.f;t[l,idx].p=i;t[r,idx].p=i