最新算法设计与分析实验报告.doc

《最新算法设计与分析实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、本科实验报告课程名称：算法设计与分析实验项目：递归与分治算法实验地点：计算机系实验楼110专业班级：物联网1601学号：2016002105学生姓名：俞梦真指导教师：郝晓丽2018年05月04日实验一递归与分治算法1.1实验目的与要求1．进一步熟悉C/C++语言的集成开发环境；2．通过本实验加深对递归与分治策略的理解和运用。1.2实验课时2学时1.3实验原理分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。需要注意的是，分治法使用递归的思想。划分后的每一个子问题

2、与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。1.4实验题目1．上机题目：格雷码构造问题Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。对于给定的正整数n，格雷码为满足如下条件的一个编码序列。（1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。（2）序列中无相同的编码。（3）序列中位置相邻的两个编码恰有一位不同。2．设计思想：根据格雷码的性质，找到他的规律，可发现，1位是01

3、。两位是00011110。三位是000001011010110111101100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。3．代码设计：#include#include#include#includeusingnamespacestd;//求格雷码递推式子：G(n-1)=B(n-1)G(i)=B(i+1)异或B(i)(0My_grad;voidget_grad(intn){//cou

4、t<<1<1){//cout<<1<tmp;for(intj=0;j=0;j--){strings="1";s+=tmp[j];My

5、_grad.push_back(s);}}}}intmain(){intn;while(cin>>n){get_grad(n);for(inti=0;i

6、析二分查找和快速排序中使用的分治思想。答：1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。（4）分析二次取中法和锦标赛算法中的分治思想。二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r部分，对找出r个中的中间值，并求r组的中间值中的中间值。锦标赛算法：两两分组比较，大者进入下一轮

7、，知道剩下1个元素max为止。在每次比较中淘汰较小元素，将被淘汰元素记录在淘汰它的元素的链表上。检查max的链表，从中知道最大元素，即second本科实验报告课程名称：算法设计与分析实验项目：贪心算法实验地点：计算机系实验楼110专业班级：物联网1601学号：2016002105学生姓名：俞梦真指导教师：郝晓丽2018年05月04日实验二贪心算法2.1实验目的与要求1．理解贪心算法的基本思想；2．运用贪心算法解决实际问题，加深对贪心算法的理解和运用。2.2实验课时4学时（课内2学时+课外2学时）2.3实验原理贪心算法的思想：（1）贪心算法（GreedyAppr

8、oach）能得到问题的最优解，要证明我