前幾天遇到這樣一道數(shù)學(xué)題：

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

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

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

兩種算法

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

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

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

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

算法實現(xiàn)

我寫了大約90行Python代碼來實現(xiàn)這個算法：

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 : 涂色方案的種數(shù)

Point類

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

main函數(shù)

程序開始運行時調(diào)用的函數(shù)，其中構(gòu)造了所需的六個點，以及分別為這六個點明確了相鄰的三個點。注意，由于這里的點只有相鄰和不相鄰的位置關(guān)系，所以不需要在意這些點到底在三棱柱里對應(yīng)哪個位置，任意設(shè)定這些點的位置對結(jié)果來說并沒有影響，只需注意它們之間的相鄰關(guān)系即可。

isLastOne函數(shù)

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

paintPoint函數(shù)

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

運行代碼，得到結(jié)果 - 264：

Ok，于是這道題就在我們的計算機的幫助下，被成功解決掉了～如果大家有更好的方案解決這一算法問題，歡迎留言進行交流～希望本文對大家學(xué)習(xí)Python和計數(shù)原理都能有所幫助。

最新評論