《算法设计与分析教学资料》第三次实验

1、上机实验报告课程名称：算法设计与分析班级：4实验日期：3.14姓名：王鹏飞学号：20117760452指导教师：王志华实验名称：第一:次实验实验序号：3实验成绩：、实验目的及要求1. 二分搜索的递归和非递归实现算法；2 棋盘覆盖的递归实现算法；3 大整数乘法的递归算法；4.strassen矩阵乘法的递归算法5手动画出两个二进制大整数的乘法过程x=1011, y=1101 o二、实验环境windows xp , eclipse3.2三、实验内容1. 二分搜索的递归和非递归实现算法；2. 棋盘覆盖的递归实现算法；3. 大整数乘法的递归算法； 4.strassen矩阵乘法的递归算法5.手动画出两个二

2、进制大整数的乘法过程x=1011, y=1101o四、算法描述及实验步骤1.二分搜索的递归和非递归实现算法； function gcd(x, y, n);beginif(left<=right)int mid=(left+right)/2;if(key=amid) return mid;if(key>amid)return gcd(a,key,mid+1 bright);else return gcd(a,keyjeft.mid-1);elsereturn 1;endfunction ungcd(x, y, n);begin当left小于时 mid=(left+right)/2;

3、if(key=amid) return mid;if(key>amid) left=mid+l;else begin right=mid-1;endreturn 1;2 棋盘覆盖的递归实现算法；考虑：使用分治策略，求解棋盘覆盖问题当k>0时，将2kx2k棋盘分割为4个2k-1x2k-1子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为 了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个l型骨牌覆盖 这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模 的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1x1。产w-1产y产1

4、产y产1产*x产1 (1) 棋盘：可以用一个二维数组boardsizesize表示一个棋盘，其屮，size=2ko 为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；(2) 子棋盘：整个棋盘用二维数组boardsizesize表示，其中的子棋盘由棋 盘左上角的下标tr、tc和棋盘大小s表示；(3) 特殊方格：用boarddrdc表示特殊方格，dr和de是该特殊方格在 二维数组board中的下标；(4) l型骨牌：一个2kx2k的棋盘中有一个特殊方格，所以，用到l型 骨牌的个数为(4k-1)/3,将所有l型骨牌从1开始连续编号，用一个全局变量 t表示。3 大整数乘法的递归算法;

5、function mult(x, y, n); x和y为2个小于2n的整数，返回结果为x和 y的乘积xybegins:=sign(x)*sign(y); s 为 x 和 y 的符号乘积x:=abs(x);y:=abs(y); x和y分别取绝对值if n=l thenif (x=l)and(y=l) then return(s)else return(o)else begina:=x的左边n/2位；b:=x的右边n/2位；c:=y的左边n/2位；d:=y的右边n/2位；ml:=mult(a,c,n/2);m2:=muet(a-b,d-c,n/2);m3:=mult(b,d,n/2);s:二 s*

6、(ml *2n+(m 1 +m2+m3)*2n/2+m3);return(s);end;end;4.strassen矩阵乘法的递归算法至此，我们可以得到完整的strassen算法如下：procedure strassex (n, a, b, c);beg inif n=2 then mateix-multiply(a, b, c)e1se begin将矩阵a和b依(1)式分块;strassen (n/2, all,b12-b22, ml);strassex (n/2, au+a12, b22, m2);strassex(n/2, a21+a22, bl 1, m3);strassex(n/2,

7、 a22, b21-b11, m4);strassen (n/2, au+a22, b11+b22, m5);strassex (n/2, a12-a22, b21+b22, 16);stkassen (n/2, a11-a21, bl 1+1312, m7);a/3 + af4h + 3 7end ;end;matr1x-mult1ply (a, 13, c)是按通常的矩阵乘法计一算oab的子算法。五、调试过程及实验结果1.二分扌!索的递归和非递归实现算法输入8输出 5 6 10 18 19 27 28 29输入18输出3输入10输出 5 9 15 18 24 2531 37 46 49输入

8、24输出4输入3 221|1|2|2|1|0|0|2|3|0|4|0|3|3|4|4|输入2 232|2|3|3|7|7|8|8|2|1|1|3|7|6|6|8|4|1|0|5|9|9|6|10 |4|4|5|5|0|9|10 |10 |12 |12 |13 10|0|17 |18 |18 |12 |11113 113 117 |17 |16 |18 |14| 11| 11| 15| 19| 16| 16| 20|14| 14| 15| 15| 19| 19| 20| 20|六、总结知道如何分治，怎么分，分到什么吋候停止，若算法思路不清晰容易造成死循 环。有时一个分开的步骤没做好，整个答案都会

