实习总结 十六期

关于实习准备的内容似乎已基本完成，暂时难以再补充更多内容，因此决定撰写有关卡特兰数的部分，该内容在笔试过程中也有所涉及。
定理：由n个+1与n个-1组成的2n项序列中，所有满足部分和始终大于等于0的序列数目即为第n个卡特兰数。

卡特兰数的通项表达式为：

归纳来看，最为常见的四类应用场景包括：

1. 括号匹配问题
   矩阵链相乘：P=a1×a2×a3×……×an，根据乘法结合律，不改变原有顺序，仅通过括号表示成对的乘积方式，问共有多少种括号匹配的可能？(即为第n个卡特兰数)
   类似问题包括：由n对括号构成的有效匹配字符串数量；
   n+1个数值相乘时，所有可能的括号插入方式数目；
   出栈顺序问题
   假设有一个容量无限的栈，进栈序列为1,2,3,...,n，则有多少种不同的出栈排列方式？(即为第n个卡特兰数)
   类似场景：有2n个人依次进入剧场。门票价格为5元。其中恰好有n人持有5元纸币，其余n人仅持有10元纸币。剧院没有其他面值的纸币。试问有多少种入场方式能够确保每位持10元纸币的人购票时都能获得5元找零？(将持5元者到达视为将5元入栈操作，持10元者到达则视为使某张5