第444章 :破解n完全問題

請關閉瀏覽器的閱讀/暢讀/小說模式並且關閉廣告遮蔽過濾功能，避免出現內容無法顯示或者段落錯亂。

顧名思義，孔明棋是古代諸葛孔明發明的。

孔明棋，是黑白棋的一種，也是目前人類歷史上唯一一種只需要一個人就可以玩的棋子。

也是法國跳棋獨立鑽石在中國的別稱，也有人叫它跳彈珠，或者叫它“pegged”。

是一種一個人就可以玩的遊戲，它是由三十三個棋子排成井字型盤面，一般流傳的玩法是先取去中央的那個棋子，便可以展開遊戲。

遊戲時，是將棋子跳過鄰近的棋子，到達一個旁邊空著的位置，被跳過的棋子則從棋盤上取開；跳的路徑可以前、後、左、右，但不可對角跳，直到剩下最後的一顆棋子，遊戲便結束了。這是一種流傳很廣的益智遊戲，也有很多種變形的棋盤擺法。

孔明奇經常出現在小學或是中學的意志比賽中。

曾經有一個說法，如果一個人能把孔明棋盤上的棋子剩餘的最少，就證明他越厲害。

如果棋盤上面最後只剩下一個棋子的話，就證明這個少年人是個天才。

葉秋還未重生之前就被老媽逼著參加過奧數數學營，但是因為那個時候葉秋實在是太廢柴了，對數學也沒有多大的興趣，所以就半途而廢了

不過在奧數訓練營中葉秋接觸過孔明棋。

當時他和另外一個同學絞盡腦汁思考了三天三夜，但是棋盤上面剩下的棋子也有六個，和上面所說的天才還差得很遠。

這種遊戲的魅力在於玩法非常簡單，但是其中變化卻是數不盡的，解法更是不只一種。

所以不論其形式如何變化，總是能帶給人們無窮的樂趣。

葉秋琢磨不出來什麼東西。

回到城堡，他還陷入在頭腦風暴之中。

陸晚晚、靳可竹、安娜三個人看到葉秋平安歸來，也紛紛鬆了一口氣，各自回到自己的臥室睡覺。

葉秋卻沒有精力睡覺，他回到了書房在用e級超級電腦演示出來了一個孔明棋的棋格。

看著面前跳躍著的黑色棋子，葉秋幾乎不用了不到30分鐘的時間就攻破了孔明棋。

棋盤上面只剩下了一個黑色的棋子。

如果葉秋現在只是一個小學生，他肯定會被所有人都認為是天才。

可是。

葉秋要破解是np完全問題，這就完全不是一個維度的了。

葉秋玩兒兩局孔明棋，也沒有和np完全問題聯絡到了一起.

當葉秋完第三次的時候玩的時候，看著棋盤上面只剩下的最後一個黑色的氣質。

葉秋突然想到了一個理論。

抽屜理論！

桌上有十個拉波波特，要把這十個拉波波特放到九個抽屜裡，無論怎樣放，我們會發現至少會有一個抽屜裡面放不少於兩個拉波波特。這一現象就是我們所說的“抽屜原理”。

抽屜原理的一般含義為：“如果每個抽屜代表一個集合，每一個拉波波特就可以代表一個元素，假如有n1個元素放到n個集合中去，其中必定有一個集合裡至少有兩個元素。”抽屜原理有時也被稱為鴿巢原理。它是組合數學中一個重要的原理，原理1：把多於n個的物體放到n個抽屜裡，則至少有一個抽屜裡的東西不少於兩件。

抽屜原理中又有兩個理論。這兩個理論結合在一起，支撐起了抽屜理論

第一抽屜原理

證明（反證法）：如果每個抽屜至多隻能放進一個物體，那麼物體的總數至多是nx1，而不是題設的nk(k≥1)，故不可能。

原理二：把多於mn(m乘n)1（n不為0）個的物體放到n個抽屜裡，則至少有一個抽屜裡有不少於（m1）的物體。

證明（反證法）：若每個抽屜至多放進m個物體