Tromino课件.ppt

该【Tromino课件 】是由【yixingmaob】上传分享，文档一共【16】页，该文档可以免费在线阅读，需要了解更多关于【Tromino课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Tromino谜题
分治算法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。
1、基本思想
2、二分法
3、基本步骤
4、tomino谜题算法设计
分治算法的基本思想
当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。
分治算法的基本步骤
分治法解题的一般步骤:
(1)分解,将要解决的问题划分成若干规模较小的同类问题;
(2)求解,当子问题划分得足够小时,用较简单的方法解决;
(3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。
Tromino谜题
Tromino是一个由期盼上的三个邻接方块组成的L型瓦片。我们的问题是,如何Tromino覆盖少了一个方块(可以在棋盘上的任何位置)的2n*2n棋盘,除了这个缺失的方块,Tromino应该覆盖棋盘上的所有方块,而且不能有重叠。为此问题设计一个分治算法。
算法设计
假设有如下8*8的棋盘,其中着红色块为少了的方块
第一步先讨论问题的最小单位,即问题的原型。此时只有四个方格的棋盘,假设其中任意一块是缺失的,则只需要直接填充其余三块即可。
第二步,问题扩大,归纳其中的规律。变成4*4个的棋盘方格
此时可以看到如果以方格中心交叉线分别为X轴,Y轴。则到了第二步,每个象限都会有一个方格着色了。并且,如果初始缺失的方格在其中任意一个象限,则其余象限分布的着色方块必须在与原点最近的方块。这一步可以总结出一个关键点,着色方块所在的象限。为了得到着色块所在象限,我们必须知道当前方格个数以及原点。但是整个问题分析过程中只有一个原点,如果想设计一个高效的算法让其自动分解执行的话必须在各个子问题上都一个变量,于是利用了当前方格的第一个点,即第一行第一列的方块。这样,当算法继续执行的时候会分解为不同的第一节点。
voidChessBoard(inttr,inttc,intdr,intdc,intsize)
//tr和tc是棋盘左上角的下标,dr和dc是特殊方格的下标,
//size是棋盘的大小,t已初始化为0
{
if(size==1)return;//棋盘只有一个方格且是特殊方格
t++;//L型骨牌号
s=size/2;//划分棋盘
//覆盖左上角子棋盘
if(dr<tr+s&&dc<tc+s)//特殊方格在左上角子棋盘中
ChessBoard(tr,tc,dr,dc,s);//递归处理子棋盘
else{//用t号L型骨牌覆盖右下角,再递归处理子棋盘
board[tr+s-1][tc+s-1]=t;
ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
}
#include<>
#defineN16
inta[100][100];
intt=1;
voidTromino(int(*a)[N],intdr,intdc,inttr,inttc,intsize)
{
ints;
if(size==1)return;
if(size>1)
{
s=size/2;
if(dr<=(tr+s-1)&&dc<=(tc+s-1))/*特殊方块在左上部分*/
{
a[tr+s-1][tc+s]=t;
a[tr+s][tc+s]=t;
a[tr+s][tc+s-1]=t;
t++;
Tromino(a,dr,dc,tr,tc,s);
Tromino(a,tr+s-1,tc+s,tr,tc+s,s);
Tromino(a,tr+s,tc+s,tr+s,tc+s,s);
Tromino(a,tr+s,tc+s-1,tr+s,tc,s);
}
if(dr>(tr+s-1)&&dc>(tc+s-1)) /*特殊方块在右下部分*/
{
a[tr+s][tc+s-1]=t;
a[tr+s-1][tc+s-1]=t;
a[tr+s-1][tc+s]=t;
t++;
Tromino(a,dr,dc,tr+s,tc+s,s);
Tromino(a,tr+s,tc+s-1,tr+s,tc,s);
Tromino(a,tr+s-1,tc+s-1,tr,tc,s);
Tromino(a,tr+s-1,tc+s,tr,tc+s,s);
}
}
}
main()
{
inti,j,dr,dc,a[N][N];
printf("pleaseinputdr(0<dr<%d):",N);
scanf("%d",&dr);
printf("pleaseinputdc(0<dc<%d):",N);
scanf("%d",&dc);
a[dr][dc]=0;
Tromino(a,dr,dc,0,0,N);
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("%-4d",a[i][j]);
printf("\n");
}
system("pause");
}