算法學習（二）分治遞歸

文章目錄

• 二、分治與遞歸
• • 1、遞歸
  • • 1.1、遞歸的思想
    • 1.2、選擇排序
    • 1.3、生成排列
    • 1.4、如何求解遞歸方程（圖解）
  • 2、分治
  • • 2.1、分治的思想
    • 2.2、什麼時候可以使用分治（一般符合4個條件）
    • 2.3、簡單樣例
    • • 2.3.1、二分搜尋
      • 2.3.2、快速排序
      • 2.3.3、歸并排序
    • 2.4、進階樣例
    • • 2.4.1、覆寫殘缺棋盤
      • 2.4.2、大整數乘法（n位）
      • 2.4.3、Strassen矩陣乘法實作

二、分治與遞歸

1、遞歸

1.1、遞歸的思想

遞歸：一個函數自己調用自己的過程我們稱為遞歸。

遞歸是計算機、數學、運籌等領域經常使用給的最強大的解決問題辦法的方法之一，它用一種簡單的方式來解決那些用其他方法解決可能挺複雜的問題。而且有些問題利用遞歸來解決可能簡單易于了解。

**基本思想：**把一個問題劃分為一個或者多個規模更小子問題，用相同的辦法來解決更小規模的子問題。

遞歸算法設計的基本步驟：

• 問題的初始條件（

  遞歸結束的出口條件

  ）。當問題規模小到一定程度能夠直接求解
• 設計一個政策，将一個問題劃分為一個或者

  多個一步步接近遞歸出口的相似的規模更小的子問題。

• 将所解決的各個小問題的解組合得到原問題的解。

如果無法保證遞歸有出口，則遞歸無法結束導緻記憶體耗盡。

經典問題——漢諾塔問題

我們如果按照正常思維想，當問題規模變大，那将是無法想象的難。

按照遞歸的思想：

• 問題是：

  将n個盤中從A移動到C

  ，需要先将n-1個盤借助C移動到B盤，剩下的最大的那個盤中直接移動到C槽。
• 子問題：

  将n-1個盤從B移動到C

  ，需要将n-1個盤子上面的n-2個借助C移動到A盤，剩下的最大的盤子直接從B移動到C
• 當要移動的盤子剩下1個直接移動即可。

void hanoi(int n,char A,char B,char C){//第一個位置表示n個盤的位置，第二個位置是輔助柱，第三個盤是目的盤
	//問題：n個盤從A移動到C 
	if(n==1){//出口條件 
		printf("%c ---> %c\n",A,C);
		return; 
	} 
	else//子問題 
		hanoi(n-1,A,C,B) ;//n個盤從A移動到C--先将n-1個盤借助C移動到B 
		printf("%c ---> %c\n",A,C);//再将剩下的一個盤中從A移動到C  
		hanoi(n-1,B,A,C);//最後将n-1個盤從B移動到C  	
} 
           

1.2、選擇排序

選擇排序：每次尋找數列中的最小元素（或者最大元素）排在

已經排好序的數字（開始時為空）後面

，最後完成排序。

很明顯：n個元素先找到最小的元素，排序。然後再在剩下的n-1個元素裡面先找到最小的元素，排序。依此類推。當剩下的元素隻剩下1個，則直接排序。

1.3、生成排列

給定一個數字n（正整數）,如何生成從0到n的全排列序列？（

n!

）如n=3

• 1 2 3
• 1 3 2
• 2 1 3
• 2 3 1
• 3 1 2

• 3 2 1

  6種全排列 ，（3！）=6

  

