算法设计与分析-_快速排序与矩阵连乘实验.doc

实验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 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, 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+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-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 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 = 20, 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+) 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+) /然后在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; 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，sij+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(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;