棋盤覆蓋演算法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)，是漸進最優解法。