之前我們講了哥尼斯堡七橋問題
這個問題最後被偉大的大數學家歐拉解決了。
他證明出這七座橋永遠不可能一次性不帶重複的走完。
後來我們又計算出：
如果只走其中的6座橋（不帶重複一次性走完），一共有256種走法。
今天我們計算一下：
如果允許重複走其中的一座橋，要把七座橋全部走完有多少種走法？
下面帶大家一起解決它。
（下文所說的走法指的是不帶重複一次性走完圖中所有線路的走法）
首先，我們要明白這幾個事實。
一、允許重複走其中的一座橋相當於在這座橋的邊上再建一座橋，起點和終點不變，為什麼要這樣理解？為了看起來直觀、方便記數。
二、理論上來說，七座橋都可以重複走一次，因此有7種建橋的方法。但是實際上可以濃縮成3大種，因為有些情況是重複的，具體如下：
①（中間線，一種情況，無重複）
②（右上和右下，二種重複情況，記數×2）
③（左邊四座橋，四種重複情況，記數×4）
因此，一會兒我們把①②③的記數分別求出來，
然後①+②×2+③×4，就可以得到最終結果了。
但是在這之前，我們還是要從簡單的圖形入手。
【1】下圖中，從A到B有4種走法。
（2×2=4）
【2】下圖中，從A到B有6種走法。
（3×2=6）
【3】下圖中，從O到O有8種走法。
（2×4=8）
下面，我們要進階一步。
【4】下圖中，從A到B有16種走法。
（1×4+2×6=16）（4是【1】的4，6是【2】的6）
【5】下圖中，從O到O有16種走法。
（2×8=16）（8是【3】的8）
【6】下圖中，從O到O有48種走法。
（6×8=48）（8是【3】的8）
【7】下圖中，從A到B有24種走法。
（3×8=24）（8是【3】的8）
下面，我們再進階一步。
【8】下圖中，從A到B有64種走法。
（24×2+16=64）（24是【7】的24，16是【5】的16）
【9】下圖中，從A到B有72種走法。
（2×2×6+3×16=72）（6是【2】的6，16是【5】的16）
【10】下圖中，從A到B有64種走法。
（2×2×4+2×24=64）（4是【1】的4，24是【7】的24）
【11】下圖中，從A到B有64種走法。
（4×16=64）（16是【4】的16）
好了，進入今天的主題。
先求①：
走法一：這其實是【8】，只不過樣式變了，但是不影響本質，所以走法是64
走法二：這其實是【9】，只不過樣式變了，但是不影響本質，所以走法是72
但是要×2，因為走法二有2種。（左邊2個橋）
72×2=144
綜上：64+144=208
但是要×2，因為可以從A到B，也可以從B到A。
208×2=416
再求②：
走法一：這其實是【10】，只不過樣式變了，但是不影響本質，所以走法是64
走法二：這其實是【11】，只不過樣式變了，但是不影響本質，所以走法是64
但是要×2，因為走法二有2種。（左邊2個橋）
64×2=128
綜上：64+128=192
但是要×2，因為可以從A到B，也可以從B到A。
192×2=384
再求③：
走法一：這其實是【7】×2，只不過樣式變了，但是不影響本質，所以走法是24×2=48
走法二：這其實是【9】，只不過樣式變了，但是不影響本質，所以走法是72
但是要×2，因為走法二有2種。（左邊2個橋）
72×2=144
綜上：48+144=192
但是要×2，因為可以從A到B，也可以從B到A。
192×2=384
結論：
根據①+②×2+③×4
416+384×2+384×4=2720
如果允許重複走其中的一座橋，要把哥尼斯堡七座橋全部走完共有2720種走法！
閱讀更多 數學與編程 的文章
