Tromino谜题
题⽬：Tromino 谜题
Tromino是指⼀个由棋盘上的三个1*1⽅块组成的 L 型⾻牌。如何⽤ Tromino 覆盖⼀个缺少了了⼀个⽅块（可以在棋盘上任何位置）
的2^n*2^n棋盘（下图展⽰了n=3情况）。除了这个缺失的⽅块，Tromino应该覆盖棋盘上的所有⽅块，Tromino可以任意转向但不能由重叠。
设计内容及要求：
（1）为此问题设计⼀个分治算法，分析算法的时间复杂度；
（2）实现所设计的算法，并以图形化界⾯演⽰覆盖过程。
问题分析与解决思路
解决思路
1问题分析与
通过对问题的分析，题⽬要求⽤分治法来解决该问题。该问题中缺失⽅块的位置是任意的，棋盘⼤⼩是2的n次⽅（n为正整数）的矩阵，所以我们先来考虑最⼩规模即当n=1时的情况。这种情况下⽆论缺失的⽅块在哪个位置，我们只需要将剩下的三个⽅块填充就好，相当于放置⼀个⾻牌。当n=2时，⽅块数为4*4，划分⼦问题前，我们先将棋盘分为四个象限，确定缺失⽅块的象限后，将其它三个象限距离中⼼位置最近的⼀个⽅块填充。此时我们再将其划分为四个⽅块数为2*2的矩阵，将已经填充的⽅块
看作缺失⽅块，则每个⼩规模矩阵都有⼀个缺失⽅块，即它们是规模相同的⼦问题，依次递归最后将整个棋盘填充完整。如图2.1.3所⽰，将8*8棋盘中的1，2，3填充后，再将其划分为四个部分得到如图2.1.2所⽰的4*4棋盘，将4*4棋盘中的1,2,3⽅块填充后再划分得到如图2.1.1所⽰的2*2棋盘，填充后继续递归最终完成整个棋盘的填充。实际编程时可让相应的位置坐标赋值为k*i（k为中点位置，i为象限，i取值为1-4），界⾯动画展⽰时根据不同的值⽤不同颜⾊显⽰⽅块即可实现不同⾻牌的区分。
图1.1 n=1时填充图1.2  n=2 时填充及划分图1.3  n=3 时填充及划分
2 模型建⽴与算法描述
记棋盘为size*size的⼆维数组T，初始化为0，缺失⽅块位置为x,y，参数m、n分别记录棋盘横向位置的开始和结束（列的取值范围，更确切的说n为纵向长度，即下标的最⼤值+1），参数l,r分别记录棋盘纵向位置的开始和结束（⾏的取值范围，r同n）
建⽴数学模型：
T[k][j-1]=T[k][j]=T[k-1][j]=1*k，(x<k且y<j)
T[k-1][j-1]=T[k][j]=T[k-1][j]=2*k，(x>=k且y<j)
T[k-1][j-1]=T[k][j-1]=T[k-1][j]=3*k，（x>=k且y>=j）
T[k-1][j-1]=T[k][j-1]=T[k][j]=4*k，（x<k且y>=j）
其中k=(m+n)/2，j=(l+r)/2
我们将上述分析过程和解决的思路进⼀步归纳为以下步骤：
（1）如果n-m>=2，执⾏步骤（2），否则结束过程。
（2）将棋盘进⾏划分象限，（寻中⼼位置即第⼀象限右下⾓坐标k,j），判断缺失⽅块的象限，将其它三个象限距离中⼼最近的位置T[k-1] [j-1]、T[k][j-1]、T[k][j]、T[k-1][j]中的与缺失⽅块不在⼀个象限的其余三个的值置为缺失⽅块象限与k的乘积。执⾏步骤（3）
（3）以象限划分将棋盘划分为四个等规模的⼦问题，将已赋值位置和缺失位置都看做缺失位置参数，相应象限范围作为参数m,n,l,r。分别对四个⼦问题重复上述步骤（1）（2）
算法伪代码描述：
T=[[0 for i in range(size)] for i in range(size)]#定义⼆维0矩阵作为棋盘
算法 Tromino(m,n,l,r,x,y)
#输⼊：矩阵范围m,n,l,r及缺失位置坐标x,y
#采⽤分治思想将棋盘T进⾏赋值，得到仅有位置x,y值为0的棋盘矩阵T
if n-m >=2:
k=int((m+n)/2)
j=int((l+r)/2)
#缺失位置在第⼀象限
if x<k and y<j:
T[k][j-1]=1*k
T[k][j]=1*k
T[k-1][j]=1*k
#将四个⼦问题递归
Tromino(m,k,l,j,x,y)
Tromino(k,n,l,j,k,j-1)
Tromino(k,n,j,r,k,j)
Tromino(m,k,j,r,k-1,j)
#缺失位置在第⼆象限
elif x>=k and y<j:
T[k-1][j-1]=2*k
T[k][j]=2*k
T[k-1][j]=2*k
Tromino(m,k,l,j,k-1,j-1)
canvas动画
Tromino(k,n,l,j,x,y)
Tromino(k,n,j,r,k,j)
Tromino(m,k,j,r,k-1,j)
#缺失位置在第三象限
elif x>=k and y>=j:
T[k-1][j-1]=3*k
T[k][j-1]=3*k
T[k-1][j]=3*k
Tromino(m,k,l,j,k-1,j-1)
Tromino(k,n,l,j,k,j-1)
Tromino(k,n,j,r,x,y)
Tromino(m,k,j,r,k-1,j)
#缺失位置在第四象限
else:
T[k-1][j-1]=4*k
T[k][j-1]=4*k
T[k][j]=4*k
Tromino(m,k,l,j,k-1,j-1)
Tromino(k,n,l,j,k,j-1)
Tromino(k,n,j,r,k,j)
Tromino(m,k,j,r,x,y)
3 算法实现与复杂度分析
3.1 数据结构
⽤python中的⼆维列表表⽰棋盘。分析题⽬可知棋盘是2^n阶⽅阵，使⽤python中的⼆维列表（类似于c语⾔中的⼆维数组）可以很⽅便的描述棋盘的特性，并且像c语⾔中的数组那样可以很容易的进⾏取某⼀位置的值的操作。
3.2 实现步骤
（1）考虑最⼩规模即棋盘⼤⼩为2*2，此时n=0,m=2,l=0,r=2，假设x=0,y=1。此时中⼼位置k=(m+n)/2=1，j=(l+r)/2=1，判断缺失位置在第⼀象限，将剩余的⼆、三、四象限的离中⼼最近位置进⾏赋值，完成⼀个⾻牌的放置。在这种情况下，棋盘刚好填满。
（2）当棋盘规模⼤于2*2时，此时只需在上述步骤放置好第⼀个⾻牌后，将棋盘按象限划分为四个相同规模的⼦问题，分别重复执⾏上述操作即可
3.3 实现技巧
（1）分治：将棋盘划分为多个相同规模的⼦问题，得到⼦问题的解，最终合并得到整个问题的解；
（2）递归：⽤递归实现对划分的⼦问题求解，层层细分再层层整合最终求得问题的解。
3.4 时间、空间复杂度分析
1 时间复杂度分析
本题采⽤分治算法，每次将问题分为4个规模相同的⼦问题，每个⼦问题的基本操作为赋值运算（3次），经计算该算法下在棋盘⼤⼩
为n（⽅块数为2^n*2^n）的情况下，基本操作次数为3*4^(n-2)，时间效率类型属于Ω（2^n）类型。
2 空间复杂度分析
在本题中，所使⽤的变量为⼆维列表，其它变量也不随运⾏规模的增⼤⽽增多，其空间复杂度为O(n^2+C)，其中n表⽰棋盘真正的⼤⼩，即数组矩阵的⾏数或列数，C为常数。
4 程序实现及运⾏结果分析
4.1 程序实现(源码Python3.6)
from tkinter import *
from tkinter import ttk
from tkinter import scrolledtext
import time
import threading
class TrominoApp:
#变量、组件定义及初始化
def__init__(self,master):
self.speed=0.2
self.select=0
self.lb1=Label(master,text="棋盘⼤⼩(2^n)",font=('微软雅⿊',8),bg='Wheat')
self.lb1.place(x=130,y=30,anchor=NW)#定位
self.lb2=Label(master,text="缺失⽅块x坐标",font=('微软雅⿊',8),bg='Wheat')
self.lb2.place(x=330,y=30,anchor=NW)
self.lb3=Label(master,text="缺失⽅块y坐标",font=('微软雅⿊',8),bg='Wheat')
self.lb3.place(x=530,y=30,anchor=NW)
#⽂本框
self.t1=Entry(master,width=10,insertborderwidth=10)#输⼊⽂本框
self.t1.place(x=220,y=30)#设置⽂本框的位置
self.t2=Entry(master,width=10,insertborderwidth=10)
self.t2.place(x=420,y=30)
self.t3=Entry(master,width=10,insertborderwidth=10)
self.t3.place(x=620,y=30)
self.t4=scrolledtext.ScrolledText(master ,width=36,bg='lightyellow',
height=31,borderwidth = 3,font=('Arial',13),wrap=WORD)#滚动⽂本框
self.t4.place(x=10,y=70)
#按钮
self.bt1=Button(master,text="查看结果",width=8,height=1,bg='Plum',font=
('微软雅⿊',8),command=self.run)#设置按钮及点击事件
self.bt1.place(x=460,y=630)
self.bt2=Button(master,text="动画演⽰",width=8,height=1,bg='Plum',font=
('微软雅⿊',8),command=self.cartoon)#设置按钮及点击事件
self.bt2.place(x=600,y=630)
self.bt3=Button(master,text="重置",width=8,height=1,bg='Plum',font=
('微软雅⿊',8),command=self.CliktheButton2)#设置按钮及点击事件
self.bt3.place(x=730,y=30)
self.bt4=Button(master,text="清空结果",width=8,height=1,bg='Plum',font=
('微软雅⿊',8),command=self.clear)#设置按钮及点击事件
self.bt4.place(x=730,y=630)
#画布
self.canvas1 =Canvas(master ,
width = 512, # 指定Canvas组件的宽度
height = 512, # 指定Canvas组件的⾼度
bg = 'white') # 指定Canvas组件的背景⾊
self.canvas1.place(x=370,y=70)#画布定位
#============================"查看结果"按钮点击事件
def run(self):
self.select=0
self.CliktheButton1()
#============================"动画演⽰"按钮点击事件
def cartoon(self):
self.select=1
self.CliktheButton1()
#==========================="重置"按钮点击事件
def CliktheButton2(self):
#清空输⼊框
self.t1.delete('0','end')
self.t2.delete('0','end')
self.t3.delete('0','end')
#清空画布
x=ALL
self.canvas1.delete(x)
return 0
#==========================="清空结果"按钮点击事件
def clear(self):
self.t4.delete(1.0,END)
#清空画布
x=ALL
self.canvas1.delete(x)
return 0
#============================由run和cartoon调⽤
def CliktheButton1(self):
#获取输⼊值
self.n=int(())
self.x=int(())
self.y=int(())
if self.n<1:
self.t4.insert(END,'\n++++++++++++++++++++++++++++++++\n错误棋盘⼤⼩必须⼤于0\n')
else:
self.size=2**self.n
#信息及结果显⽰
if self.x>=self.size or self.y>=self.size:
self.t4.insert(END,'\n++++++++++++++++++++++++++++++++\n错误坐标越界\n')
else:
self.t4.insert(END,'\n++++++++++++++++++++++++++++++++\n棋盘⼤⼩：'+str(self.size)+'*'+str(self.size)+'\n'+'x:'+str(self.x)+''+'y:'+str(self.y)+'\n') llwidth=round(int(self.canvas1['width'])/self.size)#设置⽅块⼤⼩
self.T=[[0 for i in range(self.size)] for i in range(self.size)]
t1=time.perf_counter()
self.Tromino(0,self.size,0,self.size,self.x,self.y)
t=time.perf_counter()-t1
self.t4.insert(END,'运⾏时间：'+str(t)+'\n')
#清空画布
x=ALL
self.canvas1.delete(x)
#结果演⽰
ate_llwidth,fill="black",outline="black")
self.canvas1.update()#更新画布
time.sleep(0.3)
if self.select:
self.Display(0,self.size,0,self.size,self.x,self.y)#调⽤动画演⽰函数
else:
for i in range(self.size):
for j in range(self.size):
index=self.T[i][j]
if index==0:
color='black'
else:
lors[index%(lors)-1)]
ate_llwidth,fill=color,outline="black")
self.canvas1.update()#更新画布
#============================动画演⽰函数由CliktheButton1调⽤
def Display(self,m,n,l,r,x,y):
k=int((m+n)/2)
j=int((l+r)/2)
if n-m >=2:
if x<k and y<j:#1--缺失位置在第⼀象限
#第⼆、三、四象限离中⼼最近位置置为1*k，相当于放置⼀个⾻牌
lors[(1*k)%(lors)-1)]
ate_llwidth,fill=color,outline="black")
ate_llwidth,fill=color,outline="black")
ate_llwidth,fill=color,outline="black")
self.canvas1.update()#更新画布
time.sleep(self.speed)
#递归分为四个相同规模的棋盘四个象限
self.Display(m,k,l,j,x,y)#1
self.Display(k,n,l,j,k,j-1)#2
self.Display(k,n,j,r,k,j)#3
self.Display(m,k,j,r,k-1,j)#4
elif x>=k and y<j:#2
lors[(2*k)%(lors)-1)]
ate_llwidth,fill=color,outline="black")
ate_llwidth,fill=color,outline="black")

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。