算法分析与设计实验报告24页

1、算法分析与设计实验报告目录实验一：递归与分治1 二分查找 归并排序 快速排序实验二：回溯算法8 01背包实验三：动态规划12 矩阵连乘最少乘法数实验一：递归与分治一、实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。二、实验内容1 二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。2 合并排序3 快速排序对本实验中的问题，设计出算法并编程实现。实验总结及思考3、 实验过程1. 二分查找算法：BinSearch(aArray

2、0,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 + (high - low)/2); /使用 (lo

3、w + 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; for (int i = 0; i aArra

4、yi;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/2-1toB0n/2-1 copy An/

5、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, int r)/把数组a分成L，R，再排序合

6、并成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 = 10000000;Rn2 = 10000000;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)/递归调用 if (pr

7、)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);return 0;归

8、并排序的平均时间复杂度：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, int r

9、)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

10、(int i = 0;i aArrayi;quickSort(aArray,0,j-1);cout排序后的数组：endl; for (int i = 0;i j;i+)cout aArrayin) /递归结束条件 output(); /相应的处理(输出结果)elseam=0; /设置状态：0表示不要该物品search(m+1); /递归搜索：继续确定下一个物品am=1; /设置状态：1表示要该物品search(m+1); /递归搜索：继续确定下一个物品2.用回溯算法搜索子集树的一般模式void search(int m)if(mn) /递归结束条件 output(); /相应的处理(输出结果)

11、elsefor(i=m;i=n;i+)swap(m,i); /交换am和aiif()if(canplace(m) /如果m处可放置search(m+1); /搜索下一层swpa(m,i); /交换am和ai(换回来)四、回溯算法解决0-1背包问题在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。0代表不装进背包，1代表装进背包，对树进行深度优先搜索，判断是否为可行解，若为可行解且放进去之后最大价值大于当前最大价值则修改当前最

12、大价值和背包余量。（没有进行减支）代码：#include void readdata();void search(int);void checkmax();void printresult();int c=35, n=10; /c:背包容量；n：物品数int w10, v10; /wi、vi:第i件物品的重量和价值int a10, max; /a数组存放当前解各物品选取情况；max：记录最大价值 /ai=0表示不选第i件物品，ai=1表示选第i件物品int main()readdata(); /读入数据search(0); /递归搜索printresult();void search(int

13、m)if(m=n)checkmax(); /检查当前解是否是可行解，若是则把它的价值与max比较elseam = 1; /不选第m件物品search(m+1); /递归搜索下一件物品am = 0; search(m+1);void checkmax()int i, weight=0, value=0;for(i = 0;in;i+)if(ai=1) /如果选取了该物品weight = weight + wi; /累加重量value = value + vi; /累加价值if(weightmax) /且价值大于maxmax = value; /替换maxvoid readdata()int i;

14、for(i=0;in;i+)printf(请输入第%d个物品的重量和价值n,i+1);scanf(%d %d,&wi,&vi); /读入第i件物品重量和价值void printresult()printf(背包可以装的最大价值为%d,max); 运行截图：实验三：动态规划一、实验目的 理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。2、 动态规划的基本思想对于一个多阶段过程问题，是否可以分段实现最优决策，信赖于该问题是否有最优子

15、结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。 最优子结构性质:原问题的最优解包含了其子问题的最优解 子问题的重叠性质:每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素动态规划一般方法 1.找出最优解的性质，并刻画其结构特征 2.递归地定义最优值(写出动态规划方程) 3.以自底向上的方式计算出最优值 三、用动态规划法计算矩阵连乘需要的最少乘法次数在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个pq的矩阵，B是一个qr的矩阵，则其乘积C=AB是一

16、个pr的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：现在的问题是，给定n个矩阵A1,A2,An。其中Ai与Ai+1是可乘的，i=1,2,n-1。要求计算出这n个矩阵的连乘积A1A2An。递归公式： 代码：#includeint n; /矩阵个数(0100)int p101; /矩阵维数(n+1) void Matrix_mult() int Arr101101,temp;/(Arr00不用)Arrij存放从矩阵i到矩阵j的最小矩阵乘法数 int i,j,k; int d; /矩阵间隔d for(i=1;i=n;i+) Arrii=0;/第i个矩阵到第i个矩阵乘法数为0 for(d=1;d=n-1;d+)/矩阵间隔r/矩阵链长度d+1 for(i=1;i=n-d;i+)/i=1.n-d j=i+d; /ii+d构成长度为r+1的矩阵链 Arrij=0+Arri+1j+pi-1*pi*pj; /截断位置为i for(k=i+1;kj;k+) /截断位置为k=i+1,i+2.j-1 temp=Arrik+Arrk+1j+pi-1*pk*pj; if(tempArrij) Arrij=temp; /获得从矩阵i到矩阵j的最小矩阵乘法数 printf(输入的%d个矩阵相乘的最少乘法数为：,n); printf(%dn,Arr1n); /从第1个矩阵到