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

1实验报告学院计算机科学与技术学院专业计算机科学与技术班级课程算法分析与设计教师学号姓名学期2016年春季2实验1算法设计与分析基础一、实验环境操作系统：WindowsXP或Windows\7及以上编程语言：VisualC++6.0或VS2012二、实验目的①了解算法描述的各种方法，重点学会使用自然语言与伪代码描述算法的方法。养成先用自然语言或伪代码描述算法，然后再进行程序设计的习惯。②掌握进行算法复杂度分析的方法。三、实验内容1.1求两个整数的最大公约数。1.2输出杨辉三角形前n行。例如，杨辉三角形前5行如下:1111211331146411.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)mmodn→rwhiler≠0do{n→mr→nmmodn→r}write(n)3End(算法结束)1.1.3程序设计与实现方法1：欧几里德算法的C语言描述如下：#includestdio.hmain(){intm,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(“%d\n”,n);}方法2：欧几里德算法的C++语言描述如下：#includeiostream.hintCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){intm,n;cout请输入两个正整数：;cinmn;coutm与n的最大公约数是：;coutCommonFactor(m,n)endl;}1.1.4测试数据及测试结果运行程序：请输入两个正整数：181218与12的最大公约数是：61.1.5算法复杂度分析时间复杂度分析：辗转相除法的循环次数与m、n的大小不成正比，∴时间复杂度为O(1)空间复杂度分析：算法在执行过程中临时存储单元为1个(变量r)，∴空间复杂度为O(1)41.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(1≤n≤109)，计算书的全部页码中分别用到多少次数字0，1，2，…，9。输入数据、输出结果示例输入数据：11输出结果：数字:0123456789用到次数:14111111111.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测试数据及测试结果51.4.6算法复杂度分析实验2递归与分治一、实验环境操作系统：WindowsXP编程语言：VisualC++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归并排序(MergingSort)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]一趟归并之后[3849][6597][1376][27]6二趟归并之后[38496597][132776]三趟归并之后[13273849657697]图10.132-路归并排序示例2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。2.2.3算法描述2.2.4程序设计与实现2.2.5测试数据及测试结果2.2.6算法复杂度分析2.3快速排序(QuickSort)2.2.1问题描述快速排序(QuickSort)是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。2.2.2算法分析与设计假设待排序的序列为{L.r[s]，L.r[s+1]，…，L.r[t]}，首先任意选取一个记录(通常可选第一个记录L.r[s]作为枢轴(或支点)(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算法分析与设计72.5.3算法描述2.5.4程序设计与实现2.5.5测试数据及测试结果2.5.6算法复杂度分析实验3动态规划一、实验环境操作系统：WindowsXP编程语言：VisualC++6.0或VS2012二、实验目的1、学习和了解动态规划算法的概念和基本思想；2、熟悉对动态规划问题的分析方法及其适用范围；3、掌握动态规划算法的设计思路和基本步骤；4、学会使用动态规划法解决实际问题。三、实验内容1．旅行家问题(TSP)2．多段图的最短路径问题3．0-1背包问题(knapsackproblem)。4．最长公共子序列(LCS)问题5．数塔问题四、实验开始3.1旅行家问题(TSP)3.1.1问题描述旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。3.1.2算法分析与设计各个城市间的距离可以用代价矩阵来表示。证明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要C=∞3675∞2364∞2375∞带权图的代价矩阵8短，从而导致矛盾。所以，TSP问题满足最优性原理。假设从顶点i出发，令d(i,V')表示从顶点i出发经过V'中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，V'＝V－{i}，于是，TSP问题的动态规划函数为：d(i,V')=min{cik+d(k,V－{k})}(k∈V')（1）d(k,{})=cki(k≠i)（2）从城市0出发经城市1、2、3然后回到城市0的最短路径长度是：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}这是最后一个阶段的决策，而：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}d(3,{1,2})=min{c31+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(1→0)d(2,{})=c20=6(2→0)d(3,{})=c30=3(3→0)再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)d(1,{3})=c13+d(3,{})=3+3=6(1→3)d(2,{3})=c23+d(3,{})=2+3=5(2→3)d(2,{1})=c21+d(1,{})=4+5=9(2→1)(3,{1})=c31+d(1,{})=7+5=12(3→1)d(3,{2})=c32+d(2,{})=5+6=11(3→2)再向前倒退，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)最后有：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)所以，从顶点0出发的TSP问题的最短路径长度为10，最短路径是0→1→2→3→0。动态规划法求解TSP问题的填表过程假设n个顶点用0～n-1的数字编号，首先生成1～n-1个元素的子集存放在数组V[2n-1]中，设数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次，最后回到出发点0的最短路径长度。填表方法：自底向上，逐步求值。利用前一步求出的值计算出后一步的值填入表中，每一步结束后选择最小值作为子问题的最优值，最后一步为原问题的最优解。ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0101586726951033121114第1步第2步第3步第4步第1步：填写第1列，9d(1,{})=c10=5(1→0)；d(2,{})=c20=6(2→0)；d(3,{})=c