算法试验报告

1、华北电力大学实验报告|实验名称 算法设计与分析综合实验课程名称 算法设计与分析| |专业班级软件12学生姓名：学 号：成 绩：指导教师：胡朝举实验日期:实验一分治策略一归并排序一、实验要求(1)编写一个模板函数：template MergeSort(T *a, int n);以及相应的一系列函数，采用分治策略，对任意具有：bool operator(constT&x,const T&y);比较运算符的类型进行排序。(2)与STL库中的函数std:sort(.)进行运行时间上的比较，给出比较结果， 如：动态生成100万个随机生成的附点数序列的排序列问题，给出所用的时间比 较。二、实验代码#inc

2、lude #include #include #include #define MAX 50typedef struct int arrMAX+1;int length;SortArr;SortArr *CreateSortArr() int i = 0;char buf4*MAX=;char *ptr = NULL;SortArr *sortArr = (SortArr *)malloc(sizeof(SortArr);n input:);memset(sortArr, 0, sizeof(SortArr);printf(请输入待排序数据，以逗号分隔，以分号结束scanf(%s, buf);

3、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 =

4、 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 = right

5、Arrj)(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

6、;IsortArr = 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,内部机制采用优先队

7、列，用于建立 Huffman树及进行Huffman编码输出，其用法可以如下所示：CHuffman hm();();();();eight=weighti;elsehaffTreei.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.wei

8、ght;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;

9、return 0;)实验三用回溯方法求解n后问题、实验要求问题：对任意给定的n求解n后问题。具体要求：1 .封装n后问题为类，编写以下两种算法进行求解：(1)递归回溯方法；(2)迭代回溯方法。(选).对任意给定的n,要求输出其解向量(所有解)，并输出其解数;.构造n后问题的解数表格(由程序自动生成)：n后数解数A个解42(2,4,1,3)56参考类的封装如下：class CQueen(public:CQueen(); xk-1时，判断xk能否放置void BackTrack(int t);nnul);实验四 最大子段和问题的求解一、实验要求问题：对任意动态生成的n个整数(可含负数)，求最大子段

10、及其和。具体要求：.采用至少三种方法进行求解：(1)蛮力方法(枚举方法)；(2)分治策略；(3)动态规划方法。.对算法和数据进行类的封装，编写好构造函数和析构函数；.对任意给定的n个整数，要求对以上的三种算法，都能够输出最大子段及其和。 注：教材中，对于分治策略及动态规划方法，并没有给出最大子段，只是给出了最大 子段和；请注意在编写算法程序时的实现。class CMaxSum(private:int *m_a;wn价值v1v2vn具体要求：.将背包问题进行类的封装；.能对任意给定的n种物品的重量、价值及背包限重，输出以上表格 (或纵向输出);.输出背包问题的解；.本题要求采用STL库中的排序算

11、法数据进行排序。二、实验代码#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;flo

12、at 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+等高级语言来为 自己服务。在两次实验课堂上，我们应努力抓紧时间，当

13、然这时间还是不够，所以正如老 师所建议的，需要同学在课下进行思考，提前做好准备，积极的投入到这场综合 实验编程中来，而不是光想着在两堂实验课上做出什么一鸣惊人的东西来但是，在课程结束后，我似乎忘了这荏，忘了提前做准备，所以只能在实验课 上手忙脚乱，对此感到非常后悔。希望自己能充分认识到算法的重要性， 不要随 着课程的结束就把它抛之脑后，而应该在平时的课下多进行思考， 对基本的算法 思考进行思考和研究。另外，不得不提的是对语言掌握的太差，编程基础太差。刚开始上算法课时， 老师就强调了 C+语言的重要性，要好好掌握这门语言，用处很大。但我当时没 有多当回事，并没有像其他同学那样借来 C+的相关书籍进行温习和研究。后来 到了做实验的时间，才发现书到用时方恨少的遗憾。 应该早早听老师的话，及时 的捡起已经开始遗忘的C+语言，把它理解透彻，弄熟，能灵活运用。还有，老师的开明态度也给了我们很大安慰。 第二堂实验课时，我们都很着急， 既后悔自己没有提前做准备，又为验收担忧。老师让我们根据自己的能力做出亮 点的来验收，这一方面给了我们喘息的时间，另一方面又让我们认识到了不足。 同样的学习时间，同样的知识来源，最后出现了这样