棋盘覆盖算法java

⑴ 棋盘覆盖问题的算法实现

下面讨论棋盘覆盖问题中数据结构的设计。
（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);
}
}

⑵ 分治算法——汉诺塔问题

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

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

        任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于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）汉诺塔

⑶ 10个常用算法

原理：
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

一般步骤：
（1）确定该区间的中间位置K；
（2）将查找的值T与array[k]比较。
若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。

原理：
一种通过重复将问题分解为同类的子问题而解决问题的方法

典型例子：
斐波那契数列
描述： 斐波那契数列 指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368.....自然中的斐波那契数列") 自然中的斐波那契数列，这个数列从第3项开始，每一项都等于前两项之和。

解决方式：

原理：
在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

解决问题一般步骤：
1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。

2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。

3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

典型例子：
八皇后问题
描述：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

解决方式： https://blog.csdn.net/weixin_41865447/article/details/80034433

概念：
将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。

分类：
非稳定排序算法：快速排序、希尔排序、堆排序、直接选择排序
稳定的排序算法：基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序

十个常用排序算法

利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。

分类：
枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。

将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。

很难找到逆向规律

只要符合散列思想的算法都可以被称为是Hash算法

对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称为 碰撞 。

原理
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在 某种意义上的局部最优解 。
从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

一种近似算法

一般步骤：
1、建立数学模型来描述问题；
2、把求解的问题分成若干个子问题；
3、对每一子问题求解，得到子问题的局部最优解；
4、把子问题的解局部最优解合成原来解问题的一个解。

典型例子：
0/1背包问题
马踏棋盘
均分纸牌

例题： https://www.cnblogs.com/hust-chen/p/8646009.html

概念：
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

典型例子：
排序中：归并排序、堆排序、快速排序；
实例：找伪币、求最值、棋盘覆盖

https://ke..com/item/%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95/3263297

概念：
用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。

举例：
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济）等；

应用实例：
最短路径问题 ，项目管理，网络流优化等；

https://ke..com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fromtitle=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&fromid=15742703&fr=aladdin

概念：
在一个给定的字符文本内搜寻出自己想要找的一个字符串，平常所用的各种文本编辑器里的ctrl+F大多就是使用的这些字符匹配算法。

分类：
KMP、BM、Sunday、Horspool、RK

参考：
https://cloud.tencent.com/developer/news/282694
https://blog.csdn.net/paincupid/article/details/81159320

⑷ 棋盘覆盖算法

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();
}
}
}

⑸ 棋盘覆盖问题的算法分析

设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)。

⑹ 求NOIP2007普及组初赛试题（棋盘覆盖问题）的程序解析，比如程序的思路以及每步的作用

声明：本文使用的代码和例子的来源：《计算机算法设计与分析》（王晓东编着，电子工业出版社）。我对代码做了少许修改，使可以在tc的图形模式下看到题目的结果。

题目：在一个(2^k)*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘。现在要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角，方向随意），切任何两个L型方块不能重叠覆盖。L型方块的形态如下：

■■*■■***■*■
■******■*■■*■■

题目的解法使用分治法，即子问题和整体问题具有相同的形式。我们对棋盘做一个分割，切割一次后的棋盘如图1所示，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个。假设如图1所示，特殊方格位于右上角，我们把一个L型方块（灰色填充）放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，知道子棋盘的大小为1为止。
用到的L型方块需要（4^k-1)/3 个，算法的时间是O（4^k)，是渐进最优解法。