原文链接：http://www.mydrs.org/program/list.asp?id=197
一、题意简述有n盏位置固定的彩灯排列成圆形，要用m种颜色去着色，求使相邻的彩灯着不同颜色的方案数。
二、算法分析:
设f(n)为用m种颜色给n盏彩灯着色的方案数，(i=1、2、…、n ) 见图1。 我们设三盏连续的彩灯依次编号为i-1，i，i+1。现在分析彩灯i-1与彩灯i+1。
图1 图2
（1）若彩灯i-1与彩灯i+1 颜色不同，如图1，则去掉彩灯i，如图2，则变成用m种颜色给n-1盏彩灯着色的方案数。即f(n-1)。 因为彩灯i有m-2种情况(它与彩灯i-1，i+1颜色不同)，所以此时方案数为(m-2)*f(n-1)。
图3 图4
（2）若彩灯i-1与彩灯i+1 颜色相同，如图3，则去掉彩灯i，并把彩灯i-1，i+1合并成彩灯i'，如图4。则变成用m种颜色给n-2盏彩灯着色的方案数。即f(n-2)。 因为彩灯i有m-1种情况(它与彩灯i-1，i+1颜色不同)，所以此时方案数为(m-1)*f(n-2)。 综合<1>、<2>得出计算f(n)的递归方程式:
f(n)=(m-2)*f(n-1)+(m-1)*f(n-2)
边界条件: 由上述分析过程可以看出满足递归式的n必须大于3。故必须先求出f(1)、f(2)、f(3)的值。很明显:
f(1)=m， f(2)=m*(m-1)， f(3)=m*(m-1)*(m-2)
三、小结
本题是第二试竞赛题中比较简单的一道题，但还是需要一定的数学功底，分析题意，列出递归方程式。此外，因本题方案数增长很快，因此高精度计算也是必不可少的。
作者：李榕滨
来源：福州三中
时间：2001-08-28
上一篇：《Bin Code》解题报告
下一篇：获取栈剩余空间尺寸