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

《2016春《计算机算法设计与分析》实验作业.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告学院计算机科学与技术学院专业计算机科学与技术班级课程算法分析与设计教师学号姓名学期2016年春季实验1算法设计与分析基础一、实验环境操作系统：WindowsXP或Windows7及以上编程语言：VisualC++6.0或VS2012二、实验目的①了解算法描述的各种方法，重点学会使用自然语言与伪代码描述算法的方法。养成先用自然语言或伪代码描述算法，然后再进行程序设计的习惯。②掌握进行算法复杂度分析的方法。三、实验内容1.1求两个整数的最大公约数。1.2输出杨辉三角形前n行。例如，杨辉三角形前5行如下:1111211331146411.3统计数

2、字问题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)End(算法结束)1.1.3程序设计

3、与实现方法1：欧几里德算法的C语言描述如下：#includemain(){intm,n,r;printf(“请输入两个正整数：”)；scanf(“%d%d”,&m,&n);printf(“%d和%d的最大公约数是：”，m,n);r=m%n;while(r!=0){m=n;n=r;r=m%n;}printf(“%d”,n);}方法2：欧几里德算法的C++语言描述如下：#includeintCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n

4、;}returnn;}voidmain(){intm,n;cout<<"请输入两个正整数：";cin>>m>>n;cout<

5、述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输

6、出结果：数字: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测试数据及测试结果1.4.6算法复杂度分析实验2递归与分治一、实验环境操作系统：WindowsXP编程语言：VisualC++6.0或VS2012二、实验目的①学习和了解递归与分治算法的概念和基本思想，熟悉对递归与分治问题的分析方法及其适用范围；②掌握递归与分治算法的设计思路和基本步骤

7、，学会使用递归与分治算法解决实际问题。三、实验内容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

8、，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序