福州三中 李榕滨

一、题意简述

　　有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)

三、小结

　　本题是第二试竞赛题中比较简单的一道题，但还是需要一定的数学功底，分析题意，列出递归方程式。此外，因本题方案数增长很快，因此高精度计算也是必不可少的。