计数原理是数学中的重要研究对象之一,分类加法计数原理、分步乘法计数原理是解决计数问题的最基本、最重要的方法,也称为基本计数原理,它们为解决很多实际问题提供了思想和工具。本文教大家怎么用 Python 解决在数学中遇到的计数原理问题。
Python 是一种面向对象、解释型计算机程序设计语言,由 Guido van Rossum 于 1989 年底发明,第一个公开发行版发行于 1991 年。Python 语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是 C/C++)很轻松地联结在一起。
前几天遇到这样一道数学题:
用四种不同颜色给三棱柱六个顶点涂色, 要求每个点涂一种颜色, 且每条棱的两个端点涂不同颜色, 则不同的涂色方法有多少种?
当我看完题目后,顿时不知所措。于是我拿起草稿纸在一旁漫无目的地演算了一下,企图能找到解决方法。结果一无所获。于是打算通过程序算法解决这个问题。经过 2 个多小时的研究,终于完成了代码,并求得了答案。
由于 Python 写起来比较方便而且本人比较喜欢 Python 的语法,所以研究算法时我通常采用 Python,此次也不例外。以下就是整个算法的实现过程。
两种算法
我一共想出了两种用于解决本题的算法:
算法一:将所有的涂色情况通过程序的循环计算出来,然后通过程序的条件判断去除掉不合题意的所有情况,最后得到最终结果。
算法二:从其中任意一个端点(p0)入手,由于其它所有端点都没有涂色,所以它可以涂四种颜色。将这四种颜色通过循环分别涂在这个端点上,每涂上一种颜色后,获取与它相临的一个端点(p1),并获取它可以涂上的颜色,然后通过循环将可用颜色涂上(及不能涂上与 p0 相同的颜色),每涂上一种颜色,又将 p1 相邻的未涂色的点涂色(及除 p0 外其他的相邻端点)。每个点被涂色后都采用同样的方法将相邻的点涂色,以此类推,涂完最后一个点,就记一次情况。所有的递归都完成后,就获得了所有情况。
算法一很直接很粗暴,所以我采用了算法二来解决上述问题。接下来就是具体的代码了。
算法实现
我写了大约 90 行 Python 代码来实现这个算法:
- colorList = [0, 1, 2, 3]
- pointList = []
- amount = 0
- class Point(object):
- def __init__(self):
- super(Point, self).__init__()
- self.neibors = []
- self.color = None
- def paint(self, c):
- self.color = c
- def clean(self):
- self.color = None
- def getLeftOverColors(self):
- copyOfColorList = colorList[0 : 4]
- for neibor in self.neibors:
- nc = neibor.color
- if nc in copyOfColorList:
- copyOfColorList.remove(nc)
- return copyOfColorList
- def main():
- global pointList
- p0 = Point()
- p1 = Point()
- p2 = Point()
- p3 = Point()
- p4 = Point()
- p5 = Point()
- p0.neibors = [p1, p2, p4]
- p1.neibors = [p0, p2, p5]
- p2.neibors = [p0, p1, p3]
- p3.neibors = [p2, p4, p5]
- p4.neibors = [p0, p3, p5]
- p5.neibors = [p4, p3, p1]
- pointList = [p0, p1, p2, p3, p4, p5]
- paintPoint(p0)
- print(amount)
- def paintPoint(p):
- global amount
- colors = p.getLeftOverColors()
- lastOne = isLastOne()
- for c in colors:
- p.paint(c)
- if lastOne:
- amount += 1
- else:
- for currentNeibor in p.neibors:
- if currentNeibor.color == None:
- paintPoint(currentNeibor)
- break
- p.clean()
- def isLastOne():
- global pointList
- paintedNum = 0
- for p in pointList:
- if p.color != None:
- paintedNum += 1
- return paintedNum == 5
- if __name__ == "__main__":
- main()
以下是对各段代码的介绍。
全局变量
colorList:颜色列表
pointList:存放六个点的列表
amount : 涂色方案的种数
Point 类
用于储存各个点的信息,如点的颜色(color 属性,None 代表无颜色)、相邻的点('neibors'属性)。以及提供 paint 方法用于将点标记颜色;clean 方法用于去除颜色;getLeftOverColors 方法用于获取可用颜色,及获取相邻点没有使用的颜色。
main 函数
程序开始运行时调用的函数,其中构造了所需的六个点,以及分别为这六个点明确了相邻的三个点。注意,由于这里的点只有相邻和不相邻的位置关系,所以不需要在意这些点到底在三棱柱里对应哪个位置,任意设定这些点的位置对结果来说并没有影响,只需注意它们之间的相邻关系即可。
isLastOne 函数
判断是不是最后一个未涂色的点。
paintPoint 函数
用于对作为参数传入的点进行着色。其中首先通过调用该点的 getLeftOverColors 方法获取可用颜色,然后按照上文算法中介绍的,通过遍历可用颜色列表,为该点着色,如果该点不是最后一个点(通过 isLastOne 函数判断),就递归调用 paintPoint 函数为相邻的一个未着色的点着色,如果是,则将记下一次涂色方案。
运行代码,得到结果 - 264:
Ok,于是这道题就在我们的计算机的帮助下,被成功解决掉了~如果大家有更好的方案解决这一算法问题,欢迎留言进行交流~希望本文对大家学习 Python 和计数原理都能有所帮助。
来源: http://www.phperz.com/article/17/0320/291056.html