铺瓷砖

来自计算思维百科
跳转至: 导航搜索
铺瓷砖1.jpg

用2×1大小的瓷砖铺满2×5大小的地面,共有多少种方法?条件是,瓷砖不能重叠,但可以旋转90度使用。

解决方案

方案一:穷举法

铺瓷砖2.png

运用的计算思维

2×5大小的地面只需要5块2×1大小的瓷砖就能铺满,穷举法是将5块瓷砖的铺排方式全部列出,运用了机械化的计算思维。

方案二:动态规划法

运用动态规划法解决此问题,我们需要将问题分割成子问题。假设每个小部分都是从覆盖2×5地面的最左侧竖线起始。

根据覆盖左侧竖线方式的不同,铺设2×5地面的方法可分为两种,如下图所示,左侧竖线可被一个或两个瓷砖覆盖住。

铺瓷砖3.png

当确定了左侧竖线的瓷砖铺设方式后,对竖线右侧的区域也进行同样的分割,直到所有的方式都找到,下图是动态规划求解问题的分解过程。

铺瓷砖4.png

运用的计算思维

动态规划法将问题分解成同等的子问题,递归地求解,运用的是“规约”的计算思维。

参考文献

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