编程题：扇形染色问题

染色问题

将一个圆形等分成N个小扇形,将这些扇形标记为1,2,3,…,N。现在使用M种颜色对每个扇形进行涂色，每个扇形涂一种颜色，且相邻的扇形颜色不同。

求：有多少种涂色方法。
备注：
1，不考虑数值越界。
2，N>=1，M>=3;

分析

【分析】设$a(n) $为符合要求的对n个扇形的涂色方法。
对扇形1有m种涂色方法，扇形2有m－1种涂色方法，扇形3也有m－1种涂色方法，扇形n也有m－1种涂色方法。于是，共有$m\times (m-1)^{n-1} $种不同的涂色方法。但是，$a(n)\neq m\times (m-1)^{n-1} $，因为这种涂色方法可能出现1与n着色相同的情形，这是不符合题意的，因此，答案应从$m\times (m-1)^{n-1} $中减去这些不符合题意的涂色方法。

那么，这些不符合题意的涂色方法，又怎样计算呢？这时，把1与n看作一个扇形，其涂色方法相当于用m种颜色对n－1个扇形涂色（这种转换思维相当巧妙），不同的涂色方法有$a(n-1)$种，于是，有：
$$a(n)= m\times (m-1)^{n-1} - a(n-1)\cdots \cdots (n≥3) $$
其中，$a(3)=m(m-1)(m-2) $，上式是数列的递推公式，可推导出$a(n)$的通项公式(感谢wysrc评论提醒！)：
$$a(n)= (m-1)^{n} + (-1)^n (m-1)\cdots \cdots (n≥3) $$

实现

我们根据递推公式，采用递归法实现计算。

#include<iostream>
#include<cmath>
using namespace std;
int color(int m, int n)
{
	if (n == 1){
		return m;
	}
	else if (n == 2){
		return m * (m - 1);
	}
	//else if (n == 3){
	//	return m * (m - 1) * (m - 2);
	//}
	return m * pow(m - 1, n - 1) - color(m, n - 1);
}

int main() {
	cout << color(3, 4) << " " << color(4, 3) << " " << color(4, 3) << endl;
	return 0;
}

当然也可以直接根据通项公式来编程。