《算法设计与分析实验报告.doc》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告.doc（17页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上华北电力大学实 验 报 告| 实验名称 算法设计与分析综合实验 课程名称 算法设计与分析设计实验 | 专业班级： 软件1101 学生姓名： 学 号： 成 绩：指导教师： 胡朝举 实验日期：2013.11专心-专注-专业分治策略归并排序一、 设计要求：归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求：（1）编写一个模板函数：template MergeSort(T *a, int n);以及相应的一系列函数，采用分治策略，对任意具有:bool operator(const T&x,const T&y); 比较运算符的类型进行排序。（2）与STL库
2、中的函数std:sort(.)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的整数序列的排序列问题, 给出所用的时间比较。二、选择的方案：（1）分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。（2）将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决； （3）合并，按原问题的要求，将子
3、问题的解逐层合并构成原问题的解。三、所用仪器、设备：计算机、Visual C+软件。四、实验方法与步骤：合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做排序，引入一个辅助过程merger(A,p,q,r)，其中A是个数组，pqr是下标，满足p= q r。该过程假设Ap.q和Aq+1.r都已排序，并将它们合并成一个已经排好序的子数组代替当前子数组Ap.r。函数模板的声明是在关键字 template 后跟随一个或多个模板在尖括弧内的参数和原型。与普通函数相对，它通常是在一个转换单元里声明，而在另一个单元中定义，你可以在某个头文件中定义模板。template class T T max(
4、T t1, T t2) return (t1 t2) ? t1 : t2;class T 定义 T 作为模板参数，或者是占位符，当实例化 max()时，它将替代具体的数据类型。max 是函数名，t1和t2是其参数，返回值的类型为 T。你可以像使用普通的函数那样使用这个 max()。procedure mergesort(var r,r1:listtype;s,t:integer)r,r1：均为链表，存储排序数据；过程mergesort(r,r1,s,t)完成把链表r中的关键字进行归并排序、并存放到链表r1中，其中s是下界t是上界过程merge(r2,s,m,t,r1)把链表r2中排好序的子链r
5、2s.m和子链r2m+1.t合并到r1中。实现时间计量：#define _CLOCK_T_DEFINEDsrand(unsigned)time(0);/定义一数组an;对每一个赋予一值。ai=rand();得到随即数。 duration =(double)(finish -start)/CLOCKS_PER_SEC;start=clock();将系统时间赋予Start。以便以后进行比较。std:sort(b,b+1000);系统执行1000个数据。Finish-Start为最终结果。五、实验结果：六、实验心得：通过本次实验，我们了解了归并算法的基本思想。并且通过具体的编程实现。在查找资料的情况
6、下，了解了有关时间计算的方法。同时了解了库函数的有关知识，为以后的学习有了一个好开头。算法附件：#include#include#include #ifndef _CLOCK_T_DEFINED#define long clock_t;#define _CLOCK_T_DEFINED#endiftemplate void MSort(T r,T r1,int s,int t) if(s=t) r1s=rs; else int m=(s+t)/2; MSort(r,r1,s,m); MSort(r,r1,m+1,t); Merge(r,r1,s,m,t); for(int i=1;i=t;i+)
7、 r1i=ri; templatevoid Merge_sort(T r,T r1,int n) MSort(r,r1,1,n);templatevoid Merge(T r,T r1,int s,int m,int t) int i=s; int k=s; int j=m+1; while(i=m)&(j=t) if(ri=rj) r1k=rj;j=j+1; if(im)for(int q=j;q=t;q+) rq=r1q; else for(int q=i;q=m;q+) r1q=rq; void main() int *r=new int; int *a=new int; int *r1
8、=new int; for(int i=1;i=;i+) ri=rand(); ai=ri; long start,finish; double duration; Merge_sort(r,r1,); finish=clock(); duration=(double)(finish-start)/CLOCKS_PER_SEC; cout算法时间：durationsendl; start=clock(); std:sort(a,a+); finish=clock(); duration=(double)(finish-start)/CLOCKS_PER_SEC; coutsort函数时间：du
9、rations(Const HTNode &x,const HTNode &y) return x.fy.f;THNode *t=new HTNode2*n-1;for(int i=0;in;i+) ti.c=N; ti.f=N; ti.idx=i;priority-queueHTNode,vector,greater PQ;for(int i=0;in;i+) PQ.push(ti);/以下生成N-1个内节点的标注，即左右父节点标注for（int i=n;i2*n-1;i+） THNode l=PQ.top(); PQ.pop(); THNode r=PQ.top(); PQ.pop();
10、THNode p; p.idx=i; p.l=l.idx; p.r=r.idx; p.f=l.f+r.f; tl,idx.p=i; tr,idx.p=i; ti=p; PQ.push(p);代码：#include#include#include#include#include#includeusingnamespacestd;structTHaffmanNodecharc;intidx;intl,r;intp;intf;THaffmanNode():idx(1),l(NULL),r(NULL),p(NULL),c(0),f(0);classCHuffmanpublic:THaffmanNode
11、nn,nr,nl/*,ntemp,ntemp1*/;intn;char*sFileName;FILE*rf;THaffmanNode*t;intnNext;CHuffman();/读取此格式CHuffman(char*sFileName);CHuffman(intt);voidCreateTree();voidOutputTree();voidOutputCode();friendbooloperator(constTHaffmanNode&x,constTHaffmanNode&y)returnx.fy.f;priority_queueTHaffmanNode,std:vector,std:
12、greaterPQ;CHuffman();CHuffman:CHuffman()this-n=0;CHuffman:CHuffman(char*sFileName1)this-sFileName=sFileName1;ifstreamfin(sFileName);charch4;fin.getline(ch,4);intn1=atoi(ch);coutn1n=n1;this-t=newTHaffmanNode2*n1-1;this-nNext=n1;charch1;for(inti=0;in1;i+)fin.get(ch1);ti.c=ch1;fin.ignore(100,);fin.getl
13、ine(ch,4);ti.f=atoi(ch);for(intk=0;kn;k+)couttk.ctk.fendl;for(ints=0;s=2)THaffmanNodenn,nr,nl/*,ntemp,ntemp1*/;nl=PQ.top();PQ.pop();nr=PQ.top();PQ.pop();nn.f=nl.f+nr.f;nn.l=nl.idx;nn.r=nr.idx;nn.idx=nNext+;tnl.idx.p=nn.idx;tnr.idx.p=nn.idx;tnn.idx=nn;PQ.push(nn);elset2*n-2.p=-1; break;CHuffman:CHuff
14、man(intt1)this-n=t1;this-nNext=t1;this-t=newTHaffmanNode2*t1-1;CHuffman:CHuffman(void)voidCHuffman:CreateTree()for(inti=0;i=2)THaffmanNodenn,nr,nl/*,ntemp,ntemp1*/;nl=PQ.top();PQ.pop();nr=PQ.top();PQ.pop();nn.f=nl.f+nr.f;nn.l=nl.idx;nn.r=nr.idx;nn.idx=nNext+;tnl.idx.p=nn.idx;tnr.idx.p=nn.idx;tnn.idx
15、=nn;PQ.push(nn);elset2*n-2.p=-1; break;voidCHuffman:OutputTree()for(inti=0;i2*n-1;i+)cout权重：ti.f;cout左孩子：ti.l;cout右孩子：ti.r;cout父节点：ti.p;cout在数组的位置：ti.idxendl;/现在数组中存的是哈弗曼数voidCHuffman:OutputCode()/用stack来依次记录各编码的01编码std:stackint,std:listsk;THaffmanNodentemp,ntemp1;for(inti=0;in;i+)ntemp=ti;while(nte
16、mp.p!=-1)ntemp1=tntemp.p;if(tntemp1.l.idx=ntemp.idx) sk.push(0);ntemp=ntemp1;else sk.push(1);ntemp=ntemp1;inti1=sk.size();coutti.f：;for(inti=0;ii1;i+)coutsk.top();sk.pop();coutendl;voidmain() CHuffmanchf(C: UsersqzbDesktop算法实验huffman.txt); chf.OutputTree();chf.OutputCode();system(pause);用回溯方法求解n后问题一
17、、 设计要求：问题：对任意给定的n求解n后问题。具体要求：1封装n后问题为类，编写以下两种算法进行求解：（1）递归回溯方法；（2）迭代回溯方法。(选)2对任意给定的n，要求输出其解向量（所有解），并输出其解数；3构造n后问题的解数表格（由程序自动生成）:n 后数解数第一个解42(2,4,1,3)56二、选择的方案：回溯法：确定了解空间的组织结构后，回溯法就从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处
18、不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。三、所用仪器、设备：计算机、Visual C+软件。四、实验方法与步骤：输入：皇后的个数N；输出：N皇后问题的解的个数以及它的所有可行解。n皇后问题;数组a中，ai表示第i个皇后放在第i行和第ai列,a0存放所有可行解的数目;利用棋盘的对称性，找到一个可行解后，其转置也是一个可行解，所以，只需把第一个皇后从第1列一直扫描到第(n+1)/2列即可，其他解可以根据对称性给出。问题
19、的解可表示为x1:n， 表示皇后i放在棋盘的第i行的第xi列。 a)xixj ,ij ：不允许将任何两个皇后放在同一列上； b)|j-i|xj-xi| :不允许两个皇后位于同一条斜线上。每个解元素生成之后，考察下一个元素能否在本元素的下一列放置，如果place函数的条件均不满足，则放置之，否则则向后放置，如果所有的元素位置都不行，则母元素的列数向后移动一个，再进行循环的考虑，此为回溯思想。五、实验结果与数据处理：六、实验心得： 通过对本次实现了解了回溯算法的基本思想。算法附件：#includeusingnamespacestd;/n皇后类class Queen friend int nQuee
20、n(int);/初始化函数 private: bool Place(int k);/检查第K个皇后的位置是否合适 void Backtrack(void);/扫描 int n,*x; long sum;/可行的方法数量;bool Queen:Place(int k) for(int j=1;j0) xk+=1; while(xk=n)&!(Place(k) xk+=1;/将第K个皇后移到满足要求的列上 if(xk=n)/如果列没超出最后一列，则合要求 if(k=n) sum+; cout第sum个方法endl; for(int a=1;a=k;a+) for(int b=1;b=k;b+) i
21、f(b=xa) coutQ ; else cout- ; coutendl; cout*; coutendlendl; else/如果还有皇后没放置，则继续下一个 k+; xk=0; else/如果第K个皇后没有合适的列，则回到上一个皇后 k-;int nQueen(int n)/初始化Queenqueen;queen.n=n;queen.sum=0;int*p=new intn+1;for(int i=0;i=n;i+) pi=0;queen.x=p;queen.Backtrack();deletep;return queen.sum;void main()int n;int num=0;coutn;num=nQueen(n);coutn皇后问题中可行解的个数有：num个endl;
