Recursion and divide and conquer

1. The concept of recursion

• The algorithm that directly or indirectly calls itself is called recursive algorithm
• A function defined by the function itself is called a recursive function

1.1 Factorial function

public class FactorialDemo {
    
	public static void main(String[] args) {
    
		System.out.println("1!="+factorial(1));
		System.out.println("2!="+factorial(2));
		System.out.println("3!="+factorial(3));
		System.out.println("4!="+factorial(4));
	}
	public static int factorial(int n) {
    
		
		if(n==0)
			return 1;
		return n*factorial(n-1);
		
	}

}

1.2 Fibonacci The sequence

public class Fibonacci {
    
	/** * * f(n)=1 n=0,1 * f(n)=f(n-1)+f(n-2) n>1 */
	public static void main(String[] args) {
    
		
		System.out.println("f(0)="+fibonacci(0));
		System.out.println("f(1)="+fibonacci(1));
		System.out.println("f(2)="+fibonacci(2));
		System.out.println("f(3)="+fibonacci(3));
		
	}
	
	public static int fibonacci(int n) {
    
		
		if(n==0||n==1)
			return 1;
		return fibonacci(n-1)+fibonacci(n-2);
		
	}

}

1.3 Full Permutation

public class FullPermutation {
    
	public static void main(String[] args) {
    
		int list[]= {
    1,2,3};
	    System.out.println("[1 2 3] The whole arrangement ：");
		perm(list, 0, list.length-1);
	}
	public static void perm(int list[],int k,int m) {
    
		
		if(k==m)// Traverse to the last element 
		{
     
			for(int i=0;i<=m;i++)
				System.out.print(list[i]);
			
			System.out.println();
		}
		else {
    
			for(int i=k;i<=m;i++) 
			{
     
				swap(list, i, k);// Put the current element list[k] Fixed to i Location 
				perm(list, k+1, m);
				swap(list, i, k);// Restore elements list[k] The location of 
				
			}
		}
		
	}
	public static void swap(int list[],int a,int b) {
    
		
		int temp=list[a];
		list[a]=list[b];
		list[b]=temp;
		
	}

}

1.4 Integer partition problem

Put a positive integer n Expressed as the sum of a series of positive integers ,n=n1+n2+n3+…+n${}_k$
n1>=n2>=n3…>=n${}_k$
p(n) Indicates the number of species divided

(1) When n=1 when , Regardless of m What is the value of （m>0), There is only one division, that is {1};

(2) When m=1 when , Regardless of n What is the value of , There is only one division, that is n individual 1,{1,1,1,…,1};

(3) When n=m when , According to whether the division includes n, It can be divided into two situations ：

  (a) The partition contains n The situation of , There is only one, that is {n};

  (b) The partition does not contain n The situation of , At this time, the largest number in the division must also be higher than n Small , namely n All of the (n-1) Divide .  therefore  q(n,n) =1 + q(n,n-1);

(4) When n<m when , Because there can be no negative numbers in the partition , So it's equivalent to q(n,n);

(5) but n>m when , According to whether the division contains the maximum value m, It can be divided into two situations ：

   (a) The partition contains m The situation of , namely {m, {x1,x2,...xi}},  among {x1,x2,... xi}  And for n-m, So this case is q(n-m,m)

   (b) The partition does not contain m The situation of , Then all values in the partition are better than m Small , namely n Of (m-1) Divide , The number is q(n,m-1);

   therefore  q(n, m) = q(n-m, m)+q(n,m-1);

Reference article

public class IntegerPartition {
    
	static int num[]=new int[256];// Save the partition results 
	static int ans=0;// Save the number of divisions 
	public static void main(String[] args) {
    
		System.out.println("p(6)="+q(6, 6));
		dfs(0, 0, 6,6);
		System.out.println("p(6)="+ans);
	}
	
	public static int q(int n,int m) {
    
		
		if(n<1||m<1)
			return 0;
		if(n==1||m==1)
			return 1;
		if(n<m)
			return q(n, n);
		if(n==m)
			return 1+q(n, m-1);
		return q(n, m-1)+q(n-m, m);
		
	}
	/** * * @param sum  The sum of the current traversal  * @param depth  The number of elements in the current partition  * @param max  The current maximum remaining  * @param n  Value to be divided n */
	public static void dfs(int sum,int depth,int max,int n) {
    
		
		if(sum==n)
		{
     
			System.out.print(num[0]);
			for(int i=1;i<depth;i++)
				System.out.print("+"+num[i]);
			System.out.println();
			ans++;
		}
		else if(sum<n)
		{
     
			for(int i=max;i>=1;i--)
			{
     
				num[depth]=i;
				dfs(sum+i, depth+1, i, n);
			}
		}
		
	}

}

