2010-1118

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

由于买船票的人只可能有50元和100元两种钞票，而船票票价为50元，所以买船票只有两种方式，一种是直接支付50元；另一种是支付100元找钱50元。因为售票处一开始没有钱，所以要保证每一个支付100元钱的人都能找到零钱，在他来买票之前，售票厅内必须剩余至少一张50元。这个背景，就让我们自然联想到Catalan数（类似的背景有进栈出栈、括号配对、二叉树的类型等等）。
用C(n)表示第n个Catalan数，则C(1) = 1; C(n) = ((4*n-6)/(n)) * C(n-1);
通过递推公式，我们可以求出从1－5001所有的Catalan数，对于正整数n，问题的答案即为 n * C(n+1)

由于买船票的人只可能有50元和100元两种钞票，而船票票价为50元，所以买船票只有两种方式，一种是直接支付50元；另一种是支付100元找钱50元。因为售票处一开始没有钱，所以要保证每一个支付100元钱的人都能找到零钱，在他来买票之前，售票厅内必须剩余至少一张50元。这个背景，就让我们自然联想到Catalan数（类似的背景有进栈出栈、括号配对、二叉树的类型等等）。

用C(n)表示第n个Catalan数，则C(1) = 1; C(n) = ((4*n-6)/(n)) * C(n-1);

通过递推公式，我们可以求出从1－5001所有的Catalan数，对于正整数n，问题的答案即为 n * C(n+1)