2.6.2  组织游行队伍

假定您负责组织7月4日的游行，该游行队伍由一行乐队和彩车组成。去年，相邻乐队之间有不适当竞争。为避免此类问题，组织者要求任何两个乐队都不要相邻。要组织长为n的游行队伍，有多少种方法？

假设至少可从n个乐队和n辆彩车中选择。在计算组织游行队伍的方法数目时，将"乐队-彩车"与"彩车-乐队"序列看成不同队伍，视为两种方法。

队伍以彩车或乐队结尾。组织队伍的方法数仅是各类型队伍的数目之和。也就是说，令：

P(n)是组织长为n的队伍的方法数

F(n)是长为n、以彩车结尾的队伍的方法数

B(n)是长为n、以乐队结尾的队伍的方法数

则

P(n) = F(n) + B(n)

先分析F(n)。要得到一个长为n、以彩车结尾的游行队伍，只需要将一辆彩车放在长为n-1的任何可接受队伍的末尾。因此，长为n、以彩车结尾的可接受队伍数目正好等于长为n-1的可接受队伍的总数，即

F(n) = P(n-1)

注释：长为n、以彩车结尾的可接受队伍的数目

再看B(n)。只有倒数第二个单元为彩车时，队伍才能以乐队结尾(如果倒数第二个单元为乐队，则两个乐队就会相邻)。这样，组织长为n、以乐队结尾的可接受队伍的唯一方式是：先组织长为n-1、以彩车结尾的队伍，再在末尾加上乐队。因此，长为n、以乐队结尾的可接受队伍数目完全等于长为n-1、以彩车结尾的可接受队伍数目。即

B(n) = F(n-1)

由F(n) = P(n-1)，可知：

B(n) = P(n-2)

注释：长为n、以乐队结尾的可接受队伍的数目

这样，分别按更小问题P(n-1)和P(n-2)解决F(n)和B(n)。由

P(n) = F(n) + B(n)

知

P(n) = P(n-1) + P(n-2)

注释：长为n的可接受队伍的数目

这种递归关系形式与兔子繁殖问题的解决方案相同。

与兔子问题一样，此处需要两个基例，因为递归关系根据两个更小问题定义了一个问题。与兔子问题一样，可以选取n=1和n=2为基例。虽然二者都为基例选取了相同的数值n，但是二者基例的值并不相同。换句话说，没有理由认为rabbit(1)=P(1)，rabbit(2)=P(2)。

注释：两个基例是必需的，因为存在两个更小的问题

稍微思考一下，即可求得游行问题的基例。

P(1) = 2 (游行队伍长为1，包括：乐队、彩车)

P(2) = 3 (游行队伍长为2，包括：彩车-彩车、彩车-乐队、乐队-彩车)

总之，该问题的解决方案为：

P(1) = 2

P(2) = 3

P(n) = P(n-1) + P(n-2)     若n > 2

注释：递归解决方案

本例说明了递归的两个要点：

有时候可以将问题分成不同情况来解决。例如，以彩车结尾的队伍和以乐队结尾的队伍。

基例的值相当重要。尽管P和rabbit的递归关系相同，但由于基例(n=1或n=2)值不同，导致当n增大时，P(n)与rabbit(n)的值不同。例如，rabbit(20)=6 765，而P(20)=17 711。n值越大，差异越大。其原因请自行分析。