1.5 The hanotta problem

public class HanoiDemo {
    
	public static void main(String[] args) {
    
		
		hanoi(3, 'a', 'b', 'c');
		
	}
	
	public static void hanoi(int n,char a,char b,char c) {
    
		
		if(n>0)
		{
     
			hanoi(n-1, a, c, b);// take a above n-1 A disk from a-->c  With b As an aid 
			move(n,a,b);// Put the disc n from a-->b(a、b In the recursion process, it does not necessarily represent columns a He Zhu b)
			hanoi(n-1, c, b, a);// take c above n-1 A disk from c-->b  With a As an aid 
		}
		
	}
	
	public static void move(int n,char a,char b) {
    
		
		System.out.println(" The disk "+n+" from "+a+" to "+b);// Simulate the moving process 
	}

}

2. The basic idea of divide and rule

• The basic idea of divide and conquer is to divide a scale into n The problem of k A smaller sub problem , These subproblems are independent of each other and the same as the original problem

2.1 Binary search technology

The basic idea of binary search algorithm waiting is to n The elements are divided into roughly the same number of halves , take a[n/2] And x Compare , If x=a[n/2] Then call x Algorithm was terminated ; If x<a[n/2], Then just in the array a The left half of the search continues x; If x>a[n/2], Then just in the array a Continue searching in the right half of x

2.1.1 A binary search algorithm without boundary

public static int binary_search(int arr[],int target) {
    
		
		int left=0,right=arr.length-1;
		while(left<=right)
		{
     
			int mid=left+(right-left)/2;
			if(arr[mid]==target)
				return mid;
			else if(arr[mid]>target)
				right=mid-1;
			else if(arr[mid]<target)
				left=mid+1;
		}
		return -1;
		
	}

2.1.2 A binary search algorithm for finding the left boundary

public static int binary_search_leftBound(int arr[],int target) {
    
		int left=0,right=arr.length;// [left,right)  Left closed right away 
		while(left<right)
		{
     
			int mid=left+(right-left)/2;
			if(arr[mid]==target)
				right=mid;
			else if(arr[mid]>target)
				right=mid;//[left,mid)<==>[left,mid-1]
			else if(arr[mid]<target)
				left=mid+1;//[mid+1,right)
		}
		
	    return arr[left]==target?left:-1;
	}

2.1.3 A binary search algorithm for finding the right boundary

public static int binary_search_rightBound(int arr[],int target) {
    
		int left=0,right=arr.length;// [left,right)  Left closed right away 
		while(left<right)
		{
     
			int mid=left+(right-left)/2;
			if(arr[mid]==target)
				left=mid+1;
			else if(arr[mid]>target)
				right=mid;
			else if(arr[mid]<target)
				left=mid+1;
		}
		
		  return arr[left-1]==target?left-1:-1;
	}

Complete code ：

public class BinarySearch {
    
	
	public static void main(String[] args) {
    
		int arr[]= {
    1,2,3,3,3,4,5,6};
		System.out.println(binary_search(arr, 3));
		System.out.println(binary_search_leftBound(arr, 3));
		System.out.println(binary_search_rightBound(arr, 3));
		
	}
	public static int binary_search(int arr[],int target) {
    
		
		int left=0,right=arr.length-1;
		while(left<=right)
		{
     
			int mid=left+(right-left)/2;
			if(arr[mid]==target)
				return mid;
			else if(arr[mid]>target)
				right=mid-1;
			else if(arr[mid]<target)
				left=mid+1;
		}
		return -1;
		
	}
	public static int binary_search_leftBound(int arr[],int target) {
    
		int left=0,right=arr.length;// [left,right)  Left closed right away 
		while(left<right)
		{
     
			int mid=left+(right-left)/2;
			if(arr[mid]==target)
				right=mid;
			else if(arr[mid]>target)
				right=mid;//[left,mid)<==>[left,mid-1]
			else if(arr[mid]<target)
				left=mid+1;//[mid+1,right)
		}
		
	    return arr[left]==target?left:-1;
	}
	
	public static int binary_search_rightBound(int arr[],int target) {
    
		int left=0,right=arr.length;// [left,right)  Left closed right away 
		while(left<right)
		{
     
			int mid=left+(right-left)/2;
			if(arr[mid]==target)
				left=mid+1;
			else if(arr[mid]>target)
				right=mid;
			else if(arr[mid]<target)
				left=mid+1;
		}
		
		  return arr[left-1]==target?left-1:-1;
	}
	

}

