黑白格涂色【NOIP2016提高组初赛】

2021年8月18日 | 分类: 【编程】

【问题】

一个 1×8 的方格图形(不可旋转)用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色,且不允许两个黑格相邻,共有_________种填涂方案。

【解析(方案1)】

设存在n个方格,填涂情况有2种:

1. 如果第一个是黑格,那么第二个一定是白格。共有n-2个填涂方案数。

2. 如果第一个是白格,那么第二个可以是黑格或白格。共有n-1个填涂方案数。

所以:\(f(n)=f(n-1)+f(n-2)\)

也就是说这是一个斐波那契数列问题。

边界条件是:\(f(1)=2(黑,白)\) ;\(f(2)=3(黑白,白白,白黑)\)

枚举出前几个的答案:2,3,5,8。

则有:\(f(n)=f(8)=f(6)+f(7)=55\)

【解析(方案2)】

当存在0个黑格:
\(C_{9}^{0}=1\)

当存在1个黑格:
\(C_{8}^{1}=8\)

当存在2个黑格,6个白格,有7个空可以插入:
\(C_{7}^{2}=21\)

当存在3个黑格,5个白格,有6个空可以插入:
\(C_{6}^{3}=20\)

当存在4个黑格,4个白格,有5个空可以插入:
\(C_{5}^{4}=5\)

总方案数 = 1+8+21+20+5 = 55