用Python解決計數原理問題的方法

2019-11-25 16:37:27

字體：大中小

來源：轉載

供稿：網友

前幾天遇到這樣一道數學題：

用四種不同顏色給三棱柱六個頂點涂色,要求每個點涂一種顏色,且每條棱的兩個端點涂不同顏色,則不同的涂色方法有多少種？

當我看完題目后，頓時不知所措。于是我拿起草稿紙在一旁漫無目的地演算了一下，企圖能找到解決方法。結果一無所獲。于是打算通過程序算法解決這個問題。經過2個多小時的研究，終于完成了代碼，并求得了答案。

由于Python寫起來比較方便而且本人比較喜歡Python的語法，所以研究算法時我通常采用Python，此次也不例外。以下就是整個算法的實現過程。

兩種算法

我一共想出了兩種用于解決本題的算法：

算法一：將所有的涂色情況通過程序的循環計算出來，然后通過程序的條件判斷去除掉不合題意的所有情況，最后得到最終結果。

算法二：從其中任意一個端點（p0）入手，由于其它所有端點都沒有涂色，所以它可以涂四種顏色。將這四種顏色通過循環分別涂在這個端點上，每涂上一種顏色后，獲取與它相臨的一個端點（p1），并獲取它可以涂上的顏色，然后通過循環將可用顏色涂上（及不能涂上與p0相同的顏色），每涂上一種顏色，又將p1相鄰的未涂色的點涂色（及除p0外其他的相鄰端點）。每個點被涂色后都采用同樣的方法將相鄰的點涂色，以此類推，涂完最后一個點，就記一次情況。所有的遞歸都完成后，就獲得了所有情況。

算法一很直接很粗暴，所以我采用了算法二來解決上述問題。接下來就是具體的代碼了。

算法實現

我寫了大約90行Python代碼來實現這個算法：

colorList = [0, 1, 2, 3]pointList = []amount = 0class 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 copyOfColorListdef 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 == 5if __name__ == "__main__":  main()

以下是對各段代碼的介紹。

全局變量

colorList：顏色列表

pointList：存放六個點的列表

amount : 涂色方案的種數

Point類

用于儲存各個點的信息，如點的顏色（color屬性，None代表無顏色）、相鄰的點（'neibors'屬性）。以及提供paint方法用于將點標記顏色；clean方法用于去除顏色；getLeftOverColors方法用于獲取可用顏色，及獲取相鄰點沒有使用的顏色。

main函數

程序開始運行時調用的函數，其中構造了所需的六個點，以及分別為這六個點明確了相鄰的三個點。注意，由于這里的點只有相鄰和不相鄰的位置關系，所以不需要在意這些點到底在三棱柱里對應哪個位置，任意設定這些點的位置對結果來說并沒有影響，只需注意它們之間的相鄰關系即可。

isLastOne函數

判斷是不是最后一個未涂色的點。

paintPoint函數

用于對作為參數傳入的點進行著色。其中首先通過調用該點的getLeftOverColors方法獲取可用顏色，然后按照上文算法中介紹的，通過遍歷可用顏色列表，為該點著色，如果該點不是最后一個點（通過isLastOne函數判斷），就遞歸調用paintPoint函數為相鄰的一個未著色的點著色，如果是，則將記下一次涂色方案。

運行代碼，得到結果 - 264：