作者tkcn (小安)
看板Prob_Solve
標題Re: [問題] CS touring center : stepping stone (遞迴？)
時間Tue Mar 29 00:03:57 2011
※ 引述《KitWoolsey (難得好天氣)》之銘言：
: 其實這站很多歸類於程式題的好像都會被數學做法秒殺....
: 這題的話，當n=2 時應該就是等價於高中排列組合學的
: ＂兩候選人開票 Ａ票數一路領先Ｂ的方法數＂此類題目 是有公式解的
說得非常正確，這叫作 Catalan Number，
不只是一路領先問題，其他的應用也非常多，
如果你繼續寫這些題目，相信未來還很有機會遇到。
建議把各種應用讀一下
http://en.wikipedia.org/wiki/Catalan_number
: 其實以前我就有想過要是不只兩個人怎麼辦....不過一直沒有得到解答
: 也有請教ㄧ些學長 不過好像也沒什麼想法＠＠
: 所以我猜這題沒有數學做法（？）不過應該有遞迴式....但我想不太到@@@@?
Catalan Number 可以延伸至多維:
http://oeis.org/A060854
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
1F：推 KitWoolsey: (￣▽￣＃)/ 03/29 00:10
2F：→ KitWoolsey:@@ 按錯 = = 03/29 00:10
3F：→ KitWoolsey:感謝回應 我打包回去仔細瞧瞧@_@ 03/29 00:10
4F：推 ledia:推 A060854 ... XD 03/29 09:09
5F：推 ledia:程式題用 bc 還真好解 03/29 09:11
6F：推 miraculouswi:這東西沒有遞迴公式(就人數而言和票數而言都一樣) 03/30 23:34
7F：→ miraculouswi:例如三個人開票是Motzkin numbers 03/30 23:36
8F：推 KitWoolsey:看半天找不到多維的有什麼推倒ＱＱ 03/31 21:15
9F：→ KitWoolsey:代值進去過了 不過還是搞不懂qqqqq 03/31 21:16
10F：→ tkcn:要推導什麼? 證明? 可以先看 2 維(catalan), 3 維 03/31 22:57
11F：推 KitWoolsey:2維的看完了 3維以上的呢@@@ 04/01 00:53
12F：推 miraculouswi:三維以上的可以看RP Stanley的Enumerative Combinato 04/01 03:18
13F：→ miraculouswi:-rics, 裡面有到五個人的公式,他長的很醜而且數學家 04/01 03:19
14F：→ miraculouswi:已經大致上接受他就是長那麼醜,推導用表現理論,很難 04/01 03:20
15F：→ miraculouswi:我的研究領域是這一個category,最近在寫paper這樣 04/01 03:22
16F：→ miraculouswi:講那麼多就是想勸你放棄推導他XD除非你想花時間徹底 04/01 03:24
17F：→ miraculouswi:研究類似的東東~如果還有相關問題很樂意回答=) 04/01 03:25
18F：推 KitWoolsey:噢@@@@ 感謝^^" 04/02 00:57