《算法设计与分析快速排序与矩阵连乘实验.doc》由会员分享，可在线阅读，更多相关《算法设计与分析快速排序与矩阵连乘实验.doc（12页珍藏版）》请在三一办公上搜索。
1、实验4 快速排序与矩阵连乘实验实验内容1. 快速排序。编程实现快速排序算法，深入理解快速排序算法的基本思想。【输入：一个一维整型数组；输出：快速排序之后的一维整型数组】源代码：package Test1;public class Test1 static int a=2,1,4,0,3,6;public static void main(String args) quick(a); for(int i=0;ia.length;i+) System.out.println(ai);/ 利用tmp保存参照数，虽然过程中有覆盖，但最终覆盖掉的值其实就是tmp中的数！public static int
2、 getMiddle(int list, int low, int high) int tmp = listlow; /数组的第一个作为中轴 while (low high) while (low = tmp) high-; listlow = listhigh; /比中轴小的记录移到低端 while (low high & listlow = tmp) low+; listhigh = listlow; /比中轴大的记录移到高端 listlow = tmp; /中轴记录到尾 return low; /返回中轴的位置 public static void _quickSort(int list
3、, int low, int high) if (low 0) /查看数组是否为空 _quickSort(a2, 0, a2.length - 1); 2. 随机化快速排序。使用Java或C+中内置的随机函数实现随机化快速排序，在数组中随机选择一个元素作为分区的主元(Pivot)。【输入：一个一维整型数组；输出：随机化快速排序之后的一维整型数组】源代码：#include #include void swap(int *x,int *y) int temp; temp = *x; *x = *y; *y = temp;int choose_pivot(int i,int j ) return(i
4、+j) /2);void quicksort(int list,int m,int n) int key,i,j,k; if( m n) k = choose_pivot(m,n); swap(&listm,&listk); key = listm; i = m+1; j = n; while(i = j) while(i = n) & (listi = m) & (listj key) j-; if( i j) swap(&listi,&listj); / 交换两个元素的位置 swap(&listm,&listj); / 递归地对较小的数据序列进行排序 quicksort(list,m,j-
5、1); quicksort(list,j+1,n); void printlist(int list,int n) int i; for(i=0;in;i+) printf(%dt,listi);void main() const int MAX_ELEMENTS = 10; int listMAX_ELEMENTS; int i = 0; / 产生填充序列的随机数 for(i = 0; i MAX_ELEMENTS; i+ ) listi = rand(); printf(进行排序之前的序列:n); printlist(list,MAX_ELEMENTS); / sort the list
6、using quicksort quicksort(list,0,MAX_ELEMENTS-1); / print the result printf(使用快速排序算法进行排序之后的序列:n); printlist(list,MAX_ELEMENTS);3. 求如图所示一个上三角矩阵中每一条斜线中的最大元素(L)和最小元素(S)。输入：1 3 5 7 11 20 6 8 2 3 13 7 4 8 9 20 3 10 12 6 15输出：L1 = 20, S1 = 1L2 = 8, S2 = 3L3 = 10, S3 = 2L4 = 9, S4 = 3L5 = 13, S5 = 11L6 = 2
7、0, S6 = 20源代码：4. 矩阵连乘问题。使用动态规划算法求解矩阵连乘问题。【输入：一个存储矩阵维数的一维数组；输出：矩阵连乘最优计算次序。】例如：输入：一维数组30, 35, 15, 5, 10, 20, 25输出：A2:2 * A3:3A1:1 * A2:3A4:4 * A5:5A4:5 * A6:6A1:3 * A4:6源代码：#include using namespace std;/MatrixChain计算mij所需的最少数乘次数/并记录断开位置sij/void MatrixChain(int *p,int n,int *m,int *s) for(int i=0;in;i+
8、) mii=0;/单个矩阵相乘，所需数乘次数为0 /以下两个循环是关键之一，以6个矩阵为例(为描述方便，mij用ij代替) /需按照如下次序计算 /01 12 23 34 45 /02 13 24 35 /03 14 25 /04 15 /05 /下面行的计算结果将会直接用到上面的结果。例如要计算14，就会用到12，24；或者13，34等等 for(int r=1;rn;r+) for(int i=0;in-r;i+) int j=i+r; /首先在i断开，即（Ai*（Ai+1.Aj） mij=mii+mi+1j+pi*pi+1*pj+1; sij=i; for(int k=i+1;kj;k+
9、) /然后在k（从i+1开始遍历到j-1）断开，即（Ai.Ak)*（Ak+1.Aj） int t=mik+mk+1j+pi*pk+1*pj+1; if(tmij)/找到更好的断开方法 mij=t;/记录最少数乘次数 sij=k;/记录断开位置 /如果使用下面注释的循环，则是按照如下次序计算 /01 02 03 04 05 /12 13 14 15 /23 24 25 /34 35 /45 /当要计算时14，会用到12，24，而此时24并没有被计算出来。/* for(int i=0;in;i+) for( int j=i+1;jn;j+) mij=mii+mi+1j+pi*pi+1*pj+1;
10、sij=i; for(int k=i+1;kj;k+) int t=mik+mk+1j+pi*pk+1*pj+1; if(tmij) mij=t; sij=k; */Traceback打印Ai:j的加括号方式/void Traceback(int i,int j,int *s) /sij记录了断开的位置，即计算Ai:j的加括号方式为： /(Ai:sij)*(Asij+1:j) if(i=j)return; Traceback(i,sij,s);/递归打印Ai:sij的加括号方式 Traceback(sij+1,j,s);/递归打印Asij+1:j的加括号方式 /能走到这里说明i等于sij，si
11、j+1等于j /也就是说这里其实只剩下两个矩阵，不必再分了 coutAi和A(sij+1)相乘endl; int _tmain(int argc, _TCHAR* argv) int n=6;/矩阵的个数 int *p=new intn+1; /p0:第一个矩阵的行数 /p1:第一个矩阵的列数，第二个矩阵的行数 /p2:第二个矩阵的列数，第三个矩阵的行数 p0=30; p1=35; p2=15; p3=5; p4=10; p5=20; p6=25; int *m,*s; m=new int*n; for( int i=0;in;i+) mi=new intn; s=new int*n; for
12、(int i=0;in;i+) si=new intn; MatrixChain(p,n,m,s); Traceback(0,n-1,s);for(int i=0;in;i+) delete mi; mi=NULL; delete si; si=NULL; delete m; m=NULL; delete s; s = NULL; delete p; p = NULL; return 0;说明：(1) 编程语言不限，建议使用Java、C+或者C语言。(2) 需要将程序源代码复制并粘贴到每道题之后的方框中（部分题需要填写输出结果）。(3) 在提交实验报告时，先关闭所有文件，再将文件名改为“学号-4.doc”；将实验报告在指定时间之前由学习委员收集整理后统一发送至邮箱weiliu_china。
