计算机算法设计与分析实验报告大学论文.doc

华北电力大学实 验 报 告| 实验名称 算法设计实验 课程名称 算法设计与分析 | 专业班级：信安1301 学生姓名： 学 号： 成 绩：指导教师：胡朝举 实验日期： 2015年11月 华 北 电 力 大 学 实 验 报 告实验一、归并排序(Merging Sort)分治策略一、 实验内容归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求：（1）编写一个模板函数：template MergeSort(T *a, int n);以及相应的一系列函数，采用分治策略，对任意具有:bool operator(const T&x,const T&y);比较运算符的类型进行排序。（2） 与STL库中的函数std:sort(.)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附点数序列的排序列问题, 给出所用的时间比较。归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并。二、主要思想假设初始序列含有n个记录，则可看成n个有序的子序列，每个字序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，.，如此重复，直到一个长度为n的有序序列为止。例 已知待排序记录的关键字序列为49,38,65,97,76,13,27，给出2-路归并排序法进行排序的过程2-路归并排序中的核心操作是，将待排序序列中前后相邻的两个有序序列归并为一个有序序列。相邻两个有序子序列的归并设两个有序表存放在同一数组中相邻的位置上：Rlow.mid和Rmid+1.high，每次分被从两个表中取出一个记录进行关键字的比较，将较小者放入Tlow.high中，重复此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到T中。三、 实验结果四、 算法分析1)时间复杂度当有n个记录时，需进行log2n趟归并排序,每一趟归并,其关键字比较次数不超过n,元素移动次数都是n,因此,归并排序的时间复杂度为O(nlog2n)。2)空间复杂度用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复杂度为O(n);五、 实验代码#include#include#include#include#includeusing namespace std;templatevoid MergSort(Type a, int n)Type *b = new Typen;int s = 1;while (s n)MergPass(a, b, s, n);s += s;MergPass(b, a, s, n);s += s;templatevoid MergPass(Type x, Type y, int s, int n)int i = 0;while (i = n - 2 * s)Merg(x, y, i, i + s - 1, i + 2 * s - 1);i = i + 2 * s;if (i + s n)Merg(x, y, i, i + s - 1, n - 1);else /如果剩下的不够i+s，则把剩下的放入y中for (int j = i; j = n - 1; j+)yj = xj;templatevoid Merg(Type c, Type d, int l, int m, int r)int i = l, j = m + 1, k = l;while (i = m) & (j = r)if (ci m)for (int q = j; q = r; q+)dk+ = cq;elsefor (int q = i; q = m; q+)dk+ = cq;float randf(float base, float up)return (rand() % (int)(up - base) * RAND_MAX) / (float)RAND_MAX ; /产生随机数void printArray(float *a,int N)for(int i=0;i=N;i+)coutaiendl;void main()int ArrayLen = 5;float *array = new floatArrayLen;float *arrays = new floatArrayLen;float mn, ene;printf(数组已建立： n);srand(unsigned)time(NULL); /设置随机数的seedfor (int i = 0; i ArrayLen; i+)mn = (float)rand(); /产生小数ene = randf(1,10000)+mn;arraysi =ene;arrayi = ene;int fflag = 2;while (fflag != 0)printf(输入需要显示的归并数组：n 1.归并排序 0.exitn);coutfflag;switch (fflag)case 0:break;case 1:MergSort(array, ArrayLen);printArray(array, ArrayLen);break;printf(=n);printf(n);clock_t s = 0, e = 0;s = clock();MergSort(array, ArrayLen);e = clock();cout MergSort运行了： (e - s) ms endl;clock_t start1 = 0, end1 = 0;start1 = clock();std:sort(&arrays0, &arraysArrayLen);end1 = clock();cout std:sort运行了： (end1 - start1) ms endl; int flag = 1;while (flag != 0)cout输入需要显示的排序方法：endl;cout 1.归并排序 0.exit flag;switch (flag)case 1:printf(归并排序序列:n);MergSort(array, ArrayLen);printArray(array, 5);break;case 0:break;综合实验 二贪心算法Huffman树及Huffman编码一 实验内容一个记录字符及出现频率的文件如下所示：huffman.haf7a,45b,13c,12d,16e,9f,5试编写一个读取此种格式文件类CHuffman, 内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：CHuffman hm(huffman.dat);hm.CreateTree();hm.OutputTree();hm.OutputCode(); /二进制形式的字符串对于输出树的形式可自行决定(如图形界面或字符界面)。二、主要思想该程序已封装为类在HuffmanCode.cpp中，该代码读取E:h.dat路径下的数据文件，可以更改为用户输入的指定路径，但鉴于算法核心功能已经实现，不再加强此功能。另一点，此程序在建立完哈夫曼树后，不是使用遍历二叉树求解的方法而是使用直接从叶子节点出发，直接沿路径返回至根节点进行哈夫曼编码确定，不足之处是，结构体中多加了存储字段，消耗了更多内存。此外，向量已经给出了类似栈的操作，直接利用这一点，模仿优先队列进行操作，具体说明及实现在注释中已给出。这个霍夫曼编码本身用到了贪心的思想，所以也在这里列举了出来。这个问题本身在计算机系的很多教材上都出现过。这里权且记录下来。霍夫曼的编码是这样的。假设我有一组带压缩的文本，里面各个字符出现的频率不同，现在需要对他们进行压缩。比如假设我们有100,000个字符的文本.最直观的压缩办法就是原来每个字符要8个bits。现在我一共只有6个字符，那我就把每个字符用3个二进制 位来表示，这样所有100,000个字符用300,000个bit就可以表示了。这种是最直观的方案。但是霍夫曼提出的方案更精妙一些。他提出，基于每个 字符出现的频率不同，可以让出现次数多的字符用更少的二进制位来描述，出现次数少的字符用多一些二进制来描述。比如上图显示的这个Variable-length codeword里面。a出现的频率最高，所以用一个二进制位0来表示。而f出现的频率很小，所以用4个二进制位来表示。这样总共(45 1 + 13 3 + 12 3 + 16 3 + 9 4 + 5 4) 1,000 = 224,000 bits。可以看到这个是比原来的方案更优化的解法。我们一样的还是用一张图来描述霍夫曼编码的流程：这个过程概括的说就是一个根据频率建立二叉树的过程。建完之后对应的编码也就完成了。第一步a. 这个a就和之前的活动选择问题一样，把需要的所以字符按照频率排序。第二部b. 选取出现频率最小的两个节点 f 和e。组成一个新的节点，新的节点的频率就是e和f的和。原来的e和f分别成了新节点的左子节点和右子节点。(注意这里一个默认的规则就是频率小的是左子节 点，大的是右子节点。)然后把之前的两个节点从原来的组中删除，加新的节点加入排序。第三部c. 其实和第二部雷同，就是一个循环的过程。这里再次去除队列中的最小频率的两项（这时是c和b）。组成新的节点加入队列排序。如此循环往复，最后就形成了(f)这个二叉树。现在有了二叉树只有，我们把左子树这条边标记为0，右子树标记为1。这样就差生了对应的编码方式 a=0; b=101;.三、实验结果四、算法分析五、实验代码#include#include#include#include#includeusing namespace std;struct Nodechar Content;float Frequency;Node*Left;Node*Right;Node*Parent;string Code;/编码串char LOR;/该节点作为左孩子（0）还是右孩子（1）;bool Compare(Node*a,Node*b)return a-Frequencyb-Frequency;class HuffmanCodepublic:vectorShow;/显示结果的向量/输入文件绝对路径HuffmanCode(char*file);HuffmanCode();void Executing();private:char*FilePath;Node*Root;/哈夫曼树根节点vectorAsQueue;/作为队列的向量/读取文件内容,扫描字符出现频率，形成初始队列void ReadAndScan();/生成哈夫曼树void CreateHuffmanTree();/设置编码void ErgodicTree();/释放节点void Delete(Node*n);HuffmanCode:HuffmanCode(char*file)FilePath=file;HuffmanCode:HuffmanCode()/释放节点Delete(Root);void HuffmanCode:Executing()/读取文件内容,扫描字符出现频率，形成初始队列ReadAndScan();/生成哈夫曼树CreateHuffmanTree();/遍历整棵树并设置编码ErgodicTree();/读取文件内容,扫描字符出现频率，形成初始队列void HuffmanCode:ReadAndScan()ifstream fin;fin.open(E:h.dat,ios:binary);string str;finstr;fin.close();bool used;int temp1,temp2;temp1=str.length();for(int i=0;itemp1;i+)used=false;temp2=AsQueue.size();for(int j=0;jContent=stri)AsQueuej-Frequency+;used=true;break;if(!used)Node*n=new Node();n-Content=stri;n-Frequency=1;n-Left=NULL;n-Right=NULL;AsQueue.push_back(n);sort(AsQueue.begin(),AsQueue.end(),Compare);temp2=AsQueue.size();for(int i=0;iFrequency=AsQueues-Frequency+AsQueues-1-Frequency;n-Left=AsQueues;AsQueues-LOR=0;n-Right=AsQueues-1;AsQueues-1-LOR=1;AsQueues-Parent=n;AsQueues-1-Parent=n;AsQueue._Pop_back_n(2);AsQueue.push_back(n);sort(AsQueue.begin(),AsQueue.end(),Compare);Root=AsQueue0;Root-LOR=-1;/设置编码void HuffmanCode:ErgodicTree()/从叶子节点向树顶端搜索直至根节点获取编码int temp=Show.size();for(int i=0;iLOR)c.push_back(n-LOR);n=n-Parent;int temp2=c.size();for(int j=temp2-1;j-1;j-)Showi-Code.push_back(cj);/释放节点void HuffmanCode:Delete(Node*n)if(n-Left)Delete(n-Left);if(n-Left)Delete(n-Right);delete n;测试代码段void main()HuffmanCode h(E:h.dat);h.Executing();vectorn=h.Show;int k=n.size();string b;for(int i=0;ik;i+)coutContentFrequencyCodeendl;综合实验三用回溯方法求解n后问题一、实验内容问题：对任意给定的n求解n后问题。具体要求：1封装n后问题为类，编写以下两种算法进行求解：（1）递归回溯方法；（2）迭代回溯方法。(选)2对任意给定的n，要求输出其解向量（所有解），并输出其解数；3构造n后问题的解数表格（由程序自动生成）:n 后数解数第一个解42(2,4,1,3)56参考类的封装如下：二、 主要思想（1）问题描述 在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再nn的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。（2）算法设计思想1.要解决n皇后问题，其实就是要解决好怎么放置这n个皇后，每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线，在这里我们可以以行优先，就是说皇后的行号按顺序递增，只考虑第i个皇后放置在第i行的哪一列，所以在放置第i个皇后的时候，可以从第1列判断起，如果可以放置在第1个位置，则跳到下一行放置下一个皇后。如果不能，则跳到下一列.直到最后一列，如果最后一列也不能放置，则说明此时放置方法出错，则回到上一个皇后向之前放置的下一列重新放置。这也就是回溯法遍历所有可行解的一个搜索方式。当第n个皇后放置成功后，即得到一个可行解，此时再回到上一个皇后重新放置寻找下一个可行解.如此后，即可找出一个n皇后问题的所有可行解。2.设计剪枝函数：可以用n元组x1:n来表示n后问题的解，其中xi表示皇后i放在棋盘的第i行的第xi列。由于不允许两个皇后在同一列上，所以解向量中的xi互不相同。对于任意两个皇后不能在同一对角线上这个条件，可以这样来表示：对n*n的方阵，两个皇后的位置分别是（i,j）和（k,l），则若有i-k=k-l或i+j=k+l,则说明这两皇后处于同一条对角线上。以上两个方程可以一起表示为|i-k|=|j-l|,若此式成立，则说明两个皇后位于同一条对角线上。可以利用这一个条件来设计相应的剪枝函数。3用回溯法解决n后问题时，使用完全n叉数来表示解空间，利用剪枝函数Place（）来剪去不满足条件的子树。利用一个Backtrack（）函数实现对整个解空间的回溯搜索，使用sum记录当前已经找到的可行方案数。三、实验结果四、实验代码动态规划算法解决矩阵连乘问题源程序代码#include using namespace std;int MatrixChain(int n, int *m, int *s, int *p);void Traceback(int i, int j, int *s);int main()int n;cout n;int *p = new intn + 1;int *s = new int *n + 1;int *m = new int *n + 1;for (int i = 0; in + 1; i+)si = new intn + 1;mi = new intn + 1;cout endl;cout 输入 n + 1 个数据：n;for (int i = 0; i = n; i+)cout 第 i + 1 个数据 pi;cout 矩阵的最少计算次数为： MatrixChain(n, m, s, p) endl;cout 矩阵最优计算次序为： endl;Traceback(1, n, s);system(pause);return 0;int MatrixChain(int n, int *m, int *s, int *p)for (int i = 1; i = n; i+)mii = 0;for (int r = 2; r = n; r+)for (int i = 1; i = n - r + 1; i+)int j = i + r - 1;mij = mi + 1j + pi - 1 * pi * pj;sij = i;for (int k = i + 1; kj; k+)int t = mik + mk + 1j + pi - 1 * pk * pj;if (tmij)mij = t;sij = k;return m1n;void Traceback(int i, int j, int *s)if (i = j) return;Traceback(i, sij, s);Traceback(sij + 1, j, s);cout Multiply A i , sij;cout and A (sij + 1) , j endl;回溯法解决n后问题源程序代码#include #includeusing namespace std;class Queenfriend int nQueen(int);private:bool Place(int k);void Backtrack(int t);int n, /皇后个数*x; /当前解long sum; /当前已找到的可行方案数;bool Queen:Place(int k)for (int j = 1; jn)sum+;for (int i = 1; i = n; i+)cout x i = xi ;cout endl;elsefor (int i = 1; i = n; i+)xt = i;if (Place(t)Backtrack(t + 1);int nQueen(int n)Queen X;/初始化XX.n = n;X.sum = 0;int *p = new intn + 1;for (int i = 0; i = n; i+)pi = 0;X.x = p;X.Backtrack(1);deletep;return X.sum;void main()cout p;q = nQueen(p);cout The number of the solution is: q endl;system(pause); 综合实验四 背包问题的贪心算法一、实验内容问题: 给定如下n种物品的编号，及其价值；背包重量为c, 求最佳装包方案，才能使其装入背包的价值最大。物品编号12n重量w1w2.wn价值v1v2vn具体要求：1 将背包问题进行类的封装；2 能对任意给定的n种物品的重量、价值及背包限重，输出以上表格( 或纵向输出)；3 输出背包问题的解；4 本题要求采用STL库中的排序算法数据进行排序。二、 主要思想三、实验结果四实验代码#include stdafx.h#includeusing namespace std;class beibaopublic:void chushishuzu();void jiazhipaixu();void shuchuxulie();private: int n;/物件个数 double v20;/价值数组 double w20;/质量数组 double c20;/单位价值数组 double m;/背包质量 int y20;/排序数组 double x20;/物件分量;void beibao:chushishuzu()/初始化背包 cout 请输入物件个数： this-n;cout 请依次输入价值： endl;for (int i = 1; i n + 1; i+)cin this- vi; cout 请依次输入质量： endl;for (int i = 1; i n + 1; i+)cin this- wi;cout 请输入背包质量 this- m; void beibao:jiazhipaixu()/背包排序 for (int i = 1; i n + 1; i+) this-ci = this-vi / this-wi; int max = 0; for (int i = 1; i n + 1; i+) max = 1; for (int j = 1; j n + 1; j+) if (this-cmax cj) max = j; this-cmax = 0; this-yi = max; cout 按单位价值排序为： endl; for (int i = 1; i n + 1; i+) cout wyi ; coutendl; void beibao:shuchuxulie()/输出背包序列 for (int i = 1; i n + 1; i+)this-xi = 0;int i = 0;for (i = 1; in + 1; i+)if (this-wyithis-m)break;this-xi = 1;this-m = this-m - this-wyi;if (i xi = this-m / this-wyi;cout 输出分量为： endl;for (i = 1; i n + 1; i+)cout xi nul); 五、实验心得通过本次实验，我较为透彻的理解了动态规划算法的几个基本步骤。完成实验后，我认为建立递归关系是很关键的一步，同时也是整个动态规划算法的精髓。掌握了递归的思想，就可以完成很多不必要的重复计算。虽然已经了解了动态规划算法的基本思想，而且也参考了书上的算法，但是实际的情况却并不是那么顺利，我按照书上编写程序之后，发生了很多错误，所以出现了一系列的问题。我也体会到，想要理解一个新的算法，必须要通过自己不断的编写程序，不断的思考才能真正的领悟，因此我会不断朝着这个方向努力。实验五(选做)矩阵连乘问题一、实验内容矩阵连乘问题，给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,3,n-1。考察这n个矩阵的连乘A1,A2,An。二、主要思想由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为：(1)单个矩阵是完全加括号的；(2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行：1、分析最优解的结构设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为Ai:j。考察计算A1:n的最优计算次序。设这个计算次序矩阵在Ak和Ak+1之间将矩阵链断开，1kn,则其相应的完全加括号方式为(A1Ak)(Ak+1An)。依此次序，先计算A1:k和Ak+1:n,然后将计算结果相乘得到A1:n。2、建立递归关系设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算Ai:j，1ijn，所需的最少数乘次数为mij，原问题的最优值为m1n。当i=j时，Ai:j=Ai为单一矩阵，无需计算，因此mii=0，i=1,2,n。当ij时，可利用最优子结构性质来计算mij。mij=mik+mk+1j+pi-1pkpj。由于在计算时并不知道断开点k的位置，所以k还未定。3、计算最优值根据计算mij的递归式，容易写一个递归算法计算m1n。动态规划法解决此问题，可依据递归式以自底向上的方式进行计算，在计算过程中保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法matrixChain。(见实验代码部分)。4、构造最优解算法matrixChain只计算出最优值，并没有给出最优解。但是matrixChain已经记录了构造最优解所需的全部信息。Sij中的数表明