当前位置：首页 > 资讯 > 技术文档

用Python解决计数原理问题的方法

时间：2020-08-05 16:30 编辑：来源：阅读：
扫一扫，手机访问

摘要：用Python解决计数原理问题的方法

[b]前几天遇到这样一道数学题：[/b] 用四种不同颜色给三棱柱六个顶点涂色,要求每个点涂一种颜色,且每条棱的两个端点涂不同颜色,则不同的涂色方法有多少种？ [img]http://files.jb51.net/file_images/article/201608/201684150232223.png?20167415311[/img] 当我看完题目后，顿时不知所措。于是我拿起草稿纸在一旁漫无目的地演算了一下，企图能找到解决方法。结果一无所获。于是打算通过程序算法解决这个问题。经过2个多小时的研究，终于完成了代码，并求得了答案。由于Python写起来比较方便而且本人比较喜欢Python的语法，所以研究算法时我通常采用Python，此次也不例外。以下就是整个算法的实现过程。 [b]两种算法[/b] 我一共想出了两种用于解决本题的算法： [b] 算法一：[/b]将所有的涂色情况通过程序的循环计算出来，然后通过程序的条件判断去除掉不合题意的所有情况，最后得到最终结果。 [b]算法二：[/b]从其中任意一个端点（p0）入手，由于其它所有端点都没有涂色，所以它可以涂四种颜色。将这四种颜色通过循环分别涂在这个端点上，每涂上一种颜色后，获取与它相临的一个端点（p1），并获取它可以涂上的颜色，然后通过循环将可用颜色涂上（及不能涂上与p0相同的颜色），每涂上一种颜色，又将p1相邻的未涂色的点涂色（及除p0外其他的相邻端点）。每个点被涂色后都采用同样的方法将相邻的点涂色，以此类推，涂完最后一个点，就记一次情况。所有的递归都完成后，就获得了所有情况。算法一很直接很粗暴，所以我采用了算法二来解决上述问题。接下来就是具体的代码了。 [b]算法实现[/b] 我写了大约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()

[b]以下是对各段代码的介绍。[/b] [b]全局变量[/b] [b]colorList：[/b]颜色列表 [b]pointList：[/b]存放六个点的列表 [b] amount :[/b] 涂色方案的种数 [b]Point类[/b] 用于储存各个点的信息，如点的颜色（color属性，None代表无颜色）、相邻的点（'neibors'属性）。以及提供[b]paint[/b]方法用于将点标记颜色；[b]clean[/b]方法用于去除颜色；[b]getLeftOverColors[/b]方法用于获取可用颜色，及获取相邻点没有使用的颜色。 [b]main函数[/b] 程序开始运行时调用的函数，其中构造了所需的六个点，以及分别为这六个点明确了相邻的三个点。注意，由于这里的点只有相邻和不相邻的位置关系，所以不需要在意这些点到底在三棱柱里对应哪个位置，任意设定这些点的位置对结果来说并没有影响，只需注意它们之间的相邻关系即可。 [b]isLastOne函数[/b] 判断是不是最后一个未涂色的点。 [b]paintPoint函数[/b] 用于对作为参数传入的点进行着色。其中首先通过调用该点的[b]getLeftOverColors[/b]方法获取可用颜色，然后按照上文算法中介绍的，通过遍历可用颜色列表，为该点着色，如果该点不是最后一个点（通过[b]isLastOne[/b]函数判断），就递归调用[b]paintPoint[/b]函数为相邻的一个未着色的点着色，如果是，则将记下一次涂色方案。 [b]运行代码，得到结果 - 264：[/b] [img]http://files.jb51.net/file_images/article/201608/201684150621157.png?20167415631[/img] Ok，于是这道题就在我们的计算机的帮助下，被成功解决掉了～如果大家有更好的方案解决这一算法问题，欢迎留言进行交流～希望本文对大家学习Python和计数原理都能有所帮助。

全部评论(0)

上一篇：Python计算已经过去多少个周末的方法
下一篇：Python首次安装后运行报错(0xc000007b)的解决方法

资讯排行榜
更多>>