#include<stdio.h>
void swap(int a[],int i,int j){
	int temp; 
	temp = a[i];
	a[i]=a[j];
	a[j]=temp;
} 
void display(int a[],int n){
	for(int i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	printf("\n"); 
}
void getN(int a[],int start,int n){//對n個數全排列,序列升序 
	if(start>=n){//出口條件 
		display(a,n);//列印數組 
		return;
	} 
	for(int i=start;i<n;i++)//這個下标是誰先排在前面 
	{
		swap(a,i,start);//保證每次選到的數都排在前面 
		getN(a,start+1,n);//剩下的n-1個數進行全排列 
		//交換回來
		swap(a,i,start);//保證下一次我們不改變序列 	
	}
} 

int main(){
	int n=5;
	int a[n];
	for(int i=0;i<n;i++){
		a[i]=i+1; 
		printf("%d ",a[i]);
	}
	printf("開始：\n");
	getN(a,0,n);
}
           

1.4、如何求解遞歸方程（圖解）

應用：

2、分治

2.1、分治的思想

2.2、什麼時候可以使用分治（一般符合4個條件）

注意如果子問題不是獨立的，就會包括大量的重複計算，我們就會用到動态規劃裡邊所說的

帶備忘錄的自頂向下

計算。動态規劃和分治法非常類似，都有最優子結構特征，都要能劃分為子問題。動态規劃要求子問題一般是重疊的。

2.3、簡單樣例

2.3.1、二分搜尋

2.3.2、快速排序

快排我們很熟悉了，利用了一個基準值，然後兩個下标（了解為哨兵放哨）。圖中的A[q]就是我們說的基準值了。一般基準值是随機選擇基準政策防止因資料的特征導緻的快排效率不夠好。因為快排的效率取決于劃分的對稱性。

2.3.3、歸并排序

拓展：

2.4、進階樣例

2.4.1、覆寫殘缺棋盤

問題描述：

在一個有2N ×2N個方格組成的棋盤中，有一個方格殘缺（殘缺方格位置随機），要求用如下①~④的三格闆完全覆寫棋盤中為殘缺的方格。

三格闆的編号：4個格子缺少第i格，則為i号

輸入：輸入N、殘缺格子的位置（二維數組裡邊的位置，用值0表示）

輸出填充的情況

例如：下面是一個4×4的棋盤，其中黑色的方格代表殘缺的方格。

使用三格闆覆寫後如下圖

分析問題：

• 問題規模是N，棋盤大小是2N × 2N

下面我們以一組分析如下：

　　　　　　　　　　　　　

邊界情況：當N=0，不需要三格闆；當N=1，需要一個三格闆；

很好的符合了分治的4個特點：

• 問題規模變小時比較容易解決
• 問題可以劃分為若幹個子問題
• 子問題的解合并為問題的解
• 子問題之間獨立

算法設計

package dataStruct;

import java.util.Scanner;
/**
 * 分治法實作殘缺棋盤的覆寫
 */
public class ChessBoard {
    public int tile =1;
    public int[][] board=new int[100][100];//棋盤
    /**
     *
     * @param tr  開始填充的位置 行下标
     * @param tc 開始填充的位置 列下标
     * @param dr 殘缺格子的位置 行下标
     * @param dc 殘缺格子的位置 列下标
     * @param size 棋盤的規模數，2^size
     */
    public void chessBoard(int tr,int tc,int dr,int dc,int size){
            if(size == 1)//問題規模如果是1，不需要填充
                return;
            int t = tile++;//三格闆的編号
            int s = size / 2;//分割棋盤，如8*8——4*4——2*2
            //覆寫左上角棋盤
            if(dr < tr + s && dc < tc + s)
            {//殘缺方格在左上角
                chessBoard(tr, tc, dr, dc, s);
            }
            else
            {//此部分無殘缺方格，将右下角方格當成殘缺方格
                board[tr + 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, dc, s);
            }
            else
            {//此部分無殘缺方格，将左下角方格當成殘缺方格
                board[tr + s -1][tc + s] = t;
                chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
            }
            //覆寫左下角棋盤
            if (dr >= tr + s && dc < tc + s)
            {//殘缺方格在左下角
                chessBoard(tr + s, tc, dr, dc, s);
            }
            else
            {//此部分無殘缺方格，将右上角方格當成殘缺方格
                board[tr + s][tc + s - 1] = t;
                chessBoard(tr + s, tc, tr + s, tc + s -1, s);
            }
            //覆寫右下角棋盤
            if (dr >= tr + s && dc >= tc + s)
            {//殘缺方格在右下角
                chessBoard(tr + s, tc + s, dr, dc, s);
            }
            else
            {//此部分無殘缺方格，将左上角方格當成殘缺方格
                board[tr + s][tc + s] = t;
                chessBoard(tr + s, tc + s, tr +s, tc + s, s);
            }
    }
    public  void displayBoard(int size){
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                System.out.printf("%-4d",board[i][j]);//類似于C語言的printf函數。
            }
            System.out.println();
        }
    }
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int tr = sc.nextInt();
        int tc = sc.nextInt();
        int dr = sc.nextInt();
        int dc = sc.nextInt();
        ChessBoard chessBoard = new ChessBoard();
        chessBoard.chessBoard(tr,tc,dr,dc,size);
        chessBoard.displayBoard(size);
    }
}

           

