如果第一次閱讀本系列文檔請先移步閱讀【ROSALIND】【練Python，學生信】00 寫在前面 ?謝謝配合~

題目：

計算系統(tǒng)發(fā)生祖先數(shù)（Counting Phylogenetic Ancestors）

Given: A positive integer n (3≤n≤10000).

所給：一個正整數(shù)n，大小在3到10000之間。

Return: The number of internal nodes of any unrooted binary tree having n leaves.

需得：有n個葉子結點的二叉樹包含的內(nèi)節(jié)點的數(shù)量。

?

測試數(shù)據(jù)

4

測試輸出

2

?

生物學背景

????????在之前的問題中，我們考慮用樹來描述生物進化，但具體使用哪種樹并未確定。根據(jù)達爾文的進化學說，新物種通常是在舊有物種的一部分與原物種隔離一段時間后，變化積累產(chǎn)生的。在這種理論下產(chǎn)生的進化樹中，內(nèi)節(jié)點代表著進化的分枝點，在這里舊物種演變成一個新物種或進化為兩個新物種。這種進化方式很適合用二叉樹來表示。

?

數(shù)學背景

????????二叉樹是每個結點最多有兩個子樹的樹結構，即每個節(jié)點的度都不能超過3。有根數(shù)是有根節(jié)點的數(shù)，而無根樹沒有根結點。有根數(shù)根結點的度為2，其他內(nèi)結點的度為3，而無根樹所有內(nèi)結點的度都為3。

?

思路

????????這道題我是用畫圖解決的。

????????有4個葉子結點時：

????????顯然有兩個內(nèi)節(jié)點。

????????再加入一個結點，葉子結點數(shù)量仍然為4，內(nèi)結點數(shù)量也仍為2：

????????再添加一個結點，使葉子結點的數(shù)量達到5，此時有3個內(nèi)結點：

????????再加一個結點，葉子結點的數(shù)量為5，有3個內(nèi)結點：

????????再加一個結點，有6個葉子結點，4個內(nèi)結點：

????????……

????????以此類推，可以看到內(nèi)結點總比葉子結點少兩個，所以只要用給的葉子結點數(shù)減去2即為內(nèi)結點數(shù)。

????????當然，只用畫圖的方法近于作弊，怎么推導呢？有人給出了如下證明：

????????假設一個無根二叉樹有N個結點，則必有N-1個邊，且1個邊對應2個度。假設k是內(nèi)結點的數(shù)目，n是葉子結點的數(shù)目，內(nèi)結點度為3，葉子結點度為1。又因為無根二叉樹只有內(nèi)結點和葉子結點，則可以寫出等式：3k+n = 2((k+n)-1)，整理的k=n-2。

?

代碼

????????這是一道難得的不需要編程的題，解完題后我瀏覽了一下討論區(qū)，發(fā)現(xiàn)一片歡樂。其中有一評論放在這里非常合適：“No computer program involved unless you can't subtract two in your head.”