InkSoul/content/algorithm/分治法.md

---
title: "分治法"
date: 2022-05-10T09:10:25+08:00

---

##### 基本思想

将一个规模为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进行比较。
1. $x=[n/2]$,则找到x，算法终止
2. $x<a[n/2]$,在数组a的左半部继续搜索x
3. $x>a[n/2]$,在数组a的右半部继续搜索x


   具体算法
     ```java
      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

```java
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);
            }

        }  
    }

```