因為數組初始化時預設為0，我這裡沒有将殘缺格子指派為0 了。

2.4.2、大整數乘法（n位）

我們都知道當整數的位數很大，使用乘法計算，可能導緻的數溢出，或者計算效率低下。n位數字一一相乘，位數大變得慢。那麼我們有沒有可能将其優化呢？

答案是肯定的！我們可以利用分治法。分而治之，再合并結果。

情況有如下的三種：

我們隻需要每次分治的時候，判斷目前的位數N是否為奇數，奇數我們将N+1，了解為補0.

當N<4,我們不需要分治了，直接計算傳回結果。

也就是我們隻需要知道處理情況2就行了。如圖所示：

#include<stdio.h>
#include<math.h>
#include<iostream> 
using namespace std;
int SIGN(long A)
{
    return A > 0 ? 1 : -1;
}

//X、Y為輸入的數 ，n為對齊後的位數
long caculatorBigNumber(long X,long Y, int n){
	int sign = SIGN(X) * SIGN(Y);
	
    if (X == 0 || Y == 0)//位數不同的時候，補充的0使得分割得到的數為0 
        return 0;
	if(n<4)
		return X*Y; //當劃分的位數小于4，我們不需要再遞歸分治了，直接計算。 
	if(n%2==1)//保證每次劃分後我們判斷劃分的位數是不是偶數，不是我們就必須補充0，讓它變為偶數 
		n=n+1;
	
    X = labs(X);
    Y = labs(Y);

	//我們的位數是對齊修改為了偶數
	long A = (long)(X / pow(10, n / 2));
    long B = (X % (long)pow(10, n / 2));
    long C = (long)(Y / pow(10, n / 2));
    long D = (Y % (long)pow(10, n / 2));
    long  AC = caculatorBigNumber(A, C, n / 2);
    long  BD = caculatorBigNumber(B, D, n / 2);
    long  ABCD = caculatorBigNumber((A - B), (D - C), n / 2) + AC + BD;
         
    //cout<<"A="<<A<<" B="<<B<<" C="<<C<<" D="<<D<<endl;
    //cout<<"AC="<<AC<<" BD="<<BD<<" ABCD="<<ABCD<<endl; 
    return (long long)(sign * (AC * pow(10, n) + ABCD * pow(10, n / 2) + BD));
	
}
int main(){
	int i=0;
	while(i<10){
		 long a ,b;	
		int n;
		printf("請輸入要計算的數:\n");
		scanf("%ld%ld",&a,&b);
		printf("請輸入兩個數中最大的位數：\n");

		scanf("%d",&n);
	
		printf("%ld",caculatorBigNumber(a,b,n));
		i++; 

	}
	return 0;
}
           

注意，這裡的資料不能輸入過大，否則溢出。

2.4.3、Strassen矩陣乘法實作

1、傳統的矩陣乘法公式：

也就是蠻力法

代碼實作：

int[][] maxtixCaculator(int [][]maxtix1,int [][]maxtix2,int n){
	int [][]result = new int[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			result[i][j]=0;
			for(int k=0;k<n;k++){
				result+=maxtix1[i][k]*maxtix2[k][j];
			}
		}
	}
	return result;
}
           

2、簡單的分治法實作：

算法導論中的僞碼：

你好要設計好如何分塊，同時還額外增加了遞歸棧，是以簡單的分治法并沒有比暴力法好。

那我們應該如何做才能優化呢？我們應該如同優化大整數乘法那個樣子，将計算的子問題減少。簡單的分治法進行了8個子問題的遞歸計算，如果我們可以将8變小則可以降低複雜度了 。

Strassen矩陣乘法：

由于代碼比較長，就不想琢磨寫了。參考這位仁兄的：

矩陣乘法三種方法（蠻力法、分治法、strassen）

package algorithms;
 
