算法设计与分析实验报告.doc
精选优质文档-倾情为你奉上华北电力大学实 验 报 告| 实验名称 算法设计与分析综合实验 课程名称 算法设计与分析设计实验 | 专业班级： 软件1101 学生姓名： 学 号： 成 绩：指导教师： 胡朝举 实验日期：2013.11专心-专注-专业分治策略归并排序一、 设计要求：归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求：（1）编写一个模板函数：template <typename T>MergeSort(T *a, int n);以及相应的一系列函数，采用分治策略，对任意具有:bool operator<(const T&x,const T&y); 比较运算符的类型进行排序。（2）与STL库中的函数std:sort(.)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的整数序列的排序列问题, 给出所用的时间比较。二、选择的方案：（1）分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。（2）将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决； （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(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是上界<BR>过程merge(r2,s,m,t,r1)把链表r2中排好序的子链r2s.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为最终结果。五、实验结果：六、实验心得：通过本次实验，我们了解了归并算法的基本思想。并且通过具体的编程实现。在查找资料的情况下，了解了有关时间计算的方法。同时了解了库函数的有关知识，为以后的学习有了一个好开头。算法附件：#include<iostream.h>#include<time.h>#include <algorithm>#ifndef _CLOCK_T_DEFINED#define long clock_t;#define _CLOCK_T_DEFINED#endiftemplate <typename T>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+) r1i=ri; template<typename T>void Merge_sort(T r,T r1,int n) MSort(r,r1,1,n);template<typename T>void 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(i<m)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=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<<"算法时间："<<duration<<"s"<<endl; start=clock(); std:sort(a,a+); finish=clock(); duration=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"sort函数时间："<<duration<<"s"<<endl;动态规划-格路问题一、 设计要求：格路问题有多种方法求解，可采用多种方法求解，如：(1)动态规划方法; (2)备忘录方法；(3) 递归方法。基本要求：(1) 清晰地描述此问题；(2) 采用动态规划方法求解；(3) 给出相应类的封装及数据结构；(4) 输出运算后的二维表格，或输出最短路径(如:写入一个文件)；(5) 格路的数据文件采用以下形式的格式：griddata.txt5,4 /代表m+1,n+11,-1 2,-1 1,-1 4,-1 -1,-1 /最右边点为终点E4,11 3,27 2,9 7,6 -1, 21,15 3,19 2,59 7,16 -1, 187,10 3,20 2,31 7,12 -1, 47 /最左边点为起点O这里：第1行数据为逗号隔开的两个整数值，分别代表m+1,n+1 即格路的列数与行数；每行数据代表格路上的一行数据，每组数据代表相应的点向右，向上的距离(均为整数)。二、选择的方案：动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。格路问题是求一起点到终点的最短路径。采用递归算法可以解决，而且程序的代码教为简单，但是它的时间复杂度是很大的，因为每次求当前的最短路径的时候要不断地利用其子问题的比较来实现。而采用动态规划的基本要素便是最优子结构性质和重叠子问题性质。在算法的具体实现中试递归的定义最优值而且采用自底向上的方式计算最优值。这样的方法在格路问题中的优势是很明显的，因此它的效率要比纯递归算法的高。三、所用仪器、设备：计算机、Visual C+软件。四、实验方法与步骤：用(x,y)来表示坐标,用坐标来指示格路问题的解。五、实验结果：六、实验心得： 虽然最后没能成功输出结果。但是通过对代码的编写基本了解了格路问题的基本思想。以及动态规划这一重要解决问题的方法。同时学习如何引入文件。算法附件：数据结构： struct TPoint int nUp,nRight;int nShortest; int nFrom; TPoint(): nUp(1),nRight(1),nFrom(-1)TPoint(int u,int r): nUp(u), nRight(r), nFrom(-1) ;class CGridRoadprivate:int m, n; TPoint *g; public:CGridRoad();CGridRoad(char *sFileName); CGridRoad(); /void CreateGridFromKeyBoard(); void CreateGridFromFile(char file); void Calculate();void OutputShortest();贪心算法Huffman树及Huffman编码一、 设计要求：一个记录字符及出现频率的文件如下所示：huffman.haf7a,45b,13c,12d,16e,89f,34g,20试编写一个读取此种格式文件类CHuffman, 内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：CHuffman hm("huffman.dat");hm.CreateTree();hm.OutputTree();hm.OutputCode();对于输出树的形式可自行决定(如图形界面或字符界面)。二、选择的方案：贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择。哈夫曼提出了一种构造哈夫曼前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以个叶结点开始，执行次的“合并”运算后产生最终所要求的树T。给定编码字符集C及其频率分布f，即C中任一字符c以频率f（c）在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为。也是字符c的前缀码长。该编码方案的平均码长定义为：B（T）使平均码长达到最小的前缀码编码方案称为C的一个最优前缀码。三、所用仪器、设备：计算机、Visual C+软件。四、实验方法与步骤：哈弗曼算法是自底向上的方式构造表示最优前缀码的二叉树。以每个字符出现的频率作为键值的优先队列用在贪心算法选择中有效地确定当前要合并的两颗具有最小频率的树。一旦两棵具有最小频率的树合并后，产生的一颗新的树，起频率为合并的两棵树的频率之和，并将新树插入优先队列中。五、实验结果：六、实验心得： 通过本次实验了解了贪心算法的基本思想，以及构建哈夫曼树的方法。通过对优先队列的构建方法解决问题。算法附件：基本算法：struct HTNode int l,r,p char c; float f; HTNode():l(-1),p(-1),p(-1),f(0) int idx;bool operator>(Const HTNode &x,const HTNode &y) return x.f>y.f;THNode *t=new HTNode2*n-1;for(int i=0;i<n;i+) ti.c=N; ti.f=N; ti.idx=i;priority-queue<HTNode,vector<HTNode>,greater<THNode> >PQ;for(int i=0;i<n;i+) PQ.push(ti);/以下生成N-1个内节点的标注，即左右父节点标注for（int i=n;i<2*n-1;i+） THNode l=PQ.top(); PQ.pop(); THNode r=PQ.top(); PQ.pop(); 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 <iostream>#include <fstream>#include <queue>#include <stack>#include <stdio.h>#include <list>using namespace std;struct THaffmanNode char c; int idx; int l,r; int p; int f; THaffmanNode():idx(1),l(NULL),r(NULL),p(NULL),c(0),f(0) class CHuffmanpublic: THaffmanNode nn,nr,nl/*,ntemp,ntemp1*/; int n; char *sFileName; FILE *rf; THaffmanNode *t; int nNext; CHuffman();/读取此格式 CHuffman(char *sFileName); CHuffman(int t); void CreateTree(); void OutputTree(); void OutputCode(); friend bool operator >(const THaffmanNode &x,const THaffmanNode &y) return x.f>y.f; priority_queue<THaffmanNode,std:vector<THaffmanNode>,std:greater<THaffmanNode > > PQ; CHuffman();CHuffman:CHuffman() this->n=0;CHuffman:CHuffman(char *sFileName1) this->sFileName=sFileName1; ifstream fin(sFileName); char ch4; fin.getline(ch,4); int n1=atoi(ch); cout<<n1<<endl; this->n=n1; this->t=new THaffmanNode2*n1-1; this->nNext=n1; char ch1; for (int i=0;i<n1;i+) fin.get(ch1); ti.c=ch1; fin.ignore(100,','); fin.getline(ch,4); ti.f=atoi(ch); for (int k=0;k<n;k+) cout<<tk.c<<" "<<tk.f<<endl; for(int s=0;s<n;s+) ts.idx=i; PQ.push(ts); while (!PQ.empty() if (PQ.size()>=2) THaffmanNode nn,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); else t2*n-2.p=-1; break CHuffman:CHuffman(int t1) this->n=t1; this->nNext=t1; this->t=new THaffmanNode2*t1-1;CHuffman:CHuffman(void)void CHuffman:CreateTree() for(int i=0;i<n;i+) PQ.push(ti); /构造HaffmanTree while (!PQ.empty() if (PQ.size()>=2) THaffmanNode nn,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); else t2*n-2.p=-1; break void CHuffman:OutputTree() for(int i=0;i<2*n-1;i+) cout<<"权重："<<ti.f<<" " cout<<"左孩子："<<ti.l<<" " cout<<"右孩子："<<ti.r<<" " cout<<"父节点："<<ti.p<<" " cout<<"在数组的位置："<<ti.idx<<endl; /现在数组中存的是哈弗曼数void CHuffman:OutputCode() /用stack 来依次记录各编码的0 1 编码 std:stack<int, std:list<int> > sk THaffmanNode ntemp,ntemp1; for (int i=0;i<n;i+) ntemp=ti; while(ntemp.p!=-1) ntemp1=tntemp.p; if (tntemp1.l.idx=ntemp.idx) sk.push(0); ntemp=ntemp1; else sk.push(1); ntemp=ntemp1; int i1=sk.size(); cout<<ti.f<<" ： " for(int i=0;i<i1;i+) cout<<sk.top(); sk.pop(); cout<<endl; void main() CHuffman chf("C: UsersqzbDesktop算法实验huffman.txt"); chf.OutputTree(); chf.OutputCode(); system("pause");用回溯方法求解n后问题一、 设计要求：问题：对任意给定的n求解n后问题。具体要求：1封装n后问题为类，编写以下两种算法进行求解：（1）递归回溯方法；（2）迭代回溯方法。(选)2对任意给定的n，要求输出其解向量（所有解），并输出其解数；3构造n后问题的解数表格（由程序自动生成）:n 后数解数第一个解42(2,4,1,3)56二、选择的方案：回溯法：确定了解空间的组织结构后，回溯法就从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。三、所用仪器、设备：计算机、Visual C+软件。四、实验方法与步骤：输入：皇后的个数N；输出：N皇后问题的解的个数以及它的所有可行解。n皇后问题;数组a中，ai表示第i个皇后放在第i行和第ai列,a0存放所有可行解的数目;利用棋盘的对称性，找到一个可行解后，其转置也是一个可行解，所以，只需把第一个皇后从第1列一直扫描到第(n+1)/2列即可，其他解可以根据对称性给出。问题的解可表示为x1:n， 表示皇后i放在棋盘的第i行的第xi列。 a)xixj ,ij ：不允许将任何两个皇后放在同一列上； b)|j-i|xj-xi| :不允许两个皇后位于同一条斜线上。每个解元素生成之后，考察下一个元素能否在本元素的下一列放置，如果place函数的条件均不满足，则放置之，否则则向后放置，如果所有的元素位置都不行，则母元素的列数向后移动一个，再进行循环的考虑，此为回溯思想。五、实验结果与数据处理：六、实验心得： 通过对本次实现了解了回溯算法的基本思想。算法附件：#include<iostream>usingnamespacestd;/n皇后类class Queen friend int nQueen(int);/初始化函数 private: bool Place(int k);/检查第K个皇后的位置是否合适 void Backtrack(void);/扫描 int n,*x; long sum;/可行的方法数量;bool Queen:Place(int k) for(int j=1;j<k;j+)/检查第K个皇后和前k-1个皇后的位置是否冲突 if(abs(k-j)=abs(xj-xk)|(xj=xk) return false; return true;void Queen:Backtrack(void) x1=0; int k=1; while(k>0) 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+) if(b=xa) cout<<"Q"<<" " else cout<<"-"<<" " cout<<endl; cout<<"*" cout<<endl<<endl; 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;cout<<"请输入N皇后问题中的皇后的个数N："cin>>n;num=nQueen(n);cout<<n<<"皇后问题中可行解的个数有："<<num<<"个"<<endl;
