CSP-S 2021 第一轮 第13题：有8个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两

题目

有 $8$ 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（ ）种方案。

选项

• A. 36
• B. 48
• C. 54
• D. 64

答案

C

题解

答案是 C．54。可以用递推来计算。

设 \(f(n)\) 表示从 \(n\) 个苹果中选取、且不选相邻苹果的方案数，暂时允许一个也不选。

考虑最右边的苹果：

• 不选它：前面 \(n-1\) 个苹果有 \(f(n-1)\) 种选法。
• 选它：它左边的苹果就不能选，剩下前面 \(n-2\) 个苹果有 \(f(n-2)\) 种选法。

所以 \[ f(n)=f(n-1)+f(n-2). \]

初始时 \(f(0)=1\)（什么都不选），\(f(1)=2\)（选或不选）。依次算得：

题目要求至少选一个，减去“一个也不选”的方案： \[ \boxed{55-1=54}. \]