2.2 Chessboard coverage

In a 2${}^k$$\times$ 2${}^k$ In a chessboard composed of squares , Just one square is different from the others , In the chessboard coverage problem , There are four L Type dominoes cover the chessboard , And any two L Type dominoes cannot overlap

The special square must be in 4 One of the smaller chessboards , rest 3 There are no special squares in the sub chessboard , You can use a L A-shaped dominoes cover this 3 The meeting place of a smaller chessboard , To turn the problem into 4 A smaller scale chessboard coverage problem

If there is no special square in a sub chessboard , Follow these rules ：

• The checkerboard in the upper left corner fills the square in the lower right corner
• The checkerboard in the upper right corner fills the square in the lower left corner
• The checkerboard in the lower left corner fills the square in the upper right corner
• The checkerboard in the lower right corner fills the square in the upper left corner

package chapter2;

public class ChessboardCoverage {
    
	static int title=1;//L The initial number of type a dominoes is 2  It is different from the special square mark in the chessboard 1
	public static void main(String[] args) {
    
		int board[][]= {
        {
    0,1,0,0},
							{
    0,0,0,0},
							{
    0,0,0,0},
							{
    0,0,0,0}
				       };
		
		chessBoard(board, 0, 0, 0, 1,4);
		
		for(int i=0;i<board.length;i++)
		{
     
			for(int j=0;j<board[0].length;j++)
				System.out.print(board[i][j]+" ");
			System.out.println();
		}
				
}
	/** * * @param board  The board  * @param tr  The line number of the square in the upper left corner of the chessboard  * @param tc  The column number of the square in the upper left corner of the chessboard  * @param dr  The line number of the special box  * @param dc  The column number of the special box  * @param size  The specification of the chessboard is 2^k*2^k */
	 
	public static void chessBoard(int board[][],int tr,int tc,int dr,int dc,int size) {
    
		  if(size==1)// The chessboard is divided into only one grid 
			  return;
		  
		  int t=++title;//L The type of dominoes 
		  int sz=size/2;// Split the chessboard 
		  
		  // Cover the upper left checkerboard 
		  if(dr<tr+sz&&dc<tc+sz)// This chessboard has a special square 
			  chessBoard(board, tr, tc, dr, dc, sz);//(tr,tc) It is the starting point of the chessboard in the upper left corner （ The point in the upper left corner ）
		  else {
    // There is no special square in this chessboard 
			board[tr+sz-1][tc+sz-1]=t;// use t Number L Type dominoes cover the lower right corner   The upper left sub chessboard fills the lower right corner 
			chessBoard(board, tr, tc, tr+sz-1, tc+sz-1, sz);// Cover the rest of the squares  （tr+sz-1, tc+sz-1） It is filled in in the previous step 
			
		}
		  
		 // Cover the upper right checkerboard 
		  if(dr<tr+sz&&dc>=tc+sz)
			  chessBoard(board, tr, tc+sz, dr, dc, sz);//(tr,tc+sz) It is the starting point of the checkerboard in the upper right corner （ The point in the upper left corner ）
		  else {
    // There is no special square in this chessboard 
			board[tr+sz-1][tc+sz]=t;// use t Number L Type dominoes cover the lower left corner   The upper right sub chessboard fills the lower left corner 
			chessBoard(board, tr, tc+sz, tr+sz-1, tc+sz, sz);// Cover the rest of the squares 
		}
		  
		  
		// Cover the chessboard in the lower left corner 
		  if(dr>=tr+sz&&dc<tc+sz)
			  chessBoard(board, tr+sz, tc, dr, dc, sz);//(tr,tc) Is the starting point of the chess board in the lower right corner （ The point in the upper left corner ）
		  else {
    // There is no special square in this chessboard 
			board[tr+sz][tc+sz-1]=t;// use t Number L The dominoes cover the upper right corner   The lower left chessboard fills the upper right corner 
			chessBoard(board, tr+sz, tc, tr+sz, tc+sz-1, sz);// Cover the rest of the squares 
		}
		  
		// Cover the lower right checkerboard 
		  if(dr>=tr+sz&&dc>=tc+sz)
			  chessBoard(board, tr+sz, tc+sz, dr, dc, sz);//(tr,tc) Is the starting point of the chess board in the lower right corner （ The point in the upper left corner ）
		  else {
    // There is no special square in this chessboard 
			board[tr+sz][tc+sz]=t;// use t Number L The dominoes cover the upper right corner   The lower right chessboard fills the upper left corner 
			chessBoard(board, tr+sz, tc+sz, tr+sz, tc+sz, sz);// Cover the rest of the squares 
		}
		  
		
	}
	 
}



