扇形染色问题 Python解法

问题描述

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

求：有多少种涂色方法。 备注：

1. 不考虑数值越界。
2. N>=1，M>=3;

思路

设

为符合要求的第

个扇形的涂色方法。 对扇形1有m种涂色方法，扇形2有

种涂色方法，扇形3也有

种涂色方法，扇形n也有

种涂色方法。于是，共有

种不同的涂色方法，但是这种涂色方法可能出现1与n着色相同的情形，这是不符合题意的，因此，答案应从

中减去这些不符合题意的涂色方法。不符合题意的涂色方法怎么计算？1与n看做是一个扇形，其涂色方法相当于用m种颜色对n-1个扇形涂色，即

，于是：

可推导出

的通项公式：

代码实现

def circle_divide(m, n):
    if n == 1:
        return m
    elif n == 2:
        return m*(m - 1)
    return m* (m - 1)^(n - 1) - circle_divide(m, n-1)