public class strassen {
    //建立一個随機數構成的nxn矩陣
    public static int[][] initializationMatrix(int n){
        int[][] result = new int[n][n];//建立一個nxn矩陣
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                result[i][j] = (int)(Math.random()*10); //随機生成1~10之間的數
            }
        }           
        return result;           
    }
   
    //蠻力法求矩陣相乘
    public static int[][] BruteForce(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                result[i][j] = 0;
                for(int k=0;k<n;k++){
                    result[i][j] += p[i][k]*q[k][j];
                }
            }
        }               
        return result;
    }
   
    //分治法求矩陣相乘
    public static int[][] DivideAndConquer(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];//建立一個nxn矩陣
        //當n為2時，用蠻力法求矩陣相乘，傳回結果結果
        if(n == 2){
            result = BruteForce(p,q,n);           
            return result;
        }
       
        //當n大于3時，采用分治法，遞歸求最終結果
        if(n > 2){
            int m = n/2;
            
            //将矩陣p分成四塊
            int[][] p1 = QuarterMatrix(p,n,1);
            int[][] p2 = QuarterMatrix(p,n,2);
            int[][] p3 = QuarterMatrix(p,n,3);
            int[][] p4 = QuarterMatrix(p,n,4);
            
            //将矩陣q分成四塊
            int[][] q1 = QuarterMatrix(q,n,1);
            int[][] q2 = QuarterMatrix(q,n,2);
            int[][] q3 = QuarterMatrix(q,n,3);
            int[][] q4 = QuarterMatrix(q,n,4);
            
            //将結果矩陣分成同等大小的四塊
            int[][] result1 = QuarterMatrix(result,n,1);
            int[][] result2 = QuarterMatrix(result,n,2);
            int[][] result3 = QuarterMatrix(result,n,3);
            int[][] result4 = QuarterMatrix(result,n,4);
           
            //最關鍵的步驟，遞歸調用DivideAndConquer()函數，并用公式相加
            result1 = AddMatrix(DivideAndConquer(p1,q1,m),DivideAndConquer(p2,q3,m),m);//y=ae+bg
            result2 = AddMatrix(DivideAndConquer(p1,q2,m),DivideAndConquer(p2,q4,m),m);//s=af+bh
            result3 = AddMatrix(DivideAndConquer(p3,q1,m),DivideAndConquer(p4,q3,m),m);//t=ce+dg
            result4 = AddMatrix(DivideAndConquer(p3,q2,m),DivideAndConquer(p4,q4,m),m);//u=cf+dh
            
            //合并，将四塊小矩陣合成整體
            result = TogetherMatrix(result1,result2,result3,result4,m);//把分成的四個小矩陣合并成一個大矩陣
        }
        return result;
    }
    
    //strassen法
    public static int[][] StrassenMethod(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];//建立一個nxn矩陣
        int m = n/2;
        
        //将矩陣p分成四塊
        int[][] p1 = QuarterMatrix(p,n,1);
        int[][] p2 = QuarterMatrix(p,n,2);
        int[][] p3 = QuarterMatrix(p,n,3);
        int[][] p4 = QuarterMatrix(p,n,4);
        
        //将矩陣q分成四塊
        int[][] q1 = QuarterMatrix(q,n,1);
        int[][] q2 = QuarterMatrix(q,n,2);
        int[][] q3 = QuarterMatrix(q,n,3);
        int[][] q4 = QuarterMatrix(q,n,4);
        
        int[][] m1 = DivideAndConquer(AddMatrix(p1,p4,m),AddMatrix(q1,q4,m),m);
        int[][] m2 = DivideAndConquer(AddMatrix(p3,p4,m),q1,m);
        int[][] m3 = DivideAndConquer(p1,ReduceMatrix(q2,q4,m),m);
        int[][] m4 = DivideAndConquer(p4,ReduceMatrix(q3,q1,m),m);
        int[][] m5 = DivideAndConquer(AddMatrix(p1,p2,m),q4,m);
        int[][] m6 = DivideAndConquer(ReduceMatrix(p3,p1,m),AddMatrix(q1,q2,m),m);
        int[][] m7 = DivideAndConquer(ReduceMatrix(p2,p4,m),AddMatrix(q3,q4,m),m);
        
        //将結果矩陣分成同等大小的四塊
        int[][] result1 = QuarterMatrix(result,n,1);
        int[][] result2 = QuarterMatrix(result,n,2);
        int[][] result3 = QuarterMatrix(result,n,3);
        int[][] result4 = QuarterMatrix(result,n,4);
       
        result1 = AddMatrix(ReduceMatrix(AddMatrix(m1,m4,m),m5,m),m7,m);
        result2 = AddMatrix(m3,m5,m);
        result3 = AddMatrix(m2,m4,m);
        result4 = AddMatrix(AddMatrix(ReduceMatrix(m1,m2,m),m3,m),m6,m);
        
        result = TogetherMatrix(result1,result2,result3,result4,m);//把分成的四個小矩陣合并成一個大矩陣
        
        return result;
    }
    
    
    
    
    //擷取矩陣的四分之一，number用來确定傳回哪一個四分之一
    public static int[][] QuarterMatrix(int[][] p,int n,int number){
        int rows = n/2;   //行數減半
        int cols = n/2;   //列數減半
        int[][] result = new int[rows][cols];
        switch(number){
           //左上
           case 1 :
           {
               for(int i=0;i<rows;i++)
                   for(int j=0;j<cols;j++)
                       result[i][j] = p[i][j];
               break;
           }
           //右上
           case 2 :
           {
               for(int i=0;i<rows;i++)
                   for(int j=0;j<n-cols;j++)
                       result[i][j] = p[i][j+cols];
               break;
           }
           //左下
           case 3 :
           {
               for(int i=0;i<n-rows;i++)
                   for(int j=0;j<cols;j++)
                       result[i][j] = p[i+rows][j];
               break;
           }
           //右下
           case 4 :
           {
               for(int i=0;i<n-rows;i++)
                   for(int j=0;j<n-cols;j++)
                       result[i][j] = p[i+rows][j+cols];
               break;
           }
           default:
               break;
        }
       
        return result;
     }
   
    //把均分為四分之一的矩陣，合成一個矩陣
    public static int[][] TogetherMatrix(int[][] a,int[][] b,int[][] c,int[][] d,int n){
        int[][] result = new int[2*n][2*n];
        for(int i=0;i<2*n;i++){
            for(int j=0;j<2*n;j++){
                if(i<n){
                    if(j<n)
                        result[i][j] = a[i][j];
                    else
                        result[i][j] = b[i][j-n];
                }else{
                    if(j<n)
                        result[i][j] = c[i-n][j];
                    else
                        result[i][j] = d[i-n][j-n];
                }
            }
        }
        return result;
    }
   
   
    //求兩個矩陣相加結果
    public static int[][] AddMatrix(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                result[i][j] = p[i][j]+q[i][j];
            }
        }
        return result;
    }
    
  //求兩個矩陣相減結果
    public static int[][] ReduceMatrix(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                result[i][j] = p[i][j]-q[i][j];
            }
        }
        return result;
    }
    
    //輸出矩陣的函數
    public static void PrintfMatrix(int[][] matrix,int n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                System.out.printf("% 4d",matrix[i][j]);
            System.out.println();
        }
       
    }
   
    public static void main(String args[]){
        int[][] p = initializationMatrix(8);
        int[][] q = initializationMatrix(8);
        //輸出生成的兩個矩陣
        System.out.println("p：");
        PrintfMatrix(p,8);
        System.out.println();
        System.out.println("q：");
        PrintfMatrix(q,8);
 
        //輸出分治法矩陣相乘後的結果
        int[][] bru_result = BruteForce(p,q,8);//建立一個矩陣存放矩陣相乘結果
        System.out.println();
        System.out.println("\np*q(蠻力法)：");
        PrintfMatrix(bru_result,8);
        
        //輸出分治法矩陣相乘後的結果
        int[][] dac_result = DivideAndConquer(p,q,8);//建立一個矩陣存放矩陣相乘結果
        System.out.println();
        System.out.println("p*q(分治法)：");
        PrintfMatrix(dac_result,8);
        
        //輸出strassen法矩陣相乘後的結果
        int[][] stra_result = StrassenMethod(p,q,8);//建立一個矩陣存放矩陣相乘結果
        System.out.println("\np*q(strassen法)：");
        PrintfMatrix(stra_result,8);
        
    }
 
 
}
           

一個有趣的思考：