9、不一样，还需要我们学会查找 错误的方法。可以将程序分段测试，一个环节一个环节的测试，不能想着一气 呵成。七.附录（源程序清单）1.二分搜索算法：import java.util.scanner;public class binarysearch public static int ungcd(int a,int key,int leftjnt right) while(left<=right)int mid=(left+right)/2; if(key=amid) return mid;if(key>amid)left=mid+1;elseright=mid-1;return -1

10、;public static int gcd(int a,int keyjnt left,int right) if(left<=right)int mid=(left+right)/2;if(key=amid)return mid;if(key>amid)return gcd(a,key,mid+1 bright);else return gcd(a9keyjeft,mid-1);elsereturn -1;public static void main(stringfl args) scanner sc=new scanner(system.in);try system.out

11、.printlnc本程序是二分搜索测试程序”); system.out.println(n程序自动生成一个长度为n的数组请输入n (n必 须为正整数)int n=sc.nextlnt();if(n<=0)system.out.print(n请不要输入负数”);system.exit(o);system.out.printc'自动生成数组如下：");int a=new intn;a0=(int)(math .random() * 10+1);system.out.print(a04-n ”)；for(int i=l;i<n;i+)ai=(int)(math.rand

12、om()* 10+ l)+ai-l ;system.out.print(ai+"");system.out.println(hn请输入要查找的数k (k必须为正整数)；”)； int key=sc.nextlnt();system.out.println("递归查找的结果为："+gcd(a,key,o,n-l); system.out.println("非递归查找的结果为：n+ungcd(a,key,0,n-1); catch (exception e) system.out.printlnc'非法输入数据！ ”)；2 棋盘覆盖算法：i

13、mport java.util.scanner;public class chess private int board;/用来表示棋盘private int boardsize;/表示棋盘的大小为2的多少次方 private int dr,de;/棋盘中特殊方格的位置(行号、列号) private int tile;/骨牌标号public chess()board=new intf lf 1;dr=0;dc=0;boardsize=0;public chess(int tcjnt s)int n;n=(int) math.pow(2, s);if (n<=tr | n&l

14、t;=tc)system.out.println('初始化参数错误! ”);elseboard=new intnn;dr=tr;dc=tc;boardsize=s;函数参数说明：/tr：棋盘左上角方格的行号；/tc：棋盘左上角方格的列号；/dr：特殊方格所在的行号；/de：特殊方格所在的列号；/size： 2俅,棋盘规格为2ak*2akopublic void chessboard(int tr, int tc, int dr, int de, int size) if (size=l) return;int t=tile+, s = size/2; / t:l 型骨牌号,s 分割棋盘

15、/覆盖左上角子棋盘if(dr<tr+s&&dc<tc+s)/特殊方格在此棋盘中 chessboard(tr, tc, dr, de, s);else/此棋盘中无特殊方格则用t号l型骨牌覆盖右下角 boardtr+s-1 tc+s-1 = t;/ 覆盖其余方格 chessboard(tr, tc, tr+s-1, tc+s-1, s);/覆盖右上角子棋盘if (dr<tr+s&&dc> 二 tc+s)/特殊方格在此棋盘中 chessboard(tr, tc+s, dr, de, s);else/无特殊方格，用号骨牌覆盖左下角boardtr

16、+ s - ltc + s = t;chessboard(tr, tc+s, tr+s-1, tc+s, s);/覆盖左下角子棋盘if (dr>=tr+s&&dc<tc+s) chessboard(tr+s, tc, dr, de, s);else boardtr+s tc+s-1 =t;chessboard(tr+s, tc, tr+s, tc+s-1, s);/覆盖右下角子棋盘讦(dr>=tr+s&&dc>=tc+s)特殊方格在此棋盘中 chessboard(tr+s, tc+s, dr, de, s);else board tr +

17、 stc + s = t; chessboard(tr+s, tc+s, tr+s, tc+s, s);public void print()for(int i=0;i<math.pow(2, this.boardsize);i+)for(int j=0;j<math.pow(2, this.boardsize);j+) system.out.print(string.format(n%3dr', this.boardfifj); system.out.println();1public static void main(string args)try scanner sc

18、=new scanner(system.in); system, out. println(”此程序为棋盘覆盖测试程序”); system.out.println(nin输入行号 x(x 为正整数):”); int x=sc.nextlnt();system.out.println(n请输入行号y(y为正整数)”)；int y=sc.nextlnt();system.out.println(nih输入棋盘大小k大小为2的k次方(k为正整 数门；int k=sc.nextlnt();if(x>=0&&y>=0&&k> 二 1) chess cl=

19、 new chess(x,y,k); cl.chessboard(0, 0, cl.dc, cl.dr, (int)math.pow(2,c 1 .boardsize); cl.print();else systemoutprintlnc输入棋盘参数错误”); catch (exception e) system.out.printlnc*非法输入数据！ ”)；3 大整数乘法算法： import java.util.scanner;public class multiply static long pow(int n) int s = 10;for (int i = 1; i < n;

20、i+) s = s * 10;return s;static int num(long x) int s = 0;while (x !=0) x = x / 10;s+;return s;static long multiply(long a, long b) int n = num(a);long m;long sign=(long)(mathesignum(a)*math.signum(b);long result =0;a=math.abs(a);b=math.abs(b);long a, b, c, d;if(n>l)m = pow(n / 2);a = a / m;b = a

21、% m;c = b / m;d = b % m;result += multiply(a, c) * m * m + (multiply(a, d) + multiply(b, c) * m+ multiply(b, d); else return a * b;return result*sign;public static void main(stringl args) scanner sc=new scanner(systemjn);try system.out.println("这是一个用递归分治算法解决大整数乘积的测试 程序”)；system.out.println(n请输入

22、整数 x 的值：”);long x=sc.nextlong();system.out.println(hiw输入整数 y 的值：”)；long y=sc.nextlong();system.out.printin("所得大整数乘积为："+multiply(x, y); catch (exception e) system.out.println("非法输入数据! ”)；4.strassen矩阵乘法算法：import java.util.scanner;public class strassen private static int a;private static

23、 int b;private static int c;public strassen(int n) a=new int nn;b=new int nn;c=new int nn;public static int add(int a, int b)int c=new inta.lengthao.length;for(int i = 0; i < a.length; i+) for(int j = 0; j < ai.length; j+) ciu = aij + bij;return c;public static int sub(int a, int b) int c=new

24、inta.lengthao.length;for(int i = 0; i < a.length; i+) for(intj = 0;j < ai.length; j+) cij = aij-birj;return c;public static void gcd(int n,int a,int b|,int c|)if(n=l)c00=a00*b00;if(n=2)for (int i = 0; i v n; i+) for (int k = 0; k < n; k+) int temp=0;for (intj=o;j<n;j+) temp=aij*bjk; cik+

25、=temp;elseintfml=new intn/2n/2;intm2=new intn/2n/2;intm3=new intn/2n/2;intm4=new intn/2n/2;intm5=new intn/2n/2; intm6=new intn/21n/2; intm7=new intn/2n/2;intal l=new intn/2n/2; intal2=new intn/2n/2; intnfa21=new intfn/2fn/21; inta22=new intn/2n/2;intbl l=new intn/2n/2;intbl2=new intn/2n/2;intb21=new

26、 intn/2n/2;intb22=new intn/2n/2;intjcll=new intn/2n/2;intcl2=new intn/2n/2;intc21=new intn/2n/2;intffc22=new intfn/2fn/21;for(int i = 0; i < a.length/2; i+) for(int j = 0; j < a.length/2; j+) al2i j=ai j+a.length/2;a21ij=ai+a.length/2j ;a22ij=ai+a.length/2 j+a.length/2; bllij=biu;bl2iul=bi|j+a

27、.length； b21i(j=bi+ajength/2j;b22ij=bi+a.length/2fj+a.length/2;gcd(n/2,a 11 ,sub(b 12,b22),m 1); gcd(n/2,add(a 11,al 2),b22,m2); gcd(n/2,add(a21 ,a22),b 11 ,m3); gcd(n/2,a22,sub(b21 ,b 11 ),m4); gcd(n/2,add(al l,a22),add(bl i,b22),m5); gcd(n/2,sub(a 12,a22),add(b21 ,b22),m6); gcd(n/2,sub(a 11 ,a2 l)

28、,add(b 11,bl 2),m7);int tempjj=new intn/2n/2; temp=add(sub(add(m5,m4),m2),m6); for (int i = 0; i v tempjength; i+) for (int j = 0; j < temp length; j+) cllij=tempij;temp=add(m l,m2);for (int i = 0; i < temp.length; i+) for (int j = 0; j < temp length; j+) cl2ij=tempi|j;temp=add(m3,m4);for (

29、int i = 0; i < temp.length; i+) for (int j = 0; i < temp length; j+) c21ij=tempiu；temp=sub(add(m5,m i),add(m3,m7);for (int i = 0; i < temp length; i+) for (int j = 0; j < tempjength; j+) c22ij=tempiuj;for(int i = 0; i < cength/2; i+) for(int j = 0; j < c.length/2; j+) cij=clliu;cij

30、+c.length /2=cl2ij;ci+c.length/2 fj =c2 li|j;c|i+c.length/2j+c.length/2=c22ij;public static void random(int r)for (int i = 0; i v 匸length; i+) for (int j = 0; j < rfoj.length; j+) rij=(int)(math.random()* 10+1);public static void show(int s)for (int i = 0; i < sength; i+) for (int j = 0; j < s0.length; j+) system.out.print(sij+h ”)；system.out.println();public stat