算法分析与设计实验报告

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

1、算法分析与设计实验报告学院：　信息科学与工程学院专业班级：　物联网工程1201班　指导老师：　　　李敏学号：　　090912090241姓名：　　　姚洪齐目录实验一递归与分治.............................3二分查找..........................3快速排序..........................9实验二回溯算法................................1301背包问题......................13实验三动态规划....................

2、...........2441最长子序列问题......................24矩阵连乘问题........................2741实验一递归与分治l实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。l实验预习内容编程实现讲过的例题：二分搜索、合并排序、快速排序。对本实验中的问题，设计出算法并编程实现。l试验内容和步骤1.二分查找Ø实验内容在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在

3、L中的位置或者x不在L中的信息。Ø实验要求二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O(logn)时间完成搜索任务。Ø算法分析二分查找的基本思路是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x，算法终止；如果xa[n/2]，则只要在数组a的右半部分继续搜索x。由于二分查找的数组不一定是一个整数数组，所以我采用了C++中的模板函数，将排序函数Sort和二分查找函数BinarySort写为了模板函数，这样不尽可以查找整数数组

4、，也可以查找小数数组。由于查找的数组的长度不固定，所以我用了C语言中的malloc和realloc函数，时，在用realloc函数为数组再次分配空间。由于在随机输入一组数时不知在什么位置停止，所以在输入完一组数之后，按Ctrl+Z键结束输入，然后再用cin.clear()将输入恢复，再继续输入。41Ø该算法的流程图如下：41Ø调试结果41Ø实验源程序代码#include#include#includeusingnamespacestd;#defineN10//初始空间大小#definen10

5、//增加空间大小templatevoidsort(Typea[],intnum){doubletemp;for(inti=1;i<=num-1;i++){for(intj=0;ja[j+1]){41temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}templateintBinarySearch(Type*a,Typex,intm){intleft=0;intright=m-1;while(left<=right){intmiddle=(le

6、ft+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;}41intmain(){int*a,num,length,i=0;a=(int*)malloc(sizeof(int)*N);cout<<"请输入一组数(Ctrl+z停止输入)"<>a[i]){i++;if(i>=N){a=(int*)realloc(a,sizeof(int)*(length+n));length+=n

7、;}}sort(a,i);for(intj=0;j>num;if(BinarySearch(a,num,i)!=-1){41cout<

8、le)*N);cout<<"请输入一组数"<>b[i1]){i1++;if(i1>=N){