2016春《计算机算法设计与分析》实验作业.doc

实验报告 学院 计算机科学与技术学院 专业 计算机科学与技术 班级 课程 算法分析与设计 教师 学号 姓名 学期 2016 年 春 季实验1 算法设计与分析基础一、实验环境操作系统：Windows XP或Windows7及以上 编程语言： Visual C+6.0或VS2012二、实验目的 了解算法描述的各种方法，重点学会使用自然语言与伪代码描述算法的方法。养成先用自然语言或伪代码描述算法，然后再进行程序设计的习惯。掌握进行算法复杂度分析的方法。三、实验内容 1.1求两个整数的最大公约数。1.2 输出杨辉三角形前n行。例如，杨辉三角形前5行如下:11 11 2 11 3 3 11 4 6 4 11.3统计数字问题1.4最多约数问题四、实验开始1.1 求两个整数的最大公约数1.1.1 问题描述：给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大整数。1.1.2 算法描述方法1：自然语言欧几里德算法辗转相除法： 输入m 和n； 求m除以n的余数r； 若r等于0，则n为最大公约数，输出结果n，算法结束； 否则执行第步； 将n的值放在m中，将r的值放在n中； 返回第步继续执行。方法2：伪代码表示Begin(算法开始) Read(m,n) m mod nr while r0 do nm rn m mod nr write(n) End(算法结束)1.1.3 程序设计与实现方法1：欧几里德算法的C语言描述如下： #include main() int m,n,r; printf(“请输入两个正整数：”)； scanf(“%d%d”,&m,&n); printf(“n%d和%d的最大公约数是：”，m,n); r=m%n; while (r!=0) m=n; n=r; r=m%n; printf(“%dn”,n); 方法2：欧几里德算法的C+语言描述如下：#include int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n;void main( )int m, n; coutmn; coutm与n的最大公约数是：; coutCommonFactor(m,n)endl;1.1.4 测试数据及测试结果运行程序：请输入两个正整数：18 1218与12的最大公约数是：61.1.5 算法复杂度分析时间复杂度分析：辗转相除法的循环次数与m、n的大小不成正比，时间复杂度为O(1)空间复杂度分析：算法在执行过程中临时存储单元为1个(变量r)，空间复杂度为O(1)1.2 输出杨辉三角形前n行1.2.1 问题描述1.2.2 算法描述1.2.3程序设计与实现1.2.4 测试数据及测试结果1.2.5 算法复杂度分析1.3 统计数字问题1.3.1 问题描述一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06 或006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，9。1.3.2算法分析与设计：给定表示书的总页码的10进制整数n(1n109)，计算书的全部页码中分别用到多少次数字0，1，2，9。输入数据、输出结果示例输入数据：11 输出结果：数 字: 0 1 2 3 4 5 6 7 8 9用到次数: 1 4 1 1 1 1 1 1 1 11.3.3算法描述1.3.4程序设计与实现1.3.5测试数据及测试结果1.3.6算法复杂度分析1.4 最多约数问题1.4.1 问题描述1.4.2 算法分析与设计1.4.3 算法描述1.4.4程序设计与实现1.4.5 测试数据及测试结果1.4.6 算法复杂度分析实验2 递归与分治一、实验环境操作系统：Windows XP 编程语言：Visual C+6.0或VS2012二、实验目的 学习和了解递归与分治算法的概念和基本思想，熟悉对递归与分治问题的分析方法及其适用范围；掌握递归与分治算法的设计思路和基本步骤，学会使用递归与分治算法解决实际问题。三、实验内容 2.1求最大最小元问题2.2归并排序2.3快速排序2.4众数问题2.5* 马的Hamilton周游路线问题四、实验开始2.1 求最大最小元问题2.1.1 问题描述2.1.2 算法分析与设计2.1.3 算法描述2.1.4程序设计与实现2.1.5 测试数据及测试结果2.1.6 算法复杂度分析2.2 归并排序(Merging Sort)2.2.1 问题描述“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。利用归并的思想实现排序。2-路归并排序：设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。2.2.2 算法分析与设计例如图10.13为2-路归并排序的一个例子。初始关键字 49 38 65 97 76 13 27 一趟归并之后 38 49 65 97 13 76 27 二趟归并之后 38 49 65 97 13 27 76三趟归并之后 13 27 38 49 65 76 97 图10.13 2-路归并排序示例2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。2.2.3 算法描述2.2.4程序设计与实现2.2.5 测试数据及测试结果2.2.6 算法复杂度分析2.3 快速排序(Quick Sort)2.2.1 问题描述快速排序(Quick Sort)是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。2.2.2 算法分析与设计假设待排序的序列为L.rs，L.rs+1，L.rt，首先任意选取一个记录(通常可选第一个记录L.rs作为枢轴(或支点)(pivot)，然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。这个过程称作一趟快速排序(或一次划分)。一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。2.2.3 算法描述2.2.4程序设计与实现2.2.5 测试数据及测试结果2.2.6 算法复杂度分析2.4 众数问题2.4.1 问题描述2.4.2 算法分析与设计2.4.3 算法描述2.4.4程序设计与实现2.4.5 测试数据及测试结果2.4.6 算法复杂度分析2.5* 马的Hamilton周游路线问题2.5.1 问题描述2.5.2 算法分析与设计2.5.3 算法描述2.5.4程序设计与实现2.5.5 测试数据及测试结果2.5.6 算法复杂度分析实验3 动态规划一、实验环境操作系统：Windows XP 编程语言：Visual C+6.0或VS2012二、实验目的 1、学习和了解动态规划算法的概念和基本思想； 2、熟悉对动态规划问题的分析方法及其适用范围；3、掌握动态规划算法的设计思路和基本步骤；4、学会使用动态规划法解决实际问题。三、实验内容 1旅行家问题(TSP)2多段图的最短路径问题30-1背包问题(knapsack problem)。4最长公共子序列(LCS) 问题5数塔问题四、实验开始3.1 旅行家问题(TSP)3.1.1 问题描述旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。3.1.2 算法分析与设计各个城市间的距离可以用代价矩阵来表示。C= 3 6 7 5 2 3 6 4 2 3 7 5 带权图的代价矩阵证明TSP问题满足最优性原理设s, s1, s2, , sp, s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1, s2, , sp, s一定构成一条从s1到s的最短路径。 如若不然，设s1, r1, r2, , rq, s是一条从s1到s的最短路径且经过n-1个不同城市，则s, s1, r1, r2, , rq, s将是一条从s出发的路径长度最短的简单回路且比s, s1, s2, , sp, s要短，从而导致矛盾。所以，TSP问题满足最优性原理。假设从顶点i出发，令d(i, V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，VVi，于是，TSP问题的动态规划函数为：d(i,V)=mincik+d(k,Vk) (kV) （1）d(k,)=cki(ki) （2）从城市0出发经城市1、2、3然后回到城市0的最短路径长度是：d(0,1, 2, 3)=minc01+d(1, 2, 3), c02+d(2, 1, 3), c03+d(3, 1, 2)这是最后一个阶段的决策，而： d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)这一阶段的决策又依赖于下面的计算结果：d(1, 2)= c12+d(2, ) d(2, 3)=c23+d(3, ) d(3, 2)= c32+d(2, ) d(1, 3)= c13+d(3, ) d(2, 1)=c21+d(1, ) d(3, 1)=c31+d(1, ) 而下式可以直接获得（括号中是该决策引起的状态转移）：d(1, )=c10=5(10) d(2, )=c20=6(20) d(3, )=c30=3(30)再向前倒推，有：d(1, 2)= c12+d(2, )=2+6=8(12) d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 3)= c23+d(3, )=2+3=5(23) d(2, 1)= c21+d(1, )=4+5=9(21)(3, 1)= c31+d(1, )=7+5=12(31) d(3, 2)= c32+d(2, )=5+6=11(32)再向前倒退，有：d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)=min2+5, 3+11=7(12)d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)=min4+6, 2+12=10(21)d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32)最后有：d(0, 1, 2, 3)=minc01+ d(1, 2, 3), c02+ d(2, 1, 3), c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(01) 所以，从顶点0出发的TSP问题的最短路径长度为10，最短路径是01230。 动态规划法求解TSP问题的填表过程假设n个顶点用0n-1的数字编号，首先生成1n-1个元素的子集存放在数组V2n-1中，设数组dn2n-1存放迭代结果，其中dij表示从顶点i经过子集Vj中的顶点一次且仅一次，最后回到出发点0的最短路径长度。填表方法：自底向上，逐步求值。利用前一步求出的值计算出后一步的值填入表中，每一步结束后选择最小值作为子问题的最优值，最后一步为原问题的最优解。ji 1231,21,32,31,2,30101586726951033121114第1步第2步第3步第4步第1步：填写第1列，d(1, )=c10=5 (10)； d(2, )=c20=6 (20)； d(3, )=c30=3 (30)第2步：d(1, 2)= c12+d(2, )=2+6=8(12) d(1, 3)= c13+d(3, )=3+3=6(13)d(2, 1)= c21+d(1, )=4+5=9(21) d(2, 3)= c23+d(3, )=2+3=5(23)d(3, 1)= c31+d(1, )=7+5=12(31) d(3, 2)= c32+d(2, )=5+6=11(32)第3步：d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)=min2+5, 3+11=7(12)d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)=min4+6, 2+12=10(21)d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32)第4步：d(0, 1, 2, 3)=minc01+ d(1, 2, 3), c02+ d(2, 1, 3), c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(01)最优解为：01、12、23、30，即，最短路径为：01230，最短路径长度为：10设顶点之间的代价存放在数组cnn中，动态规划法求解TSP问题的算法如下： 3.3.3 算法描述算法3.1TSP问题 1for (i=1; in; i+) /初始化第0列 di0=ci0; 2for (j=1; j2n-1-1; j+) for (i=1; in; i+) /依次进行第i次迭代 if (子集Vj中不包含i) 对Vj中的每个元素k，计算dij=min(cik+dkj-1); 3对V2n-1-1中的每一个元素k，计算d02n-1-1=min(c0k+dk2n-1-2); 4输出最短路径长度d02n-1-1;3.1.4 程序实现3.1.5 测试数据及测试结果3.1.6 算法复杂度分析显然，算法3.1的时间复杂性为O(2n)。和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。3.2 多段图的最短路径问题3.2.1 问题描述设图G=(V, E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2kn, 1ik），使得E中的任何一条边(u, v)，必有uVi，vVi+m（1ik, 1i+mk），则称图G为多段图，称sV1为源点，tVk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。举例：3.2.2算法分析与设计3.2.3 算法描述3.2.4 程序实现3.2.5 测试数据及测试结果3.2.6 算法复杂度分析3.3 0-1背包问题(knapsack problem)3.3.1 问题描述0-1背包问题(knapsack problem)，某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数, 背包的容量为W，W为一非负数。目标是如何选择装入背包的物品，使装入背包的物品总价值最大，所选商品的一个可行解即所选商品的序列如何？3.3.2 算法分析与设计可将这个问题形式描述如下：约束条件为： 举例:若商店一共有5类商品，重量分别为：3 4 7 8 9价值分别为：4 5 10 11 13背包容量为：17则：所选商品的一个序列为：0 0 0 1 1 所选商品的最大价值为243.3.3 算法描述3.3.4程序设计与实现#include #include #include int min(int w,int c) /求2个数中的最小值return(wc?w:c); void knapsack(int v,int w,int c,int n,int*m) /求最优值 / int jmax=min(wn-1,c); for (int j=0; j=jmax; j+) mnj=0; for(int jj=wn;jj1; i-) /递归部分 jmax=min(wi-1,c); for(int j=0; j=jmax; j+) mij=mi+1j; for (int jj=wi;jj=w1) m1c=max(m1c,m2c-w1+v1); cout最优值：m1cendl; cout*endl; int traceback(int *m,int w,int c,int n,int x) /回代，求最优解 / cout得到的一组最优解如下:endl; for (int i=1;in;i+) if (mic=mi+1c) xi=0; else xi=1; c-=wi; xn=(mnc)?1:0; for (int y=1;y=n;y+) coutsetw(5)xy; coutendl; return xn; void main() int n,c; int *m; coutnc; int *v=new intn+1; cout请输入价值 (vi):endl; for (int i=1;ivi; int *w=new intn+1; cout请输入重量 (wi):endl; for (int j=1;jwj; int *x=new intn+1; m=new int*n+1; /动态分配二维数组 for(int p=0;pC) 4.1 xi=1; /将第i个物品放入背包 4.2 C=C-wi; /背包容量减去放入背包中物品的重量 4.3 i+; /去掉放入背包中的物品5. xi=C/wi; /分割需放入背包中的最后一个物品，让背包装满容量C4.1.4 程序实现/背包问题(贪心算法).cpp#include #define LEN 10 /物品最多个数struct Element /物品结构体类型float w; /重量float v; /价值float per; /单位重量价值v/wint i; /物品序号;void mergeSort(Element *d)/冒泡排序：对一维结构体数组d按“单位重量价值”降序排列Element temp;for (int i=0;iLEN-1;+i)for(int j=0;jLEN-1-i;+j) if (dj.perdj+1.per)temp=dj;dj=dj+1;dj+1=temp;float knapsack(float c,float *w,float *v,float *x)/求容量为C、物品重量为w、价值为v的背包问题的解xint n=LEN;Element dLEN=0;for (int i=0;in;+i)di.w=wi;di.v=vi;di.per=vi/wi;di.i=i;mergeSort(d);float opt=0; /opt存放背包中物品的价值总和for (i=0;in;+i) xi=0; for(i=0;ic) break;xdi.i=1;opt+=di.v;c-=di.w;if (in) xdi.i=c/di.w;opt+=xdi.i*di.v; return opt;void main()float wLEN=12.5,10,9,8,6,7,5,3,2.5,4.6;float vLEN=10,9,8,6,3,4,5,3,1.2,2.2;float xLEN=0; float opt=knapsack(35,w,v,x);printf(背包中物品的总价值为：%gn,opt);printf(最优解x数组为：);for (int i=0;iLEN;+i) printf(%g ,xi);putchar(n);4.1.5 测试数据及测试结果背包中物品的总价值为：31.4最优解x数组为：0.64 1 1 0 0 0 1 1 0 04.1.6 算法复杂度分析算法的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此，其时间复杂性为O(nlog2n)。4.2 最小生成树问题4.2.1 问题描述一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的(n-1)条边。 对于一个带权(假定每条边上的权均为大于零的实数)连通无向图G中的不同生成树，其每棵树的所有边上的权值之和也可能不同，图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。 4.2.2 算法分析与设计按照生成树的定义，n个顶点的连通图的生成树有n个顶点、n-1条边。因此，构造最小生成树的准则有三条： (1)必须只使用该图中的边来构造最小生成树； (2)必须使用且仅使用n-1条边来连接图中的n个顶点；(3)不能使用产生回路的边。4.2.3 算法描述方法1. 普里姆算法 普里姆(Prim)算法是一种构造性算法： 假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造最小生成树T的步骤如下： (1)初始化U=v0。v0到其他顶点的所有边为候选边； (2)重复以下步骤n-1次，使得其他n-1个顶点被加入到U中： 从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是v,将v加入U中，删除和v关联的边； 考察当前V-U中的所有顶点vi,修改候选边：若(v,vi)的权值小于原来和vi关联的候选边,则用(v,vi)取代后者作为候选边。普里姆算法求解最小生成树的过程方法2. 克鲁斯卡尔算法 克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，则构造最小生成树的步骤如下： (1)置U的初值等于V(即包含有G中的全部顶点)，TE的初值为空集(即图T中每一个顶点都构成一个分量)。 (2)将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE；否则舍弃，直到TE中包含(n-1)条边为止。克鲁斯卡尔算法求解最小生成树的过程4.2.4 程序实现/ywmp174e7_3.cpp 最小生成树.Prim(普里姆)算法#include #define N 20 /网络中最多顶点数#define E 30 /网络中最多边数#define MAX 1000.0 /网络中无边相连则为无穷大(用MAX表示)/连通网络及其生成树的存储表示typedef struct int startvex,endvex; /边的起点和终点 float length; /边的权值edge;float distNN; /连通网络的带权邻接矩阵edge tN-1; /最小生成树t由N-1条边组成int n,en; /顶点数n，边数envoid creategraph(void) /建立无向网络的邻接矩阵dist int i,j,k; float w; printf(请输入图中顶点个数:); scanf(%d,&n); printf(请输入图中边的条数:); scanf(%d,&en); getchar(); /跳过回车 for (i=0;i=n-1;i+) for (j=0;j=n-1;j+) distij=MAX; /邻接矩阵初始化 for (k=1;k=en;k+) /输入e条边(起点.终点.权) printf(i j w=);scanf(%d%d%f,&i,&j,&w); distij=w; distji=w; void prim(void) /普里姆算法:从第1个顶点出发构造连通网络dist的最小生成树t int i,j,m,v; float d,min,max=MAX; edge e; for (j=1;j=n-1;j+) /构造初始侯选边集 tj-1.startvex=1; /顶点1是第一个加入最小生成树中的点 tj-1.endvex=j+1; tj-1.length=dist0j; for (i=0;i=n-2;i+) /求最小生成树中第0至第n-2共n-1条边 min=max; for (j=i;j=n-2;j+) /在侯选边集中寻找最短边所在下标m if (tj.lengthmin) min=tj.length; m=j; e.startvex=tm.startvex; /将下标为m的边与下标为i的边交换 e.endvex=tm.endvex; e.length=tm.length; tm.startvex=ti.startvex; tm.endvex=ti.endvex; tm.length=ti.length; ti.startvex=e.startvex; ti.endvex=e.endvex; ti.length=e.length; printf(%d,%d,%g) ,ti.startvex-1,ti.endvex-1,ti.length); /输出第i条边 v=ti.endvex; /v为最小生成树中的新顶点 for (j=i+1;j=n-2;j+) /调整侯选边集 d=distv-1tj.endvex-1; if (dtj.length) tj.startvex=v; /起点为v,终点不变 tj.length=d; /权取较小的 printf(n);void main(void)creategraph(); prim();4.2.5 测试数据及测试结果用普里姆(Prim)算法求以下无向网的最小生成树： 无向网 最小生成树 请输入图中顶点个数:6请输入图中边的条数:10i j w=0 1 6i j w=0 2 1i j w=0 3 5i j w=1 2 5i j w=1 4 3i j w=2 3 5i j w=2 4 6i j w=2 5 4i j w=3 5 2i j w=4 5 6(0,2,1) (2,5,4) (5,3,2) (2,1,5) (1,4,3)4.2.6 算法复杂度分析Prim()算法中有两重for循环，所以时间复杂度为O(n2)。完整的克鲁斯卡尔(Kruskal)算法应包括对边按权值递增排序，上述算法假设边已排序的情况下，时间复杂度为O(e2)。 如果给定的带权连通无向图G有e条边,n个顶点，采用堆排序(在第11章中介绍)对边按权值递增排序，那么用克鲁斯卡尔算法构造最小生成树的时间复杂度降为O(elog2e)。 由于它与n无关，只与e有关，所以说克鲁斯卡尔算法适合于稀疏图。4.3 单源最短路经问题4.3.1 问题描述给定带权图G =(V,E)，还给定 V 中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路径长度，该问题称为单源最短路径问题。4.3.2 算法分析与设计4.3.3 算法描述狄克斯特拉(Dijkstra)算法4.3.4 程序实现/图的邻接矩阵存储表示头文件.h/-图的数组(邻接矩阵)存储表示-#define INFINITY 1000 /最大值#define MAX_VERTEX_NUM 20 /最大顶点个数typedef enum DG,DN,UDG,UDN GraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCellVRType adj; /VRType是顶点关系类型.对无权图用1或0表示相邻否;对带权图,则为权值类型 InfoType *info; /该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /存放顶点信息的一维数组 AdjMatrix arcs; /存放邻接矩阵的二维数组 int vexnum,arcnum; /图的当前顶点数和弧数 GraphKind kind; /图的种类标志MGraph;int LocateVex(MGraph G,VertexType v)/求顶点v在图G中的位置 for (int i=0; i=G.vexnum-1&strcmp(G.vexsi,v); i+) ; return i;void InitAM(MGraph &G,InfoType &IncInfo)/输入图的公共信息,初始化邻接矩阵G int i,j; coutG.vexnumG.arcnumIncInfo;/IncInfo为0则各弧不含其它信息 cout请输入图的G