主題
題目連結：
題目大意：
輸入有多列，每列給定一正整數 n（2 ≦ n ≦ 400，且 n 為偶數。當 n = 0 時，代表輸入結束），試問有著 n 個節點的完全無向圖（即所有點之間（除了自己到自己以外）都有一條邊連著）可以產生出多少個彼此的邊不重複之生成樹（Spanning Tree）。
輸出格式參見範例輸出。
範例輸入：
4
0
範例輸出：
Case 1: 2
解題思維：
本題有公式解，而且相當地簡潔。邊不重複的生成樹之數量恰好為
n ÷ 2
個。
而這個可以利用數學歸納法證明：
先將節點們分成左右兩行，並將左邊的節點編為 L1 、 L2 、……，右邊的節點編為 R1 、 R2 、…… 如下圖
接著我們便開始證明：
n = 2 時，邊只有一條，所以生成樹就只有那一棵。此時命題成立。
假設 n = k 時，命題成立。再假設 m = k ÷ 2 且其生成樹為 T1 、 T2 、 …… 、 Tm。此時令 n = k + 2。將「新增」的那兩個節點特別定為 x 和 y（而不是 Lm+1 和 Rm+1，此為方便起見），則我們可以看到我們將
T1 加上 (L1, x) 、 (R1, y) 這兩條邊便可以得到一棵生成樹；
T2 加上 (L2, x) 、 (R2, y) 這兩條邊便可以得到另一棵生成樹；
……
Ti 加上 (Li, x) 、 (Ri, y) 這兩條邊便可以得到再一棵生成樹；
……
Tm 加上 (Lm, x) 、 (Rm, y) 這兩條邊便可以得到又一棵生成樹。
因此最後我們剩下 x 依序到 R1 、 R2 、 …… 、 Rm 這 m 條邊、 y 分別到 L1 、 L2 、 …… 、Lm 這 m 條邊以及 (x, y) 這條邊。而這 2m + 1 條邊可以形成最後一棵生成樹。
例如，以下為 n = 4 的情況（藍色的點以及邊為「新增」的物件）
而下圖為 n = 6 的情況
因此此時命題也成立。所以根據數學歸納法，命題成立。
因此最大的生成樹之數量為 m 棵，即 n ÷ 2 棵。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
