作者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