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

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

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

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

兩種算法

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

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

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

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

算法實(shí)現(xiàn)

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

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() 

以下是對(duì)各段代碼的介紹。

全局變量

    colorList：顏色列表

    pointList：存放六個(gè)點(diǎn)的列表

    amount : 涂色方案的種數(shù)

Point類

用于儲(chǔ)存各個(gè)點(diǎn)的信息，如點(diǎn)的顏色（color屬性，None代表無(wú)顏色）、相鄰的點(diǎn)（'neibors'屬性）。以及提供paint方法用于將點(diǎn)標(biāo)記顏色；clean方法用于去除顏色；getLeftOverColors方法用于獲取可用顏色，及獲取相鄰點(diǎn)沒有使用的顏色。

main函數(shù)

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

isLastOne函數(shù)

判斷是不是最后一個(gè)未涂色的點(diǎn)。

paintPoint函數(shù)

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

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

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

最新評(píng)論