一道阿里面试编程题目：将一个圆形等分成N个小扇形，将这些扇形标记为1，2，3,…，N。现在使用M种颜色对每个扇形进行涂色，每个扇形涂一种颜色，且相邻的扇形颜色不同,问有多少种不同的涂法?（N≥1，M≥3）
解题思路这道题正常的思路很麻烦，如果用递归算法的话就比较简单。
递归，先找规律。设一共有f(n,m)种涂法，那么就找f(n,m)和前一项的关系。
考虑一种特殊情况，N=4，如下图所示，有两种情况需要考虑，分为A、B不同色（左）和A、B同色（右）两种情况，则
f(4,m)=m (m-1) (m-2)(m-2)+m(m-1)(m-1)=m(m-1)(m^2-3m+3)
如下所示
那么，当N=5时，有如下情况：
f(5,m)=(m (m-1) (m-2)(m-2)+m(m-1)(m-1))(m-1)=m(m-1)(m^2-3m+3)(m-1)= f(4,m) (m-1)
可见f(5,m)比f(4,m)多了(m-1)一项，简单推理可知当N≥5时有：
f(n,m) = f(n-1,m) (m-1)
现在考虑特殊情况下的f(n,m)，N分别为3，2，1时，f(3,m)=m (m-1) (m-2);f(2,m)=m (m-1) ;f(1,m)=m.
至此，所有的情况都已考虑清楚，最后将思路转化为代码，如下供大家参考：
#include<iostream> using namespace std;int calculate(int n, int m) { int num; if (n < 1 || m < 3) return 0; if (n == 1) num = m; else if (n == 2) num = m * (m - 1); else if (n == 3) num = m * (m - 1) * (m - 2); else if (n == 4) num = m * (m - 1) * ((m - 1) + (m - 2) * (m - 2)); else num = calculate(n - 1, m) * (m - 1); return num;}int main() { int n = 1,m = 3,res; while (1) { cout << "请输入n：" << endl; cin >> n; cout << "请输入m：" << endl; cin >> m; cout << "n=" <<n<< ",m=" << m<< endl; res = calculate(n, m); cout << "结果：" << res <<endl; cout << "----------------" << endl; } return 0;} 测试提供几组数据以供测试：
f(3,3) = 6
f(6,3) = 72
f(4,4) = 84
f(5,4) = 252总结
这道编程题目，使用递归算法，如果要用其他正常思路可能考虑的情况会更加复杂，可能由于个人水平问题写的不是很完美，代码仅供参考，如果有错误的地方希望能够指出，相互学习！