切換
舊版
前往
大廳
主題

ZeroJudge - e876: Q1 - 配對連線　解題心得

Not In My Back Yard | 2020-04-19 02:10:39 | 巴幣 0 | 人氣 168
題目連結：
題目大意：
每列給定一正整數 N （1 ≦ N ≦ 100，N ＝ 0 時代表輸入結束），代表一個圓上現在有 2N 個點。將這 2N 個點兩兩配對並用線將兩點連起，形成 N 條線段。請問有多少種配對畫線的方式，使得這 N 條線段彼此不互相交叉？

範例輸入：
1
2
3
0
範例輸出：
1
2
5
解題思維：
觀察以下有 12 個點（n ＝ 6）的圓：
可以看到對於最頂端的那個點（放射線狀的出發點），總共有 11 條線可以連去其他的點。假設現在挑的是實線的那一條（位於中間的線段），於此將圓分作左右兩邊，兩邊各 5 個點。可以看到剩下的兩邊各自連線一定至少會有左邊一點接到右邊一點，就會跨到中間的線。

但是如果現在是挑中間的線的左邊那一條（最靠近中間的並屬於左邊的那一條線段），將會把左右兩邊分為 4 、 6 個點，可以對應到 n ＝ 2 以及 n ＝ 3 的情況。也就是對於這個分割線的挑法，其方法數為 （n ＝ 2 的方法） × （n ＝ 3 的方法） 。

類似的，可以找到其他的方法數為（n ＝ 1 的方法） × （n ＝ 4 的方法）、（n ＝ 0 的方法） × （n ＝ 5 的方法）、（n ＝ 3 的方法） × （n ＝ 2 的方法）、（n ＝ 4 的方法） × （n ＝ 1的方法）、（n ＝ 5 的方法） × （n ＝ 0 的方法）

假設 Di 代表 n ＝ i 的方法數（n ＝ 0 的方法數在此計為 1），則上面的性質可寫為
可以看到這等價於以前提過的卡塔蘭數（Catalan Number）。但是因為 n 可以到 100 ，使得方法數的值可以很大。因此需要大數運算。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#大數#數學#排列組合
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

相關創作

達人 春節加碼？ 從期望值來看賓果賓果能玩嗎？
15 1076
【數學】排列組合之組合表達式
0 77
鳥鳥玩數學-比較複雜的階梯問題(三種解法)(101中科實中教甄)
0 242
鳥鳥玩數學-試著用列舉的方法解錢包裡的錢可以換多少種款項(國小也能學得解法)
0 160
【zerojudge】c031. 00264 - Count on Cantor
0 39
達人 數學心得：314 國際數學日 圓周率日
7 754
【zerojudge】c002. 10696 - f91
0 53
【zerojudge】b901+d715 階乘最後一位非零數
0 87
分享一道男生特別有感的排列組合難題
0 132
達人 霧島簡評113學測數學A
16 1370
08. 給初學者練習PGA2D運用邏輯的網頁小遊戲
0 52
【zerojudge】b810 - 九○七四二的問題之(二)
0 78
達人 這題有錯！112 數學A 模擬考—「已知一點與兩角平分線，求原三角形」
6 654
達人 介紹數學遊戲 Renzoku 連續 - 離散世界的「連續」
16 642
【隨筆】六邊形球體
3 194
數學少女的啟發
0 118
07. PGA2D，點與線的表示法
0 61
惡作劇隨筆系列2
0 60
達人 錯誤的學習數學心態與方法
33 1558
達人 書評：數學女孩秘密筆記：圖形的證明 – 為何要證明？
14 1067

更多創作

追蹤 創作集
其他創作
作品資料夾