NOIP 提高 2016 第一轮 第 21 题：一个 1 8 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只

题目

一个 $1\times 8$ 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_种填涂方案。

答案

55

题解

考点定位

本题考「不相邻染色计数」,对应大纲 2.1.5 计数（难度【4】）。

解题过程

1×8 方格黑白涂色，无相邻黑格：设 f(i) 为 i 格方案数，f(i)=f(i−1)+f(i−2)（第 i 格白/黑）：f(1)=2、f(2)=3 ⇒ f(8)=55？递推：2,3,5,8,13,21,34,55。官方答案 55。

答案：55。

易错提醒

① 递推两分支：第 i 格白 → f(i−1)；黑 → 第 i−1 必白 → f(i−2)；② 即斐波那契变形。