算法设计实验报告

1.hanoi塔packagesyy;importjava.util.*;publicclassHanoi{ publicstaticvoidmove(intn,inta,intb) { System.out.println("把第"+n+"个盘子"+"从第"+a+"个塔座移到第"+b+"个塔座"); } publicstaticvoidhanoi(intn,inta,intb,intc) { if(n>0) { hanoi(n-1,a,c,b); move(n,a,b); hanoi(n-1,c,b,a); } } publicstaticvoidmain(String[]args) { System.out.println("请输入一个人不小于0的盘子的个数！"); Scannerscan=newScanner(System.in); intn=scan.nextInt(); intx=1,y=2,z=3; hanoi(n,x,y,z); }}2.Stassen矩阵乘法：packagesyy;importjava.io.*;importjava.util.*;classmatrix{publicint[][]m=newint[32][32];}publicclassjzcf{publicintjudgment(intn){intflag=0,temp=n;while(temp%2==0){if(temp%2==0)temp/=2;elseflag=1;}if(temp==1)flag=0;returnflag;}publicvoidDivide(matrixd,matrixd11,matrixd12,matrixd21,matrixd22,intn)/*分解矩阵方法*/{inti,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++){d11.m[i][j]=d.m[i][j];d12.m[i][j]=d.m[i][j+n];d21.m[i][j]=d.m[i+n][j];d22.m[i][j]=d.m[i+n][j+n];}}publicmatrixMerge(matrixa11,matrixa12,matrixa21,matrixa22,intn)/*合并矩阵方法*/{inti,j;matrixa=newmatrix();for(i=1;i<=n;i++)for(j=1;j<=n;j++){a.m[i][j]=a11.m[i][j];a.m[i][j+n]=a12.m[i][j];a.m[i+n][j]=a21.m[i][j];a.m[i+n][j+n]=a22.m[i][j];}returna;}publicmatrixAdhocMatrixMultiply(matrixx,matrixy)/*阶数为2的矩阵乘法方法*/{intm1,m2,m3,m4,m5,m6,m7;matrixz=newmatrix();m1=(y.m[1][2]-y.m[2][2])*x.m[1][1];m2=y.m[2][2]*(x.m[1][1]+x.m[1][2]);m3=(x.m[2][1]+x.m[2][2])*y.m[1][1];m4=x.m[2][2]*(y.m[2][1]-y.m[1][1]);m5=(x.m[1][1]+x.m[2][2])*(y.m[1][1]+y.m[2][2]);m6=(x.m[1][2]-x.m[2][2])*(y.m[2][1]+y.m[2][2]);m7=(x.m[1][1]-x.m[2][1])*(y.m[1][1]+y.m[1][2]);z.m[1][1]=m5+m4-m2+m6;z.m[1][2]=m1+m2;z.m[2][1]=m3+m4;z.m[2][2]=m5+m1-m3-m7;returnz;}publicmatrixMatrixPlus(matrixf,matrixg,intn)/*矩阵加法方法*/{inti,j;matrixh=newmatrix();for(i=1;i<=n;i++)for(j=1;j<=n;j++)h.m[i][j]=f.m[i][j]+g.m[i][j];returnh;}publicmatrixMatrixMinus(matrixf,matrixg,intn)/*矩阵减法方法*/{inti,j;matrixh=newmatrix();for(i=1;i<=n;i++)for(j=1;j<=n;j++)h.m[i][j]=f.m[i][j]-g.m[i][j];returnh;}publicmatrixMatrixMultiply(matrixa,matrixb,intn)/*矩阵乘法方法*/{intk;matrixa11,a12,a21,a22;a11=newmatrix();a12=newmatrix();a21=newmatrix();a22=newmatrix();matrixb11,b12,b21,b22;b11=newmatrix();b12=newmatrix();b21=newmatrix();b22=newmatrix();matrixc11,c12,c21,c22,c;c11=newmatrix();c12=newmatrix();c21=newmatrix();c22=newmatrix();c=newmatrix();matrixm1,m2,m3,m4,m5,m6,m7;k=n;if(k==2){c=AdhocMatrixMultiply(a,b);returnc;}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(MatrixMinus(b12,b22,n/2),a11,k);m2=MatrixMultiply(b22,MatrixPlus(a11,a12,k),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矩阵returnc;}}publicstaticvoidmain(String[]args)throwsIOException{jzcfinstance=newjzcf();inti,j,num;matrixA,B,C;A=newmatrix();B=newmatrix();C=newmatrix();Scannerin=newScanner(System.in);System.out.print("输入矩阵的阶数:");num=in.nextInt();if(instance.judgment(num)==0){System.out.println("输入矩阵A:");for(i=1;i<=num;i++)for(j=1;j<=num;j++)A.m[i][j]=in.nextInt();System.out.println("输入矩阵B:");for(i=1;i<=num;i++)for(j=1;j<=num;j++)B.m[i][j]=in.nextInt();if(num==1)C.m[1][1]=A.m[1][1]*B.m[1][1];//矩阵阶数为1时的特殊处理elseC=instance.MatrixMultiply(A,B,num);System.out.println("矩阵C为:");for(i=1;i<=num;i++){for(j=1;j<=num;j++)System.out.print(C.m[i][j]+"");System.out.println();}}elseSystem.out.println("输入的阶数不是2的N次方");}}3.合并排序：packagesyy;publicclasshebingpaixu{publicvoidmerge_sort(int[]arrays,intstart,intend){if(start<end){intm=(start+end)/2;merge_sort(arrays,start,m);merge_sort(arrays,m+1,end);combin_arrays(arrays,start,m,end);}}publicvoidcombin_arrays(int[]arrays,intstart,intm,intend){intlength=end-start+1;inttemp[]=newint[length];//用来存放比较的数组，用完复制回到原来的数组inti=start;intj=m+1;intc=0;while(i<=m&&j<=end){if(arrays[i]<arrays[j]){temp[c]=arrays[i];i++;c++;}else{temp[c]=arrays[j];j++;c++;}}while(i<=m){temp[c]=arrays[i];i++;}while(j<=end){temp[c]=arrays[j];j++;}c=0;for(intt=start;t<=end;t++,c++){arrays[t]=temp[c];}snp(arrays);}publicvoidsnp(int[]arrays){for(inti=0;i<arrays.length;i++){System.out.print(arrays[i]+"");}System.out.println();}publicstaticvoidmain(String[]args){hebingpaixum=newhebingpaixu();inta[]={6,4,3,10,7,5};m.merge_sort(a,0,a.length-1);}}快速排序：packagesyy;publicclassQSort{publicstaticvoidmain(String[]args){//TODO自动生成方法存根quicksortqs=newquicksort();intdata[]={14,26,84,65,76,49,53,39};qs.data=data;qs.sort(0,qs.data.length-1);qs.display();}}classquicksort{publicintdata[];privateintpartition(intsortArray