《算法分析与设计实验报告(共25页)》由会员分享，可在线阅读，更多相关《算法分析与设计实验报告(共25页)（25页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上算法分析与设计实验报告目录实验一：递归与分治1 二分查找 归并排序 快速排序实验二：回溯算法8 01背包实验三：动态规划12 矩阵连乘最少乘法数专心-专注-专业实验一：递归与分治一、实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。二、实验内容1 二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。2 合并排序3 快速排序对本实验中的问题，设计出算法并编程实现。实验总结及思考3、 实验过程1. 二分
2、查找算法：BinSearch(aArray0,1n-1,key) low-0; right-n-1; while low=right do maArraymid l-mid+1; if keyaArraymid r-mid-1; if key=aArraymid return mid; 代码：#include using namespace std;void Binary(int aArray,int key,int length) /二分查找 int mid,low,high; mid=low=0; high=length-1; while(low=high) mid = low + (hi
3、gh - low)/2); /使用 (low + high) / 2 会有整数溢出的问题 if(low=length|high - low=0) cout元素不存在，查找失败aArraymid) /key在右边 low=mid+1; else if(keyaArraymid) /key在左边 high=mid-1; else cout查找成功，元素的位置是:midendl; break; int main()int length = 0;int key = 0;cout请输入数组的长度： length;int* aArray = new intlength;cout请输入数组：endl; fo
4、r (int i = 0; i aArrayi;cout请输入待查找的数字： key;Binary(aArray,key,length);delete aArray; /释放空间 return 0;二分查找的平均时间复杂度为O(logn)最坏情况下的时间复杂度O(n)运行截图：2. 合并排序基本操作如下: （1）分解:将n 个元素分成各含n/2 个元素的子序列 （2）解决:用合并排序法对两个子序列递归地排序 （3）合并:合并两个已排好序的子序列得到排序结果 在对子序列排序时，其长度为1 时递归结束。单个元素被视为是已排好序的。算法：MergeSort(A0n-1)if n1 copy A0n/
5、2-1toB0n/2-1 copy An/2n-1toC0n/2-1 MergeSort(B0n/2-1) MergeSort(C0n/2-1) Merge(B,C,A)Merge(B0p-1,C0q-1,A0P+q-1)i-0;j-0;k-0while ip and jq do if Bi=Cj Ak-Bi;i-i+1; else Ak-Cj;j-j+1; k-k+1; if i=p copyCjq-1toAkp+q-1 elsecopyBiq-1toAkp+q-1代码：#includeusing namespace std;void Merge(int *a, int p, int q,
6、int r)/把数组a分成L，R，再排序合并成a int n1 = q-p+1;int n2 = r-q;int *L = new intn1+1;int *R = new intn2+1;int i, j, k;for (i=0; in1; i+)Li = ap+i;for (j=0; jn2; j+)Rj = aq+j+1;Ln1 = ;Rn2 = ;for (i=0,j=0,k=p;k=r;k+)if (Li=Rj)ak = Li;i+;elseak = Rj;j+;delete L;delete R;void MergeSort(int *a, int p, int r)/递归调用 i
7、f (pr)int q = (p+r)/2;MergeSort(a, p, q);MergeSort(a, q+1, r);Merge(a, p, q, r); int main()int j = 0;cout请输入数组的长度： j;int* aArray = new intj;cout请输入原始数组：endl; for (int i = 0;i aArrayi;MergeSort(aArray,0,j-1); cout排序后的数组：endl; for (int i = 0;i j;i+)cout aArrayi ;delete aArray;/释放空间 system(pause);retur
8、n 0;归并排序的平均时间复杂度：O(logn)运行截图：3. 快速排序 实现快速排序的分治过程如下: （1）分解:数组Ap.r被划分为两个(可能空)子数组Ap.q-1和Aq+1.r, 使得 Ap.q-1中的每个元素都小于等于 A(q),而且，小于等于 Aq+1.r中的 元素。下标q 也在这个划分过程中进行计算。 （2）解决:通过递归调用快速排序，对子数组Ap.q-1和Aq+1.r排序 （3）合并:因为两个子数组是就地排序的，将它们的合并不需要操作，整个数组 Ap.r已排序。代码：#includeusing namespace std;void quickSort(int s, int l,
9、int r)if (lr) int i = l, j = r;int x = sl;/找一个基准数while (i j) while(i = x) / 从右向左找第一个小于x的数j-; if(i j)si+ = sj;while(i j & si x) / 从左向右找第一个大于等于x的数i+; if(i j)sj- = si;si = x;quickSort(s, l, i - 1); / 递归调用quickSort(s, i + 1, r);int main()int j = 0;cout请输入数组的长度： j;int* aArray = new intj;cout请输入原始数组：endl; for (int i = 0;i aArrayi;quickSort(aArray,0,j-1);cout排序后的数组：endl; for (int i = 0;i j;i+)cout aArrayin) /递归结束条件 output(); /相应的处理(输出结果)el
