赞
踩
目录
在一个个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
例如:
对棋盘覆盖有了一个初步理解之后,采用分治法的思想能够很好的解决该问题。
对于一个规模为n的问题,若n很容易解决(n很小)则直接求解,否则将问题划分为k(1<k≤n)个小规模子问题,这些子问题相互独立且与原问题形式相同。对子问题进行递归求解,并将各个子问题的解进行组合合并得到原问题的解。这种算法设计策略被称为分治法。
分治算法生成的子问题总是原始问题的较小模式,这为使用递归技术提供了便利。在这种情况下,通过反复使用分而治之的方法,子问题的类型可以与原始问题保持一致,但规模不断缩小,直到子问题可以轻松直接地解决为止。因此递归过程是自然生成的。在算法设计中应用分治算法和递归可以提高效率。分治算法可以解决的问题一般具有以下特点。
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
3) 利用该问题分解出的子问题的解可以合并为该问题的解
4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题
棋盘覆盖问题的已知条件是在一个的棋盘上有一个特殊方格,因此算法的输入可以用来表示棋盘的大小,用(dr, dc)来表示特殊方格在棋盘中的位置。棋盘覆盖问题的输出结果是一个覆盖了L 形骨牌的棋盘,如何表示三个方格被同一个L形骨牌覆盖称为关键,将数据抽象成程序设计语言方便处理的形式,可以直接使用整数来填充表示被同一个L形骨牌覆盖的三个方格。这样就完成了棋盘覆盖问题中输入/输出数据的抽象。
将2k x 2k的棋盘划分为2(k-1) x 2(k-1)这样的子棋盘4块,递归填充各个棋子,填充分为四个情况,递归的出口为k=0,也就是子棋盘的方格数为1,递归填充的四种情况:
- 如果特殊方格在左上子棋盘,则递归填充左上子棋盘;否则填充左上子棋盘的右下角,将右下角看作特殊方格,然后递归填充左上棋盘。
- 如果特殊方格在右上子棋盘,则递归填充右上子棋盘;否则填充右上子棋盘的左下角,将左下角看作特殊方格,然后递归填充右上棋盘。
- 如果特殊方格在左下子棋盘,则递归填充左下子棋盘;否则填充左下子棋盘的右上角,将右上角看作特殊方格,然后递归填充左下棋盘。
- 如果特殊方格在右下子棋盘,则递归填充右下子棋盘;否则填充右下子棋盘的左上角,将左上角看作特殊方格,然后递归填充右下棋盘。
mathplotlib实现可视化,tkinter实现人机交互界面。
- import tkinter as tk
- from matplotlib import image
- from matplotlib.pyplot import pause
- import numpy as np
- cnt = 0
-
- def change_rgb(rgb):
- return "#%02x%02x%02x" % rgb
-
- def countboard(board):
- global countbox
- n = len(board)
- n = n*n
- countbox = [-1 for x in range(n)]
- k = 0
- for i in range(len(board)):
- for j in range(len(board)):
- countbox[k] = board[i][j]
- k+=1
- countbox = np.unique(countbox)
- for i in range(len(board)):
- for j in range(len(board)):
- for k in range(len(countbox)):
- if board[i][j] == countbox[k]:
- board[i][j] = k
-
-
- def drawboard(canvas1, board, startx=50, starty=50, cellwidth=50):
- width = 2 * startx + len(board) * cellwidth
- height = 2 * starty + len(board) * cellwidth
- canvas1.config(width=width, height=height)
-
- global cnt
- cnt+=1
- for i in range(len(board)):
- for j in range(len(board)):
- index = board[i][j]
- if index != -1:
- if index == 0:
- color = 'red'
- elif index == 1:
- color = 'gold'
- elif index == 2:
- color = 'blue'
- elif index == 3:
- color = 'green'
- elif index <= cnt:
- tc = (255-index*12, 255-index*10, index*10)
- color = change_rgb(tc)
- board[i][j] == -1
- else:
- color = 'white'
- cellx = startx + i * 50
- celly = starty + j * 50
- canvas1.create_rectangle(cellx, celly, cellx + cellwidth, celly + cellwidth,
- fill=color, outline="black")
- canvas1.after(1000, drawboard, canvas1, board)
-
- def ChessBoard(tr, tc, dr, dc, size):
- global mark
- global Board
- mark += 1
- count = mark
- if size == 1:
- return
- s = size // 2
- # 覆盖左上角子棋盘
- if dr < tr+s and dc < tc+s:
- ChessBoard(tr, tc, dr, dc, s)
- else:
- Board[tr+s-1][tc+s-1] = count
- ChessBoard(tr, tc, tr+s-1, tc+s-1, s)
- # 覆盖右上角子棋盘
- if dr < tr+s and dc >= tc+s:
- ChessBoard(tr, tc+s, dr, dc, s)
- else:
- Board[tr+s-1][tc+s] = count
- ChessBoard(tr, tc+s, tr+s-1, tc+s, s)
- # 覆盖左下角子棋盘
- if dr >= tr+s and dc < tc+s:
- ChessBoard(tr+s, tc, dr, dc, s)
- else:
- Board[tr+s][tc+s-1] = count
- ChessBoard(tr+s, tc, tr+s, tc+s-1, s)
- # 覆盖右下角子棋盘
- if dr >= tr+s and dc >= tc+s:
- ChessBoard(tr+s, tc+s, dr, dc, s)
- else:
- Board[tr+s][tc+s] = count
- ChessBoard(tr+s, tc+s, tr+s, tc+s, s)
-
-
- def showImage(Board):
- n=len(Board)
- for i in range(n):
- for j in range(n):
- print(Board[i][j], end=' ')
- print(' ')
-
-
- def Input():
- global Board
- global mark
- mark = 0
- n=entry_board_size.get()
- x=entry_board_x.get()
- y=entry_board_y.get()
- n=2**int(n)
- board = np.zeros(shape=[n, n], dtype=int)
-
- Board = [[-1 for x in range(n)] for y in range(n)]
- ChessBoard(0, 0, int(x), int(y), n)
- countboard(Board)
-
- window_chessboard = tk.Toplevel(window)
- window_chessboard.title('Chessboard')
-
- canvas1 = tk.Canvas(window_chessboard, bg="white")
- canvas1.pack()
- # button = tk.Button(window_chessboard, text="Next", font=('Arial', 15), command = drawboard(canvas1, Board))
- # button.pack()
- drawboard(canvas1, Board)
- showImage(Board)
-
-
- window = tk.Tk()
- window.title('Chessboard Coverage')
- window.geometry('800x400')
- window.resizable(width=False,height=False)
- tk.Label(window, text = 'Chessboard Coverage', font=('Times New Roman',25)).place(x=240,y=50)
- tk.Label(window, text = "输入棋盘大小(2的幂指数):",font=('Arial',15)).place(x=70, y=150)
- var_board_size = tk.StringVar()
- entry_board_size = tk.Entry(window, textvariable=var_board_size, font=('Arial',15))
- entry_board_size.place(x=350, y=150)
- tk.Label(window, text = "输入特殊方格位置:", font=('Arial',15)).place(x=70,y=200)
- tk.Label(window, text = "横坐标x:", font=('Arial',15)).place(x=150,y=250)
- var_board_x = tk.StringVar()
- entry_board_x = tk.Entry(window, textvariable=var_board_x, font=('Arial',15))
- entry_board_x.place(x=230, y=250)
- tk.Label(window, text = "纵坐标y:", font=('Arial',15)).place(x=450,y=250)
- var_board_y = tk.StringVar()
- entry_board_y = tk.Entry(window, textvariable=var_board_y, font=('Arial',15))
- entry_board_y.place(x=530, y=250)
- btn = tk.Button(window, text = "Run", font=('Arial',15),command = Input).place(x=350,y=300)
-
- window.mainloop()
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。