实验1 递归与分治策略.doc

南京信息工程大学 算法设计与分析 实验(实习)报告实验(实习)名称 实验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,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 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 : 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; 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 NUMBERNUMBER;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 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(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, 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, 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.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;private 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+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);mergeSort(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 = 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