切割篱笆

来自计算思维百科
跳转至: 导航搜索
切割篱笆1.jpg

有道篱笆用7个同宽的木板拼接而成。因年久未修,有些木板已经折断或磨损,使整道篱笆呈现出参差不齐的轮廓,所以要用新的木板替换。不过为了环保,可以用一部分旧篱笆切割出长方形的木板充当木料,怎样计算能够切割出的最大长方形的面积?(不能以斜线切割)

切割篱笆2.png

解决方案

方案一-暴力法

用蛮力法截取长方形时只需要考虑两个因素,一是从哪块木板开始,二是到哪块木板结束。根据这两个因素,我们可以算出所有截取方式所对应的长方形面积,最后选出最大的即可。下面列出蛮力法中两种切割方式:

切割篱笆3.png

运用的计算思维

方案一运用了蛮力法寻找最大的长方形,是一种机械化的思维方式。

方案二-分治法

将7块木板的问题分成3块木板和4块木板的两个子问题。

切割篱笆4.png

那么我们希望得到的最大的长方形是在下面三种情况中出现:

1.最大面积的长方形在左侧的子问题中获得。

2.最大面积的长方形在右侧的子问题中获得。

3.最大面积的长方形横跨左右两侧的子问题。

对于前两种情况,我们只需要对每个子问题再进行分治,直到只有两块木板时,选出最大的即可。对于第三种情况的长方形必定横跨两个子问题,那么,我们可以从两个子问题的分界线出发,分别向左右两侧一格一格扩展下去。 两个子问题截取长方形如下图所示:

切割篱笆5.png

当最大长方形横跨两边时,比较1、2、3、4块长方形面积得出最大的长方形:

切割篱笆6.png

切割篱笆7.png

运用的计算思维

方案二利用分治法将大问题分解成小问题,对每个小问题再进行分解,递归地求解,最后将各小问题答案合并成最终的答案,运用了“分解”和“递归”的思想。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015