//O(4^k)

2.3 Merge sort

import java.util.Arrays;

public class MergeSortDemo {
    
	public static void main(String[] args) {
    
		int arr[]= {
    1,3,2,6,5,7,9,8,4};
		int temp[]=new int[arr.length];
		mergeSort(arr, temp, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	
	public static void mergeSort(int arr[],int temp[],int lo,int hi) {
    
		
		if(lo>=hi)
			return;
		
		int mid=lo+(hi-lo)/2;
		mergeSort(arr, temp, lo, mid);
		mergeSort(arr, temp, mid+1, hi);
		merge(arr, temp, lo, mid, hi);
		
	}
	
	public  static void merge(int arr[],int temp[],int lo,int mid,int hi) {
    
		
		int i=lo;
		int j=mid+1;
		int t=0;
		while(i<=mid&&j<=hi)
		{
     
			if(arr[i]<=arr[j])
				temp[t++]=arr[i++];
			else
				temp[t++]=arr[j++];
				
		}
		while(i<=mid)
			temp[t++]=arr[i++];
		
		while(j<=hi)
			temp[t++]=arr[j++];
		
		t=0;
	    i=lo;
		while(i<=hi)
			arr[i++]=temp[t++];
			
		
	}

}

2.4 Quick sort

import java.util.Arrays;
import java.util.Random;

public class QuickSortDemo {
    
	public static void main(String[] args) {
    
		int arr[]= {
    1,3,2,6,5,7,9,8,4};
		quickSort(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	
	public static void quickSort(int arr[],int lo,int hi) {
    
		
		if(lo>=hi)
			return;
		int j=randomizedPartion(arr, lo, hi);
		quickSort(arr, lo,j-1);
		quickSort(arr, j+1, hi);
		
	  
		
	}
	
	public static int partion(int arr[],int lo,int hi) {
    
		
		int i=lo;
		int j=hi+1;
		int v=arr[lo];
		
		while(true)
		{
     
			while(arr[++i]<v)
				if(i==hi)
					break;
			
			while(arr[--j]>v)
				if(j==lo)
					break;
			
			if(i>=j)
				break;
			
			swap(arr, i, j);
		}
		swap(arr, lo, j);
		return j;
		
	}
	public static int randomizedPartion(int arr[],int lo,int hi) {
    // Divide randomly 
		
		int i=new Random().nextInt(hi-lo+1)+lo;//[lo,hi] Random integer between 
		swap(arr, i, lo);// Put the element corresponding to the generated random number in the first place 
		return partion(arr, lo, hi);
		
		
		
	}
	public static void swap(int arr[],int a,int b) {
    
		  int temp=arr[a];
		  arr[a]=arr[b];
		  arr[b]=temp;
	}

}

2.5 Round robin problem

public class RoundRobinSchedule {
    
	
	public static void main(String[] args) {
    
		  int a[][]=new int[9][9];
		  table(3,a);
		  for(int i=1;i<=8;i++)
		  {
     
			  for(int j=1;j<=8;j++)
				  System.out.print(a[i][j]+" ");
			  System.out.println();
		  }
	}
	
	public static void table(int k,int a[][]) {
    
		int n=1;
		for(int i=1;i<=k;i++)
			n*=2;//n Indicates the number of players  2^k
		
		for(int i=1;i<=n;i++)
			a[1][i]=i;// Initialize the first row of the table   That is to say 1 The competition schedule of contestant No 
		
		int m=1;//(m+1,m+1) Is the starting position of each round of replication 
		for(int s=1;s<=k;s++)// Number of divisions  k=3 when  8-4->2
		{
     
			n/=2;// Division of players 
			for(int t=1;t<=n;t++)// The first time you need to copy 4 Time   The second time you need to copy 2 Time   The third time you need to copy 1 Time ( Each copy involves two assignment operations )
			{
     
				for(int i=m+1;i<=2*m;i++)// The control line 
				{
     
					for(int j=m+1;j<=2*m;j++)// Control the column 
					{
       
						
						a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m];// Copy the values in the upper left corner to the lower right corner 
						a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2];// Copy the values in the upper right corner to the lower left corner 
					}
					
				}
				
			}
			m*=2;
		}
	}

}