算法系列(一)：分治政策--棋盤覆寫
一、分析
問題描述：
圖1-1 k=2時的一個特殊棋盤
在一個 2^k * 2^k 個方格組成的棋盤中，若恰有一個方格與其它方格不同，則稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。顯然特殊方格在棋盤上出現的位置有 4^k 種情形。因而對任何 k>=0 ，有 4^k 種不同的特殊棋盤。圖1-1中的特殊棋盤為 k=2 時 16 個特殊棋盤中的一個。
在棋盤覆寫問題中，要用圖1-2所示的4種不同形态的 L 型骨牌覆寫一個給定的特殊棋牌上除特殊方格以外的所有方格，且任何 2 個 L 型骨牌不得重疊覆寫。易知，在任何一個 2^k * 2^k 的棋盤中，用到的 L 型骨牌個數恰為 (4^k-1)/3 。
(a) (b) (c) (d) 圖1-2 4種不同形态的L型骨牌
用分治政策，可以設計解棋盤問題的一個簡捷的算法。
在本例分析之前先簡單回顧分治政策，“分治”，顧名思義，分而治之：分治法的基本思想是将一個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然後将各子問題的解合并得到原問題的解。
基本模式：
二、求解
數學歸納法證明：問題有解
(1) k=1時，有解
(2) k=2時，有解
(3) 設k-1時成立(k>=2)，則k時？
将 2^k * 2^k 棋盤分割為 4 個 2^(k-1) * 2^(k-1) 子棋盤，如下圖所示。
特殊方格必位于 4 個較小子棋盤之一中，其餘 3 個子棋盤中無特殊方格。為了将這 3 個無特殊方格的子棋盤轉化為特殊盤，我們可以用一個 L 型骨牌覆寫這 3 個較小的棋盤的彙合處，如下圖所示，這 3 個子棋盤上被 L 型骨牌覆寫的方格就成為該棋盤上的特殊方格，進而将原問題化為 4 個較小規模的棋盤覆寫問題。遞歸的使用這種分割，直至棋盤簡化為 2^1x2^1 棋盤。
三、程式
例：每一個L型骨牌用相等的數字填充。從1，2，3，......，(0号為特殊方塊所在位置)，按左上、右上、右下、左下順序依次填充
示例：當 k=3,即2^3x2^3：
程式分析及代碼(Java)：
版本(1.0)：我們先把窗體繪制出來：
/**
* @author Sherly-Liu
* @version 1.0(繪制窗體)
*/
class WindowsFrame extends JFrame implements ActionListener {
// 菜單
JMenuBar bar = new JMenuBar();
JMenu fileMenu = new JMenu(" 檔案 ");
JMenuItem setupItem = new JMenuItem(" 建立 ");// 菜單項
JMenuItem quitItem = new JMenuItem(" 退出 ");
JMenu helpMenu = new JMenu(" 幫助 ");
JMenuItem aboutItem = new JMenuItem("關于ChessboardCover");
JLabel backgroundLabel = new JLabel(); // 背景
Container contentPane = this.getContentPane();
// 建立任務的視窗
JFrame setupFrame;
// 建立任務視窗元素
JPanel jPanel1, jPanel2, jPanel3, jPanel4;
JLabel jLabel1, jLabel2, jLabel3, jLabel4, jLabel5;
JTextField drTextField, dcTextField;// 特殊方塊行、列
JButton confirmButton, cancelButton;// 确認、取消按鈕
JComboBox k_cmb;// 下拉清單(問題規模k)
/**
* 視窗類構造方法
*/
public WindowsFrame() {
super("ChessboardCover（棋盤覆寫）");
initialize();
}
/**
* 主視窗元素初始化
*/
public void initialize() {
// 将視窗位置放在螢幕中央
Dimension screensize = Toolkit.getDefaultToolkit().getScreenSize();
this.setSize(880, 600);
Dimension framesize = this.getSize();
int x = (int) screensize.getWidth() / 2 - (int) framesize.getWidth()
/ 2;
int y = (int) screensize.getHeight() / 2 - (int) framesize.getHeight()
/ 2;
this.setLocation(x, y);
// 設定背景圖檔，把Lable加進LayoutPane
try {
backgroundLabel.setIcon(new ImageIcon(ImageIO.read(new File(
"drawable", "background.jpg"))));
} catch (IOException e) {
e.printStackTrace();
}
this.getLayeredPane().add(backgroundLabel,
new Integer(Integer.MIN_VALUE));
backgroundLabel.setBounds(0, 20, 880, 550);
contentPane.setLayout(null);
this.setJMenuBar(bar);
fileMenu.add(setupItem);
fileMenu.addSeparator();// 分割線
fileMenu.add(quitItem);
helpMenu.add(aboutItem);
bar.add(fileMenu);
bar.add(helpMenu);
setupItem.addActionListener(this);
quitItem.addActionListener(this);
aboutItem.addActionListener(this);
((JPanel) contentPane).setOpaque(false);// 内容面闆設定為透明，LayoutPane面闆背景才顯現
this.setResizable(false);
this.setVisible(true);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
/**
* 建立問題視窗初始化
*/
public void setupInit() {
setupFrame = new JFrame("setup");
jPanel1 = new JPanel();
jPanel2 = new JPanel();
jPanel3 = new JPanel();
jPanel4 = new JPanel();
jLabel1 = new JLabel("k= ");
jLabel2 = new JLabel(" 将建立2^k寬度的棋盤");
jLabel3 = new JLabel("特殊方格的位置： ");
jLabel4 = new JLabel("行： ");
jLabel5 = new JLabel(" 列： ");
Font font = new Font("隸書", Font.BOLD, 18);// 字型大小的設定
jLabel1.setFont(font);
jLabel2.setFont(font);
drTextField = new JTextField(8);
dcTextField = new JTextField(8);
String[] item = { "1", "2", "3", "4", "5", "6", "7" };
k_cmb = new JComboBox(item);
confirmButton = new JButton("确定");
confirmButton.addActionListener(new SetupActionListener());
cancelButton = new JButton("取消");
cancelButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
setupFrame.dispose();
}
});
jPanel1.add(jLabel1);
jPanel1.add(k_cmb);
jPanel1.add(jLabel2);
jPanel2.add(jLabel3, BorderLayout.WEST);
jPanel3.add(jLabel4);
jPanel3.add(drTextField);
jPanel3.add(jLabel5);
jPanel3.add(dcTextField);
jPanel4.add(confirmButton);
jPanel4.add(cancelButton);
setupFrame.setLayout(new GridLayout(4, 1, 5, 5));
setupFrame.add(jPanel1);
setupFrame.add(jPanel2);
setupFrame.add(jPanel3);
setupFrame.add(jPanel4);
setupFrame.setVisible(true);
setupFrame.setSize(400, 220);
Dimension scrs = Toolkit.getDefaultToolkit().getScreenSize();
Dimension fs = setupFrame.getSize();
int x = (int) scrs.getWidth() / 2 - (int) fs.getWidth() / 2;
int y = (int) scrs.getHeight() / 2 - (int) fs.getHeight() / 2;
setupFrame.setLocation(x, y);
}
/**
* 菜單響應事件
*/
@Override
public void actionPerformed(ActionEvent e) {
// TODO Auto-generated method stub
String command = e.getActionCommand();
// 建立問題
// ********************************************
if (command.equals(" 建立 ")) {
setupInit();
}
// 退出***************
if (command.equals(" 退出 ")) {
int result = JOptionPane.showConfirmDialog(null, "是否真的退出程式？",
"提示資訊", JOptionPane.YES_NO_OPTION,
JOptionPane.QUESTION_MESSAGE);
if (result == 0) {
System.exit(0);
}
}
// 關于******************************************
if (command.equals("關于ChessboardCover")) {
JOptionPane.showMessageDialog(null, "ChessboardCover Demo 1.0"
+ "\n" + "Author:劉曉玲" + "\n" + "2015.12",
"關于ChessboardCover", JOptionPane.INFORMATION_MESSAGE, null);
}
}
/**
* 命名内部類，建立問題監聽器
*/
private class SetupActionListener implements ActionListener {
@Override
public void actionPerformed(ActionEvent e) {
}
}
}
// ***************************************
public class Main {
public static void main(String[] args) {
new WindowsFrame();
}
}
運作一下程式：
版本(1.1)：設計棋盤的資料結構：
（1）重載Label标簽，添加行列坐标屬性以及顔色；
import javax.swing.JLabel;
/**
* @author Sherly-Liu
* 重載标簽，增加行列坐标屬性
* @param lable标簽
* @param row行坐标
* @param column列坐标
*/
public class MyLabel extends JLabel {
JLabel label;
private int row;// 行坐标
private int column;// 列坐标
public MyLabel(int row, int column) {
super();
label = new JLabel();
this.row = row;
this.column = column;
}
public int getRow() {
return row;
}
public void setRow(int row) {
this.row = row;
}
public int getColumn() {
return column;
}
public void setColumn(int column) {
this.column = column;
}
}
（2）設計L型骨牌的資料結構
import java.awt.Color;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import javax.swing.JPanel;
/**
* @author Sherly-Liu L型骨牌類：組成為三個呈L型相連的lable标簽
* @param lable1
* @param lable2
* @param lable3
* @param tile骨牌編号
*/
public class L_Chess extends JPanel {
MyLabel label1;
MyLabel label2;
MyLabel label3;
Color color;
private int tile;// 骨牌編号
/**
* 構造方法:參數：三個标簽的橫縱坐标以及骨牌編号
*/
public L_Chess(int label1_r, int label1_c, int label2_r, int label2_c,
int label3_r, int label3_c, int tile) {
super();
this.tile = tile;
label1 = new MyLabel(label1_r, label1_c);
label2 = new MyLabel(label2_r, label2_c);
label3 = new MyLabel(label3_r, label3_c);
color = getRandomColor();
MyMouseListener listener = new MyMouseListener();
label1.addMouseListener(listener);
label2.addMouseListener(listener);
label3.addMouseListener(listener);
}
public int getTile() {
return tile;
}
public void setTile(int tile) {
this.tile = tile;
}
/**
* 擷取一個随機顔色
*
* @return Color
*/
public Color getRandomColor() {
int r1 = (int) (Math.random() * 255); // 通過調用Math類的random産生随機數
int g1 = (int) (Math.random() * 255); // 再通過随機數分别設定三原色，紅綠藍
int b1 = (int) (Math.random() * 255);
Color color = new Color(r1, g1, b1); // 建立一個顔色對象
return color;
}
/**
* 命名内部類，滑鼠點選監聽器
*/
private class MyMouseListener implements MouseListener {
@Override
public void mouseClicked(MouseEvent e) {
label1.setText(tile + "");
label1.setBackground(color);
label2.setText(tile + "");
label2.setBackground(color);
label3.setText(tile + "");
label3.setBackground(color);
}
@Override
public void mouseEntered(MouseEvent e) {
}
@Override
public void mouseExited(MouseEvent e) {
}
@Override
public void mousePressed(MouseEvent e) {
label1.setVisible(true);
label2.setVisible(true);
label3.setVisible(true);
}
@Override
public void mouseReleased(MouseEvent e) {
}
}
}
（3）設計棋盤的資料結構
import java.awt.Color;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.border.LineBorder;
/**
* @author Sherly-Liu 棋盤類
* @param tr表示棋盤左上角行坐标
* @param tc表示棋盤左上角列坐标
* @param dr表示特殊方格的行坐标
* @param dc表示特殊方格的列坐标
* @param SIZE
* =2^k。棋盤的規格為2^k*2^k
*
*/
public class Chessboard extends JPanel {
int k; // 棋盤的規格為2^k*2^k
int SIZE; // SIZE=2^k
int[][] b;// 棋格,棋盤規格為2^k*2^k個棋格
int tile = 1;// 骨牌編号
L_Chess[] chess;// L型骨牌,個數為 (4^k-1)/3
int dr;// 表示特殊方格的行坐标
int dc;// 表示特殊方格的列坐标
// 構造方法
public Chessboard(int k, int dr, int dc) {
this.k = k;
this.dr = dr;
this.dc = dc;
SIZE = (int) Math.pow(2, k);
b = new int[SIZE][SIZE];// 申請n*n數組空間
int temp = (((int) Math.pow(4, k)) - 1) / 3;// L型骨牌,個數為 (4^k-1)/3
chess = new L_Chess[temp];
Fill(0, 0, SIZE, dr, dc);
InitUI();
}
/**
* Fill方法：每一個L型骨牌用相等的數字填充。從1，2，3，......，(0号為特殊方塊所在位置)，按左上、右上、右下、左下順序依次填充
*/
public void Fill(int tr, int tc, int size, int dr, int dc) {
if (size == 1)
return;
else {
int t = tile++;
int s = size / 2;// 将棋盤四等分，即将問題分解為四個SIZE=2^(k-1)的子問題
if ((dr < tr + s) && (dc < tc + s)) {// 特殊方格在左上子棋盤
// b[tr + s - 1][tc + s] = b[tr + s][tc + s] = b[tr + s][tc + s
// - 1] = t;// 覆寫第一個L型骨牌：在右上、右下、左下交界處
chess[t - 1] = new L_Chess(tr + s - 1, tc + s, tr + s, tc + s,
tr + s, tc + s - 1, t);// 覆寫第一個L型骨牌：在右上、右下、左下交界處
// 采用遞歸分别求解每個子問題
Fill(tr, tc, s, dr, dc);
Fill(tr, tc + s, s, tr + s - 1, tc + s);
Fill(tr + s, tc + s, s, tr + s, tc + s);
Fill(tr + s, tc, s, tr + s, tc + s - 1);
} else if ((dr < tr + s) && (dc >= tc + s)) {// 特殊方格在右上子棋盤
// b[tr + s - 1][tc + s - 1] = b[tr + s][tc + s - 1] = b[tr +
// s][tc
// + s] = t;// 覆寫第一個L型骨牌：在左上、左下、右下交界處
chess[t - 1] = new L_Chess(tr + s - 1, tc + s - 1, tr + s, tc
+ s - 1, tr + s, tc + s, t);// 覆寫第一個L型骨牌：在左上、左下、右下交界處
// 采用遞歸分别求解每個子問題
Fill(tr, tc, s, tr + s - 1, tc + s - 1);
Fill(tr, tc + s, s, dr, dc);
Fill(tr + s, tc + s, s, tr + s, tc + s);
Fill(tr + s, tc, s, tr + s, tc + s - 1);
} else if ((dr >= tr + s) && (dc >= tc + s)) {// 特殊方格在右下子棋盤
// b[tr + s - 1][tc + s - 1] = b[tr + s - 1][tc + s] = b[tr +
// s][tc
// + s - 1] = t;// 覆寫第一個L型骨牌：在右上、左上、左下交界處
chess[t - 1] = new L_Chess(tr + s - 1, tc + s - 1, tr + s - 1,
tc + s, tr + s, tc + s - 1, t);// 覆寫第一個L型骨牌：在右上、左上、左下交界處
// 采用遞歸分别求解每個子問題
Fill(tr, tc, s, tr + s - 1, tc + s - 1);
Fill(tr, tc + s, s, tr + s - 1, tc + s);
Fill(tr + s, tc + s, s, dr, dc);
Fill(tr + s, tc, s, tr + s, tc + s - 1);
} else if ((dr >= tr + s) && (dc < tc + s)) {// 特殊方格在左下子棋盤
// b[tr + s - 1][tc + s - 1] = b[tr + s - 1][tc + s] = b[tr +
// s][tc
// + s] = t;// 覆寫第一個L型骨牌：在左上、右上、右下交界處
chess[t - 1] = new L_Chess(tr + s - 1, tc + s - 1, tr + s - 1,
tc + s, tr + s, tc + s, t);// 覆寫第一個L型骨牌：在左上、右上、右下交界處
// 采用遞歸分别求解每個子問題
Fill(tr, tc, s, tr + s - 1, tc + s - 1);
Fill(tr, tc + s, s, tr + s - 1, tc + s);
Fill(tr + s, tc + s, s, tr + s, tc + s);
Fill(tr + s, tc, s, dr, dc);
}
}
}
/**
* 初始化UI
*/
public void InitUI() {
this.setBounds(0, 0, 880, 500);
this.setVisible(true);
this.setBackground(Color.WHITE);
this.setLayout(null);
int width = 880 / SIZE;
int height = 500 / SIZE;
// 特殊方格
JLabel label = new JLabel();
label.setOpaque(true);
label.setBorder(new LineBorder(Color.GRAY));
label.setBackground(Color.WHITE);
label.setText("0");
label.setBounds(dc * width, dr * height, width, height);
this.add(label);
for (int i = 0; i < chess.length; i++) {
chess[i].label1.setOpaque(true);
chess[i].label1.setBorder(new LineBorder(Color.GRAY));
chess[i].label1.setVisible(true);
chess[i].label2.setOpaque(true);
chess[i].label2.setBorder(new LineBorder(Color.GRAY));
chess[i].label2.setVisible(true);
chess[i].label3.setOpaque(true);
chess[i].label3.setBorder(new LineBorder(Color.GRAY));
chess[i].label3.setVisible(true);
chess[i].label1.setBounds(chess[i].label1.getColumn() * width,
chess[i].label1.getRow() * height, width, height);
chess[i].label2.setBounds(chess[i].label2.getColumn() * width,
chess[i].label2.getRow() * height, width, height);
chess[i].label3.setBounds(chess[i].label3.getColumn() * width,
chess[i].label3.getRow() * height, width, height);
this.add(chess[i].label1);// 參數：(Component comp,int index)
this.add(chess[i].label2);
this.add(chess[i].label3);
}
}
public void Show() {
for (int i = 0; i < chess.length; i++) {
chess[i].label1.setText(chess[i].getTile() + "");
chess[i].label1.setBackground(chess[i].color);
chess[i].label2.setText(chess[i].getTile() + "");
chess[i].label2.setBackground(chess[i].color);
chess[i].label3.setText(chess[i].getTile() + "");
chess[i].label3.setBackground(chess[i].color);
}
}
}
版本(1.2)：實作建立問題按鈕的監聽事件：
/**
* 命名内部類，建立問題監聽器
*/
private class SetupActionListener implements ActionListener {
@Override
public void actionPerformed(ActionEvent e) {
setupFrame.dispose();
if (drTextField.getText().toString().equals("")
|| dcTextField.getText().toString().equals("")) {
JOptionPane.showMessageDialog(null, "特殊方塊的行值、列值不允許為空", "警告",
JOptionPane.WARNING_MESSAGE, null);
} else {
int k = Integer.valueOf(k_cmb.getSelectedItem().toString());
int dc = Integer.valueOf(dcTextField.getText().toString()) - 1;
int dr = Integer.valueOf(drTextField.getText().toString()) - 1;
int n = (int) Math.pow(2, k);
if (dr >= n || dc >= n) {
JOptionPane.showMessageDialog(null, "特殊方塊的行值、列值不允許大于 2^k ",
"警告", JOptionPane.WARNING_MESSAGE, null);
} else if (dr < 0 || dc < 0) {
JOptionPane.showMessageDialog(null, "特殊方塊的行值、列值不允許小于等于 0 ",
"警告", JOptionPane.WARNING_MESSAGE, null);
} else {
if (chessboardPanel != null) {
contentPane.remove(chessboardPanel);
}
chessboardPanel = new Chessboard(k, dr, dc);
contentPane.add(chessboardPanel);
showButton.setVisible(true);
showButton.setEnabled(true);
}
}
}
}
四、程式運作結果
實作了點選一下棋格自動填充L型骨牌，點選Show All！按鈕全部填充：
PS：類圖
（PS:之是以這一次把代碼分析得那麼細是因為有很多同學總是開頭難，不知道要怎麼開始寫代碼，是以加上了詳細的版本說明，一步一步引導大家寫程式，很适合新手看，當然老程式看看就可以過了，也歡迎指出程式設計上的不足一起探讨。）
源碼下載下傳位址:http://download.csdn.net/detail/qq_22145801/9687074
參考：計算機算法設計與分析 電子工業出版社 王曉東編著