算法分析与计实验报告.docxVIP

算法分析与设计实验报告学 院：　信息科学与工程学院专业班级：　物联网工程1201班　指导老师： 　　　李 敏 学号：　　0909120902姓名： 　　　姚洪齐目录实验一 递归与分治.............................3 二分查找..........................3快速排序..........................9实验二 回溯算法................................13 01背包问题......................13实验三 动态规划...............................24 最长子序列问题......................24 矩阵连乘问题........................27实验一 递归与分治实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。实验预习内容编程实现讲过的例题：二分有哪些信誉好的足球投注网站、合并排序、快速排序。对本实验中的问题，设计出算法并编程实现。试验内容和步骤1.二分查找实验内容在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。实验要求二分有哪些信誉好的足球投注网站方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O(logn)时间完成有哪些信誉好的足球投注网站任务。算法分析二分查找的基本思路是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x，算法终止；如果xa[n/2]，则只要在数组a的左半部分继续有哪些信誉好的足球投注网站x，如果xa[n/2]，则只要在数组a的右半部分继续有哪些信誉好的足球投注网站x。由于二分查找的数组不一定是一个整数数组，所以我采用了C++中的模板函数，将排序函数Sort和二分查找函数BinarySort写为了模板函数，这样不尽可以查找整数数组，也可以查找小数数组。由于查找的数组的长度不固定，所以我用了C语言中的malloc和realloc函数，时，在用realloc函数为数组再次分配空间。由于在随机输入一组数时不知在什么位置停止，所以在输入完一组数之后，按Ctrl+Z键结束输入，然后再用cin.clear()将输入恢复，再继续输入。该算法的流程图如下：调试结果实验源程序代码#includeiostream#includestdio.h#includestdlib.husing namespace std;#define N 10//初始空间大小#define n 10//增加空间大小templateclass Typevoid sort(Type a[],int num){ double temp; for(int i = 1;i = num-1;i++){ for(int j = 0;j num-i;j++){ if(a[j] a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } }}templateclass Typeint BinarySearch(Type *a,Type x,int m){ int left=0; int right=m-1; while(left=right){ int middle = (left+right)/2; if(x==a[middle]) return middle; if(xa[middle])left=middle+1; else right=middle-1; } return -1;}int main(){ int *a,num,length,i = 0; a = (int *)malloc(sizeof(int)*N); cout请输入一组数(Ctrl+z停止输入)endl; while(cina[i]){ i++; if(i=N){ a = (int *)realloc(a,sizeof(int)*(length+n)); length += n; } } sort(a,i); for(int j =