算法设计与分析的实验报告 2.docx

实验一递归与分治策略1. 实验内容：1) Hanoi塔问题2) Strassen矩阵乘法3) 合并排序（Merge Sort）4) 快速排序（Quick Sort）汉诺塔：代码：package towers;public class Pai public static void main(String args) towers(4,A,B,C); public static void towers(int n,char frompeg,char topeg,char auxpeg) if (n=1) System.out.println(move disk1 from peg+frompeg+to peg+topeg); return; towers(n-1,frompeg,auxpeg,topeg); System.out.println(move disk+n+ from peg+frompeg+to peg+topeg); towers(n-1,auxpeg,topeg,frompeg);运行结果：（2）矩阵相乘：代码：package help;import java.io.*; import java.util.*; class matrix /定义矩阵结构 public int m = new int1010; public class Strassen public int IfIsEven(int n)/判断输入矩阵阶数是否为2k int a = 0,temp=n; while(temp%2=0) if(temp%2=0) temp/=2; else a=1; if(temp=1) a=0; return a; public void Divide(matrix d,matrix d11,matrix d12,matrix d21,matrix d22,int n)/分解矩阵 int i,j; for(i=1;i=n;i+) for(j=1;j=n;j+) d11.mij=d.mij; d12.mij=d.mij+n; d21.mij=d.mi+nj; d22.mij=d.mi+nj+n; public matrix Merge(matrix a11,matrix a12,matrix a21,matrix a22,int n)/合并矩阵 int i,j; matrix a = new matrix(); for(i=1;i=n;i+) for(j=1;j=n;j+) a.mij=a11.mij; a.mij+n=a12.mij; a.mi+nj=a21.mij; a.mi+nj+n=a22.mij; return a; public matrix TwoMatrixMultiply(matrix x,matrix y) /阶数为2的矩阵乘法 int m1,m2,m3,m4,m5,m6,m7; matrix z = new matrix(); m1=(y.m12 - y.m22) * x.m11; m2=y.m22 * (x.m11 + x.m12); m3=(x.m21 + x.m22) * y.m11; m4=x.m22 * (y.m21 - y.m11); m5=(x.m11 + x.m22) * (y.m11+y.m22); m6=(x.m12 - x.m22) * (y.m21+y.m22); m7=(x.m11 - x.m21) * (y.m11+y.m12); z.m11 = m5 + m4 - m2 + m6; z.m12 = m1 + m2; z.m21 = m3 + m4; z.m22 = m5 + m1 - m3 - m7; return z; public matrix MatrixPlus(matrix f,matrix g,int n) /矩阵加法 int i,j; matrix h = new matrix(); for(i=1;i=n;i+) for(j=1;j=n;j+) h.mij=f.mij+g.mij; return h; public matrix MatrixMinus(matrix f,matrix g,int n) /矩阵减法方法 int i,j; matrix h = new matrix(); for(i=1;i=n;i+) for(j=1;j=n;j+) h.mij=f.mij-g.mij; return h; public matrix MatrixMultiply(matrix a,matrix b,int n) /矩阵乘法方法 int k; matrix a11,a12,a21,a22; a11 = new matrix(); a12 = new matrix(); a21 = new matrix(); a22 = new matrix(); matrix b11,b12,b21,b22; b11 = new matrix(); b12 = new matrix(); b21 = new matrix(); b22 = new matrix(); matrix c11,c12,c21,c22,c; c11 = new matrix(); c12 = new matrix(); c21 = new matrix(); c22 = new matrix(); c = new matrix(); matrix m1,m2,m3,m4,m5,m6,m7; k=n; if(k=2) c=TwoMatrixMultiply(a,b); return c; else k=n/2; Divide(a,a11,a12,a21,a22,k); /拆分A、B、C矩阵 Divide(b,b11,b12,b21,b22,k); Divide(c,c11,c12,c21,c22,k); m1=MatrixMultiply(a11,MatrixMinus(b12,b22,k),k); m2=MatrixMultiply(MatrixPlus(a11,a12,k),b22,k); m3=MatrixMultiply(MatrixPlus(a21,a22,k),b11,k); m4=MatrixMultiply(a22,MatrixMinus(b21,b11,k),k); m5=MatrixMultiply(MatrixPlus(a11,a22,k),MatrixPlus(b11,b22,k),k); m6=MatrixMultiply(MatrixMinus(a12,a22,k),MatrixPlus(b21,b22,k),k); m7=MatrixMultiply(MatrixMinus(a11,a21,k),MatrixPlus(b11,b12,k),k); c11=MatrixPlus(MatrixMinus(MatrixPlus(m5,m4,k),m2,k),m6,k); c12=MatrixPlus(m1,m2,k); c21=MatrixPlus(m3,m4,k); c22=MatrixMinus(MatrixMinus(MatrixPlus(m5,m1,k),m3,k),m7,k); c=Merge(c11,c12,c21,c22,k); /合并C矩阵 return c; public matrix GetMatrix(matrix X,int n) int i,j; X = new matrix(); Random random = new Random(); for(i=1;i=n;i+) for(j=1;j=n;j+) X.mij = (int)(Math.random()*10); for(i=1;i=n;i+) for(j=1;j=n;j+) System.out.print(X.mij+ ); System.out.println(); return X; public matrix UsualMatrixMultiply(matrix A,matrix B,matrix C,int n) int i,j,t,k; for (i=1;i=n;i+) for (j=1;j=n;j+) for (k=1,t=0;k=n;k+) t+=A.mik*B.mkj; C.mij=t; return C; public static void main(String args)throws IOException Strassen instance = new Strassen(); int i,j,n; matrix A,B,C,D; A = new matrix(); B = new matrix(); C = new matrix(); D = new matrix(); Scanner in = new Scanner(System.in); System.out.print(输入矩阵的阶数: ); n = in.nextInt(); if(instance.IfIsEven(n)=0) System.out.println(矩阵A:); A=instance.GetMatrix(A,n); System.out.println(矩阵B:); B=instance.GetMatrix(B,n); if(n=1) C.m11=A.m11*B.m11; /矩阵阶数为1时的特殊处理 else C=instance.MatrixMultiply(A,B,n); System.out.println(Strassen矩阵C为:); for(i=1;i=n;i+) for(j=1;j=n;j+) System.out.print(C.mij + ); System.out.println(); D = instance.UsualMatrixMultiply(A,B,D,n); System.out.println(普通乘法矩阵D为:); for(i=1;i=n;i+) for(j=1;j=n;j+) System.out.print(D.mij + ); System.out.println(); else System.out.println(输入的阶数不是2的N次方); 运行结果：（3）合并排序：代码: import java.util.Scanner;public class mergesort public static void main(String args) throws ExceptionSystem.out.println(要排序的数字的个数是：);Scanner sc=new Scanner(System.in);int sum=sc.nextInt();int a=new int sum;System.out.println(输入待排序的数字：);for(int i=0; ia.length; i+)ai=sc.nextInt();System.out.println(排序后为：);mergeSort(a,0,a.length-1);for(int i=0; ia.length; i+)System.out.print(ai+t);public static void mergeSort (int a, int begin, int end) if(beginend)int a1=new intend-begin+1;int begin0=0;int mid=(begin+end)/2;mergeSort(a,begin,mid);mergeSort(a,mid+1,end);int begin1=begin;int begin2=mid+1;int end1=mid;int end2=end;for(int i=0; ia1.length; i+)if(begin1=end1 & begin2=end2)if(abegin1abegin2)a1begin0=abegin1;begin0+;begin1+;elsea1begin0=abegin2;begin0+;begin2+;elsebreak;if(begin1=end1)for(;begin0a1.length; begin0+)a1begin0=abegin1;begin1+;elsefor(;begin0a1.length; begin0+)a1begin0=abegin2;begin2+;for(int i=0; ia1.length; i+)abegin+i=a1i;运行结果：（4）快速排序：代码：package src;public class Qsort public static void main(String args) quicksort qs = new quicksort();int data = 44,22,2,32,54,22,88,77,99,11; qs.data = data; qs.sort(0, qs.data.length-1); qs.display(); class quicksortpublic int data;private int partition(int sortArray,int low,int hight)int key = sortArraylow;while(lowhight)while(low=key)hight-; sortArraylow = sortArrayhight; while(lowhight & sortArraylow=key)