122 lines
3.9 KiB
Markdown
122 lines
3.9 KiB
Markdown
---
|
||
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);
|
||
}
|
||
|
||
}
|
||
}
|
||
|
||
```
|