分而治之法解决问题

分而治之法解决问题

ID:32823296

大小:1.40 MB

页数:4页

时间:2019-02-16

分而治之法解决问题_第1页
分而治之法解决问题_第2页
分而治之法解决问题_第3页
分而治之法解决问题_第4页
资源描述:

《分而治之法解决问题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、201100820157数学与统计学院全秋洪残缺棋盘问题残缺棋盘(defectivechessboard)是一个有2k×2k个方格的棋盘,其中恰有一个方格残缺。图3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注意当k=0时,仅存在一种可能的残缺棋盘(如图3a所示)。事实上,对于任意k,恰好存在22k种不同的残缺棋盘。残缺棋盘的问题要求用3个方格的板(三格板)(triominoes)覆盖残缺棋盘(如图4所示)。在此覆盖中,两个三格板不能重叠,三格板不能覆盖残缺方格,但必须覆盖其他所有的方格。在这种限制条件下,所需要的三格板总数为(22k-1)/3。可

2、以验证(22k-1)/3是一个整数。k为0的残缺棋盘很容易被覆盖,因为它没有非残缺的方格,用于覆盖的三格板的数目为0。当k=1时,正好存在3个非残缺的方格,并且这三个方格可用图4中的某一方向的三格板来覆盖。实际是要求用三格板覆盖n*n的方格棋盘,空出指定位置。图3残缺棋盘图4不同方向的三格板4/4用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖2k×2k残缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2k×2k棋盘一个很自然的划分方法就是将它划分为如图5a所示的4个2k-1×2k-1棋盘。注意到当完成这种划分后,4个小棋盘中仅仅有一个棋盘存在残缺方格(因为

3、原来的2k×2k棋盘仅仅有一个残缺方格)。首先覆盖其中包含残缺方格的2k-1×2k-1残缺棋盘,然后把剩下的3个小棋盘转变为残缺棋盘,为此将一个三格板放在由这3个小棋盘形成的角上,如图5b所示,其中原2k×2k棋盘中的残缺方格落入左上角的2k-1×2k-1棋盘。可以采用这种分割技术递归地覆盖2k×2k残缺棋盘。当棋盘的大小减为1×1时,递归过程终止。此时1×1的棋盘中仅仅包含一个方格且此方格残缺,所以无需放置三格板。图5分割2k×2k棋盘可以将上述分而治之算法编写成一个递归的C++函数TileBoard。该函数定义了一个全局的二维整数数组变量Board来表示棋盘

4、。Board[0][0]表示棋盘中左上角的方格。该函数还定义了一个全局整数变量tile,其初始值为1。函数的输入参数如下:•tr棋盘中左上角方格所在行。•tc棋盘中左上角方格所在列。•dr残缺方块所在行。•dc残缺方块所在列。•size棋盘的行数或列数。TileBoard函数的调用格式为TileBoard(tr,tc,dr,dc,size),其中size=2k。覆盖残缺棋盘所需要的三格板数目为(size2-1)/3。函数TileBoard用整数1到(size2-1)/34/4来表示这些三格板,并用三格板的标号来标记被该三格板覆盖的非残缺方格。令t(k)为函数Ti

5、leBoard覆盖一个2k×2k残缺棋盘所需要的时间。当k=0时,size等于1,覆盖它将花费常数时间d。当k>0时,将进行4次递归的函数调用,这些调用需花费的时间为4t(k-1)。除了这些时间外,if条件测试和覆盖3个非残缺方格也需要时间,假设用常数c表示这些额外时间。可以得到以下递归表达式:可以用迭代的方法来计算这个表达式,可得t(k)=(22k)。程序:残缺棋盘#includevoidTileBoard(inttr,inttc,intdr,intdc,intsize);voidOutputBoard(intsize);constn=8;i

6、nttile=1;intBoard[n][n];voidmain(){TileBoard(0,0,3,2,n);OutputBoard(n);}voidTileBoard(inttr,inttc,intdr,intdc,intsize){//覆盖残缺棋盘if(size==1)return;intt=tile++,//所使用的三格板的数目s=size/2;//象限大小//覆盖左上象限if(dr

7、+s-1][tc+s-1]=t;//覆盖其余部分4/4TileBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上象限if(dr=tc+s)//残缺方格位于本象限TileBoard(tr,tc+s,dr,dc,s);else{//本象限中没有残缺方格,把三格板t放在左下角Board[tr+s-1][tc+s]=t;//覆盖其余部分TileBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下象限if(dr>=tr+s&&dc

8、s);else{//把三

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。