《实验1 递归与分治策略》由会员分享，可在线阅读，更多相关《实验1 递归与分治策略（9页珍藏版）》请在金锄头文库上搜索。
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,c
2、har A,char 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 S
3、trassen()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.length;
5、 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 NUMBERNUMB
6、ER;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 i
7、nt 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(A,
8、 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, te
9、mp, 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(B1
10、1, B12, 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.
11、length/2=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;priva
12、te static int 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
13、+1+i; array1l1 = 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);mergeSor
14、t(a, poi + 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 = aq;int i = p-1;for(int j = p; j=q - 1; j+)if(aj = key)i
