Knight.Liao's Tale

今天晚上小妹问我一个问题，

“有一个随意的数组，一个栈，一个队列。现将数组内的元素随机进栈或进队列，等数组中所有元素均在栈中与队列中时，开始出栈和出队列。问题是：这样形成的序列总数有多少种？”

对于这个问题，我现在还没有很确切的解答。要解决这个问题，需先了解如果单独只有栈时，序列有多少种的解决方法。因此，我也花了些时间在“出栈序列”种类问题上，从而发现了非常有趣了“Catalan数”。

【对于小妹的问题，我已经在8月31号做出了解答，用程序模拟出来了。可以发现得出来的序列并不是全排列，是介于栈与全排列之间的序列】

在中文维基上[1]，它是这么来定义的：

卡塔兰数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。

卡塔兰数的一般项公式为

前几项为 （OEIS中的数列A000108）: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

继续阅读

Catalan数

梯度、方向導數與切平面

如果一个屋子里面有20个人，那么其中两个人生日相同的可能性是50%么？

其实这个现象有个名字——叫做生日悖论，在不少领域里都非常有用（如密码学和散列算法）。您可以自己试验一下——下次你参加一个二三十人规模的聚会时，问问他们每个人的生日。这群人中很可能有两人生日相同。这总能让人大吃一惊！

这个现象之所以如此让人吃惊，是因为我们常常拿自己的生日和别人比较。比如，您遇到一个人，问他生日是哪天，你们两人生日相同的概率只有1/365(0.27%)。也就是说，任意两人生日相同的概率非常小。即使您问了20个人，概率还是很低——不到5%。所以，我们觉得遇到和自己生日相同的人很不常见。

然而，一个屋子里有20个人，情况就不同了，这20个人中的每个人都会问其余 19个人的生日。每个人都只有很小的可能性与别人生日相同（不到 5%），但是每个人都问了19次，这就极大增加了概率。

如果想计算出精确概率，您可以这样做。假设您有一个很大的挂历，上面包括全部365天。您走过去，在您的生日上划个大大的X。第二个走过去的人就只有364 个未标的日期可供选择，所以生日不同的概率是364/365。第三个走过去的人就只有363个未标日期，所以生日不同的概率为 363/365。如果您将所有20人生日都不相同的概率乘起来，就会得到：

364/365×363/365×...（365-20+1)/365=生日不同的概率

这是生日不同的概率，所以有相同生日的概率就是1减去那个数字。

假设一组里有30个人，算算这个概率是多少！

	double dBirthdayProbety= 1.0;
	for(int i = 364;i>=365-20+1;--i)
	{
		dBirthdayProbety *= i/365.0;
	}
	std::cout << 1 - dBirthdayProbety <<  std::endl;

可以计算出来，如果一间屋子里有23个人，那么两个人同天生日的概率会超过50%。
再加一个：赤道是地球的腰带，它的长近似等于4万千米，假设这条腰带长出1米 那么它与地球表面之间有多大的空隙：1/(2*pai) = 16cm

Reference：

http://hi.baidu.com/larefa/blog/item/e4e9b3507c350265843524b4.html
第一次修改于 2010年9月11日