Download presentation
Presentation is loading. Please wait.
1
10303: How Many Trees? ★★☆☆☆ 題組：Contest Archive with Online Judge
解題者：朱峘愷 解題日期：2011年5月8日 題意：此樹為資料結構中的二元樹。給你節點的數目n， 求出最多可以形成多少種不同的二元樹。每筆測試資料一列。每列有1個整數 n（1 <= n <= 1000），代表有多少個節點。針對輸入的n值，輸出可以形成多少種不同的二元樹。
2
題意範例： uva上給的測資太小在補上
3
題意範例： 3個節點 5種組合
4
解法1： 時間目前是超過的，研發中 3個節點 5種組合 以不同的位置做根 1 2 3 2個節點 兩種組合 2個節點 兩種組合 3 1 往回找兩個節點 需要幾種組合
5
解法2：Catalan number 卡塔蘭數
卡塔蘭數是組合數學中一個常在各種計數問題中出現的數列。由以比利時的數學家歐仁·查理·卡塔蘭 命名。 我們可以用直接計算上述公式的方法，也可以在由公式推出下列算式 然後，照著公式去寫
6
解法範例：無 討論： 困難點=>大數問題 不能用上述做法，到7就炸了。 所以，改用struct、class去建造一個linklist。 也可以用array或string的方式用十進位的方式去 儲存。
Similar presentations
