分治法 | 飞鸿踏雪

基本思想

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解子问题数量不定，但最好使每个子问题的规模相等

一般算法设计模式

divide-and-conquer(p)
{
    if(|p|<=n0) 
        adhoc(p);
    divide p into smaller subinstances p1,p2,pk;
    for(i=1,i<=k,k++)
        yi=divide-and-conquer(pi);
    return merge(y1,···,yk);
}

二分搜索技术

将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。

$x=[n/2]$,则找到x，算法终止
$x<a[n/2]$,在数组a的左半部继续搜索x

$x>a[n/2]$,在数组a的右半部继续搜索x

具体算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


 public static int binarySearch(int [] a,int x,int n){
 //在a[0]<=a[1]<=···<=a[n-1]中搜索x
 //找到x时返回起在数组中的位置，则返回-1
 int left =0;int right=n-1;
 while(left<=right)
 {
 int middle=(left+right)/2;
 if(x==a[middle])
     return middle;
 if(x>a[middle])
     left=middle+1;
 else
     right=middle-1;
 }
 return-1;//未找到x
 }

棋盘覆盖

在一个$2^k\times2^k$ 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘,在该问题中要用4中种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任意2个L型骨牌不得重叠覆盖

利用分治法得出的简洁算法

当k>0时，将$ 2^k\times 2^k $棋盘分割为4个$ 2^{k-1}\times 2^{k-1}$ 子棋盘，特殊方格必定位于4个较小子棋盘之一，其余3个子棋盘中无特殊方格。未来将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖着3个较小棋盘的会合处，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题，递归地使用这种分割，直至棋盘简化为1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


public class Divide_and_conquer {
    public void chessBoard(int tr,int tc,int dr,int dc,int size){
        int tile=0;
        int board[][]=new int[6][6];
        if(size==1)
            return;
        int t=tile++,
        s=size/2;

        //覆盖左上角棋盘
        if(dr<tr+s&&dc<tc+s)
            chessBoard(tr, tc, dr, dc, s);
        else{
        //用t号L型骨牌覆盖右下角
            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{
            //此棋盘中无特殊方格
            //用t号L型骨牌覆盖左下角
            board[tr+s-1][tc+s]=t;
            //覆盖其他方格
            chessBoard(tr, tc+s, tr+s-1, tc, s);
            }

        //覆盖左上角棋盘
        if(dr>=tr+s&&dc<tc+s)
        //特殊方格在此棋盘中
            chessBoard(tr+s, tc, dr, dc, s);
        else{
        //此棋盘中无特殊方格
        //用t号L型骨牌覆盖右下角
            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{
            //此棋盘中无特殊方格
            //用t号L型骨牌覆盖左下角
            board[tr+s][tc+s]=t;
            //覆盖其他方格
            chessBoard(tr+s, tc+s, tr+s, tc+s, s);
            }

        }  
    }