经典算法题（三）——Catalan数列

1.四个人过河，用时间分别为1，2，5，10，最多只能两个人同时过河，且过河需要手电筒（只有一个），问怎样才能最快过河2.有一个函数intf(intn)，编写代码检测它是不是总是输出03.25匹马比赛，5匹马为一组，如何最快的比赛得到速度最快的前三名马，需要几次（无法计时，假设一马匹的速度保持不变）4，用两个栈模拟队列先进先出，模拟其add和romve功能，给出思路和代码
5.一景区需要门票5元，售票员没有零钱，假设这一天会来2N个人，其中N个人会给5元钱，N个人给10元，问所有人都不需要等待的概率是多少
属于卡特兰数列问题：
h(n)=C(2n,n)/(n+1)(n=0,1,2,…)（其前几项为:1,1,2,5,14,42,132,429,1430）
解：下列问题都是Catalan数列:
1.有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？2.一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路
3.在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
4.n个结点可够造多少个不同的二叉树?
5.一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?