JAVA基于分治算法實現的棋盤覆蓋問題示例
本文主要介紹了ava基于分治算法實現的棋盤覆蓋問題,簡單描述了棋盤覆蓋問題,并結合具體實例形式分析了java基于分治算法實現棋盤覆蓋問題的相關操作技巧,需要的朋友可以參考下
分治算法是用了分治思想的一種算法，在進行了解棋盤問題前，我們先了解一下什么是分治？
將父問題分解為子問題同等方式求解，這和遞歸的概念很吻合，所以在分治算法通常以遞歸的方式實現(當然也有非遞歸的實現方式)。分治算法的描述從字面上也很容易理解，分、治其實還有個合并的過程：
- 分(Divide)：遞歸解決較小的問題(到終止層或者可以解決的時候停下)
- 治(Conquer)：遞歸求解，如果問題夠小直接求解。
- 合并(Combine)：將子問題的解構建父類問題
一般分治算法在正文中分解為兩個即以上的遞歸調用，并且子類問題一般是不想交的(互不影響)。當求解一個問題規模很大很難直接求解，但是規模較小的時候問題很容易求解并且這個問題并且問題滿足分治算法的適用條件，那么就可以使用分治算法。
在一個2^k * 2^k個方格組成的棋盤中，有一個方格與其它的不同，若使用以下四種L型骨牌覆蓋除這個特殊方格的其它方格，如何覆蓋。四個L型骨牌如下圖：
棋盤中的特殊方格如圖：
實現的基本原理是將2^k * 2^k的棋盤分成四塊2^(k - 1) * 2^(k - 1)的子棋盤，特殊方格一定在其中的一個子棋盤中，如果特殊方格在某一個子棋盤中，繼續遞歸處理這個子棋盤，直到這個子棋盤中只有一個方格為止如果特殊方格不在某一個子棋盤中，將這個子棋盤中的相應的位置設為骨牌號，將這個無特殊方格的了棋盤轉換為有特殊方格的子棋盤，然后再遞歸處理這個子棋盤。以上原理如圖所示：
具體代碼如下：
package demo;public class Chess { /*tr表示棋盤左上角行號 tc表示棋盤左上角列號 dr表示特殊棋盤的行號 dc表示特殊棋盤的列號*/ public static void ChessBoard(int tr, int tc, int dr, int dc, int size) { if(size == 1) { return; } int t = title ++; int s = size/2; //覆蓋左上角子棋盤 if(dr < tr + s && dc < tc +s) { //特殊方格在此棋盤中 ChessBoard(tr, tc, dr, dc, s); } else { //此棋盤中無特殊方格，用t號L型骨牌覆蓋右下角 Board[tr + s - 1][tr + 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, s); } //覆蓋左下角子棋盤 if(dr >= tr + s && dc < tc +s) { //特殊方格在此棋盤中 ChessBoard(tr + s, tc, dr, dc, s); } else { //此棋盤中無特殊方格，用t號L型骨牌覆蓋右上角 Board[tr + s][tr + s -1] = t; //覆蓋其余方格 ChessBoard(tr, 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); } } @SuppressWarnings("static-access") public static void main(String args[]) { System.out.println("測試結果："); Board[2][2] = 0; Chess ch = new Chess(); ch.ChessBoard(0, 0, 2, 2, size); for(int i = 0; i < size; ++ i) { for(int j = 0; j < size; j++) { System.out.print(Board[i][j] + " "); } System.out.println(); } } static final int size = 4; static int title = 1; static int Board[][] = new int[size][size];}復制代碼
運行結果：
