棋盘覆盖实验算法描述

1. 棋盘覆盖算法

import java.util.*;

public class TestChessBoard {
public static void main(String[] args) {
int tr=0,tc=0,dr=1,dc=2,size=8;
ChessBoard.chessBoard(tr,tc,dr,dc,size);
ChessBoard.display();
}
}

class ChessBoard {
public static int tile = 0;
public static int[][] board= new int[10][10];
public static void chessBoard (int tr,int tc,int dr,int dc,int size) {

if(size == 1) return;
int t = tile++ , s = size/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 static void display() {
for(int i=0;i<8;i++){
for(int j=0;j<8;j++) {
System.out.print(" "+board[i][j]);
}
System.out.println();
}
}
}

2. 分治算法——汉诺塔问题

一、分治算法概念
      “分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

        这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换) 。

        任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

二、分治法的设计思想

        将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

三、分治策略

        对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

四、分治法实现步骤

①分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；②解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；③合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：                                                                                           Divide-and-Conquer(P)                                                                                                          1. if |P|≤n0                                                                                                                               2. then return(ADHOC(P))                                                                                                     3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk                                                                                     4. for i←1 to k                                                                                                                        5. do yi ← Divide-and-Conquer(Pi)  递归解决Pi                                                                    6. T ← MERGE(y1,y2,…,yk)  合并子问题                                                                              7. return(T)

五、可使用分治法求解的一些经典问题                                                                             （1）二分搜索 

 （2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖 

 （5）合并排序

（6）快速排序

（7）线性时间选择

 （8）最接近点对问题

 （9）循环赛日程表

（10）汉诺塔

3. 棋盘覆盖问题的算法分析

设T(k)是算法ChessBoard覆盖一个2^k×2^k棋盘所需时间，从算法的划分
策略可知，T(k)满足如下递推式：
T(k) = 1 当k=0时
T(k) = 4T(k-1) 当k>0时
解此递推式可得T(k)=O(4^k)。

4. 分治算法几个经典例子

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础。

图二

大整数乘法

Strassen矩阵乘法

棋盘覆盖

合并排序

快速排序

线性时间选择

最接近点对问题

循环赛日程表

汉诺塔

5. 棋盘覆盖问题的算法实现

下面讨论棋盘覆盖问题中数据结构的设计。
（1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；
（2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；
（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标;
（4） L型骨牌：一个2^k×2^k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4^k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。
设全局变量t已初始化为0，分治法求解棋盘覆盖问题的算法用C++语言描述如下：
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
int s, t1; //t1表示本次覆盖所用L型骨牌的编号
if (size == 1) return; //棋盘只有一个方格且是特殊方格
t1 = ++t; // L型骨牌编号
s = size/2; // 划分棋盘
if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盘中
ChessBoard(tr, tc, dr, dc, s); //递归处理子棋盘
else{ //用 t1号L型骨牌覆盖右下角，再递归处理子棋盘
board[tr + s - 1][tc + s - 1] = t1;
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 { //用 t1号L型骨牌覆盖左下角，再递归处理子棋盘
board[tr + s - 1][tc + s] = t1;
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 { //用 t1号L型骨牌覆盖右上角，再递归处理子棋盘
board[tr + s][tc + s - 1] = t1;
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 { //用 t1号L型骨牌覆盖左上角，再递归处理子棋盘
board[tr + s][tc + s] = t1;
ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}