编者按：
　　本文十分详细的介绍了《栈的计数》这题的两种递推算法，图文并茂，十分适合初学者阅读，并从中领会清晰、严密的分析思路。另外，随文附带的程序十分简洁，值得学习。
　　作为普及组的试题，出题者的意图可能仅仅希望考察选手对搜索和递推算法的掌握，但是，本题作为组合数学Catalan数的经典模型，可以用组合数学的方法快捷高效的求解。类似的利用Catalan数求解的问题有NOI2001福建组队赛《球迷购票问题》等，类似的递推问题还有NOI2000福建组队赛《车皮排序问题》等，希望有能力的同学继续研究。

摘要：
　　　 　　算法一 算法二 算法三
算法　　　　递推 递推 Catalan数
时间复杂度　O(n2) O(n2) O(n)
空间复杂度　O(n) O(n2) O(1)

问题转述：
　　求一列共n辆的火车按顺序通过一个栈所产生的排列总数。

下载全文（Zip压缩包，151KB）