文章目录
  1. 1. 阿里巴巴2018实习生面试题
    1. 1.1. 题目
    2. 1.2. 解题

引言:学姐碰到的一道题,一开始就觉得应该是个数学题,但想了很久想不出来,觉得可以用dfs,但复杂度太高了,后来又觉得可以优化一下复杂度,但仍然太高,于是搜了一下,又是一个排列组合问题。


这是一个阿里巴巴在线考试算法题。

阿里巴巴2018实习生面试题

题目

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

求:有多少种涂色方法

备注:

  1. 不考虑数值越界的情况
  2. N>=1, M>=3。
  3. 一个例子:如果N=3,M=3时,一共有6种涂法。

时间限制: 3S(C/C++以外的语言为: 5S)

内存限制: 128M (C/C++以外的语言为: 640M)

输入:

输入数据为1行,2个int型的整数。分别表示涂色的颜色数量,以及将圆形分割的份数。

输出:

输入为涂色的方法数,是一个整型数

解题

参考文献 - 高考数学中涂色问题的常见解法及策略

记分为n个扇形m种颜色时染色方法为ana_n

递推公式:

an=m(m1)n1an1a_n=m*(m-1)^{n-1}-a_{n-1}

comments powered by HyperComments
文章目录
  1. 1. 阿里巴巴2018实习生面试题
    1. 1.1. 题目
    2. 1.2. 解题