多米诺-分治法(共4页).docx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《多米诺-分治法(共4页).docx》由会员分享,可在线阅读,更多相关《多米诺-分治法(共4页).docx(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上计算机算法设计与分析分治法求解多米诺骨牌 题目:现有n块“多米诺骨牌”S1,S2,Sn水平放成一排,每块骨牌Si包含左右两个部分,每个部分赋予一个非负整数值,如下图所示为包含6块骨牌的序列。骨牌可做180度旋转,使得原来在左边的值变到右边,而原来在右边的值移到左边,假设不论si如何旋转,Li总是存储si左边的值,Ri总是存储右边的值,Wi用于存储si的状态:当Li=Ri时记为0,否则记为1,试采用分治法设计算法求i=1n-1RiLi+1最大值,以及当取得最大之时每个骨牌的状态。解:输入为n个多米诺骨牌S1,S2,Sn ,可将输入在中间那块骨牌的中间,即骨牌S1+n2的
2、中间处拆分,这样原问题就被拆分为两个子问题,但是可以发现,新的子问题与原问题结构不完全一样。为解决这一问题,可对原始的输入作如下处理:此处拆分在原始输入序列左右两端各加半块骨牌,记为S0 和Sn+1 ,对应于L、R则为R0和Ln+1,并且令R0和Ln+1里面的值为0。如下图所示:则原规模为n的问题求MAX(i=1n-1RiLi+1)变为规模为规模为n+2的问题求i=0nRiLi+1,结构有所变化,但实际上由于左右两边加的半块骨牌中的元素值为0,对原问题结果并不会产生影响。这时在按原来的拆分方法进行拆分,就可将问题拆为两个规模为原问题一半的子问题。具体算法如下:(其中数组W用于存放所求和最大时各
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多米诺 分治
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内