实验递归与分治策略

1、南京信息工程大学 算法设计与分析 实验(实习)报告实验(实习)名称 实验1 递归与分治策略 实验(实习)日期 2016.10 得分 指导老师 宣文霞 系 计算机 专业 网络工程 班级 2 姓名 刘信言 学号 20142346074 1. 实验目的1) hanoi塔问题2) strassen矩阵乘法3) 合并排序（merge sort）4) 快速排序（quick sort）2. 实验内容及分析设计过程：1）hanoi塔问题import java.util.scanner;public class hanoi public static void hanoi(int number,char a,c

2、har b,char c) if(number=1) system.out.println(a+-+c); return; hanoi(number-1,a,c,b); hanoi(1,a,b,c); hanoi(number-1,b,a,c); public static void main(string args) scanner input =new scanner(system.in); int n= input.nextint(); hanoi(n,a,b,c); 2）strassen矩阵乘法import java.util.*;public class strassenpublic

3、 strassen()a = new intnumbernumber;b = new intnumbernumber;c = new intnumbernumber;public void input(int a)scanner scanner = new scanner(system.in);for(int i = 0; i a.length; i+) for(int j = 0; j ai.length; j+) aij = scanner.nextint();public void output(int resault)for(int b : resault) for(int temp

4、: b) system.out.print(temp + );system.out.println();public void mul(int first, int second, int resault)for(int i = 0; i 2; +i) for(int j = 0; j 2; +j) resaultij = 0;for(int k = 0; k 2; +k) resaultij += firstik * secondkj;public void add(int first, int second, int resault)for(int i = 0; i first.lengt

5、h; i+) for(int j = 0; j firsti.length; j+) resaultij = firstij + secondij;public void sub(int first, int second, int resault)for(int i = 0; i first.length; i+) for(int j = 0; j firsti.length; j+) resaultij = firstij - secondij;public void strassen(int a, int b, int c)/定义一些中间变量int m1=new int numbernu

6、mber;int m2=new int numbernumber;int m3=new int numbernumber;int m4=new int numbernumber;int m5=new int numbernumber;int m6=new int numbernumber;int m7=new int numbernumber;int c11=new int numbernumber;int c12=new int numbernumber;int c21=new int numbernumber;int c22=new int numbernumber;int a11=new

7、 int numbernumber;int a12=new int numbernumber;int a21=new int numbernumber;int a22=new int numbernumber;int b11=new int numbernumber;int b12=new int numbernumber;int b21=new int numbernumber;int b22=new int numbernumber;int temp=new int numbernumber;int temp1=new int numbernumber;if(a.length=2)mul(

8、a, b, c);else/首先将矩阵a，b 分为4块for(int i = 0; i a.length/2; i+) for(int j = 0; j a.length/2; j+) a11ij=aij;a12ij=aij+a.length/2;a21ij=ai+a.length/2j;a22ij=ai+a.length/2j+a.length/2;b11ij=bij;b12ij=bij+a.length/2;b21ij=bi+a.length/2j;b22ij=bi+a.length/2j+a.length/2;/计算m1sub(b12, b22, temp);mul(a11, temp,

9、 m1);/计算m2add(a11, a12, temp);mul(temp, b22, m2);/计算m3add(a21, a22, temp);mul(temp, b11, m3);/m4sub(b21, b11, temp);mul(a22, temp, m4);/m5add(a11, a22, temp1);add(b11, b22, temp);mul(temp1, temp, m5);/m6sub(a12, a22, temp1);add(b21, b22, temp);mul(temp1, temp, m6);/m7sub(a11, a21, temp1);add(b11, b1

10、2, temp);mul(temp1, temp, m7);/计算c11add(m5, m4, temp1);sub(temp1, m2, temp);add(temp, m6, c11);/计算c12add(m1, m2, c12);/c21add(m3, m4, c21);/c22add(m5, m1, temp1);sub(temp1, m3, temp);sub(temp, m7, c22);/结果送回c中for(int i = 0; i c.length/2; i+) for(int j = 0; j c.length/2; j+) cij=c11ij;cij+c.length/2=

11、c12ij;ci+c.length/2j=c21ij;ci+c.length/2j+c.length/2=c22ij;public static void main(string args)strassen demo=new strassen();system.out.println(输入矩阵a);demo.input(a);system.out.println(输入矩阵b);demo.input(b);demo.strassen(a, b, c);demo.output(c);private static int a;private static int b;private static i

12、nt c;private final static int number = 4;3）合并排序（merge sort）public class mergesort2 public static void merge(int a, int p, int q, int r)int l1 = q-p+1;int l2 = r-q;int array1 = new intl1 + 1;int array2 = new intl2 + 1;for(int i = 0; il1; i+)array1i = ap+i;for(int i = 0; il2; i+)array2i= aq+1+i; array

13、1l1 = integer.max_value;array2l2 = integer.max_value;int i = 0;int j = 0;for(int k = p; k=r; k+)if(array1i = array2j )ap+= array1i;i+;elseap+= array2j;j+;public static void mergesort(int a, int low, int high)if(low = high)return;elseint poi = (low + high)/2;mergesort(a, low, poi);mergesort(a, poi +

14、1, high);merge(a, low, poi, high);public static void main(string args) int array = 1,3,6,4,6,4,8,3,8,3,0;mergesort(array, 0, array.length - 1);for(int i = 0; iarray.length; i+)system.out.print(arrayi + );4）快速排序（quick sort）public class quicksort public static int partition(inta, int p, int q)int key

15、= aq;int i = p-1;for(int j = p; j=q - 1; j+)if(aj = key)i = i + 1;int temp = ai;ai= aj;aj= temp; aq = ai+1;/这句话漏掉了ai+1 = key;return i+1;public static void quicksort(int a, int p, int q)if(pq)int poi = partition(a, p, q);quicksort(a, p, poi -1 );quicksort(a, poi + 1, q);public static void main(string args) int a= 3,5,2,4,6,1,9,8,7,4;quicksort(a, 0, a.length - 1);for(int i = 0; ia.length; i+)system.out.pri