欢迎来到天天文库
浏览记录
ID:1773419
大小:28.41 KB
页数:3页
时间:2017-11-13
《用分治法求解棋盘覆盖问题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、棋盘覆盖问题问题描述:在一个2k×2k(k≥0)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为特殊方格。显然,特殊方格在棋盘中出现的位置有4k中情形,因而有4k中不同的棋盘,图(a)所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图(b)所示的4中不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且热河亮哥L型骨牌不得重复覆盖。图(b)图(a)问题分析:K>0时,可将2k×2k的棋盘划分为4个2k-1×2k-1的子棋盘。这样划分后,由于原棋盘只有一个特殊方格,所以,这4个子棋盘中只有1个子棋盘中有特殊方格,其
2、余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化成为特殊棋盘,以便采用递归方法求解,可以用一个L型骨牌覆盖这3个较小的棋盘的会合处,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略,直至将棋盘分割为1×1的子棋盘。问题求解:下面介绍棋盘覆盖问题中数据结构的设计。(1)棋盘:可以用一个二维数组board[size][size]表示一个棋盘,其中size=2k。为了在递归处理的过程中使用同一个棋盘,将数组board设为全局变量。(2)子棋盘:整个棋盘用二维数组board[size][size]表示,其
3、中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示。(3)特殊方格:用board[dr][dc]表示特殊方格,dr和dc是该特殊方格在二维数组board中的下标。(4)L型骨牌:一个2k×2k的棋盘中有一个特殊方格,所以,用到L型骨牌的个数为(4k-1)/3,将所有L型骨牌从1开始连续编号,用一个全局变量tile表示。C语言源码:/*author:彭洪伟*studentID:0950310006*class:计科1班*problem:分治法解决棋盘覆盖问题*/#include#includein
4、ttile=1;//记录骨牌的型号intboard[20][20]={0};//存储棋盘被覆盖的情况voidChessBoard(inttr,inttc,intdr,intdc,intsize){//tr和tc是棋盘左上角的下标,dr和dc是特殊方格的下标,size是棋盘的大小intt=0;ints;if(size==1)return;t=tile++;s=size/2;//划分棋盘//覆盖左上角棋盘if(dr
5、rd[tr+s-1][tc+s-1]=t;ChessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角棋盘if(dr
6、d[tr+s][tc+s-1]=t;ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角棋盘if(dr>=tr+s&&dc>=tc+s)//特殊方格在棋盘的右下角ChessBoard(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}intmain(){intk,x,y;printf("请输入棋盘的规模K:");scanf("%d",&k);printf("请输入特殊方格的下标x,y:");s
7、canf("%d%d",&x,&y);ChessBoard(0,0,x,y,pow(2,k));for(inti=0;i 当前文档最多预览五页,下载文档查看全文 侵权申诉 举报 1 1 2 3 / 3 此文档下载收益归作者所有 下载文档 当前文档最多预览五页,下载文档查看全文 点击下载本文档 版权提示 下载文档 举报 温馨提示: 1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。 2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。 3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。 4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。 相关文章 更多 棋盘覆盖和整数规划问题 分治法和蛮力法求解最近对问题 棋盘覆盖和整数规划问题 棋盘覆盖和整数规划问题 用分治法求解棋盘覆盖问题 分治算法求解棋盘覆盖问题的互动教学过程 棋盘覆盖问题C语言.doc 棋盘覆盖问题-C语言.doc 分治算法实验---棋盘覆盖问题.docx 棋盘覆盖问题.pptx 相关标签 分治 求解 覆盖 问题
此文档下载收益归作者所有