C#，卡特兰数（Catalan number，明安图数）的算法源代码

一、概要

卡特兰数（英语：Catalan number），又称卡塔兰数、明安图数，是组合数学中一种常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。1730年左右被蒙古族数学家明安图使用于对三角函数幂级数的推导而首次发现，1774年被发表在《割圜密率捷法》。

二、卡特兰数的历史

1730年，中国清代蒙古族数学家明安图比卡特兰更早使用了卡特兰数，在发现三角函数幂级数的过程中，见《割圜密率捷法》。后来他的学生在1774年将其完成发表。
1753年，欧拉在解决凸包划分成三角形问题的时候，推出了卡特兰数。
1758年，Johann Segner 给出了欧拉问题的递推关系。
1838年，拉梅给出完整证明和简洁表达式；欧仁·查理·卡特兰在研究汉诺塔时探讨了相关问题，解决了括号表达式的问题。
1900年，Eugen Netto 在著作中将该数归功于卡特兰。
内蒙古师范大学教授罗见今1988年以及1999年的文献研究表明实际上最初发现卡特兰数的也不是欧拉，而是明安图。
最后，由比利时的数学家欧仁·查理·卡特兰命名。在中国却应当由清代蒙古族数学家明安图命名。

三、应用

1、数字序列的括号化（n对括号正确匹配数目）
2、凸多边形三角划分
3、给定节点组成二叉搜索树
?

四、源代码与改进代码

1、原始代码

/// <summary>
/// 计算第 n 个卡塔兰数
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static ulong CatalanOriginal(int n)
{
	ulong res = 0;
	if (n <= 1)
	{
		return 1;
	}
	for (int i = 0; i < n; i++)
	{
		res += CatalanOriginal(i) * CatalanOriginal(n - i - 1);
	}
	return res;
}

2、计算结果（前64个卡塔兰数）

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, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 9057316177202639132, 10713166123620736856, 16342585076431942214, 2689383809735779348, 5102839245063848452, 11119451935032739784, 14452914362348096668, 14071982300670990120, 11142706294756623192, 3114992555900662896, 16682282172542456626, 11604953028367754716, 10347338891492931260, 6533841209031609592, 17577068357745673116, 11934029089710590568, 3367710287996676216, 1700012784093890096, 9253156062895436676, 11766576147974922296, 7683395182710107672, 16195324623391601584, 15200231439582411976, 13944974943675103408, 15751729141727956688, 14950683510242200608, 7096100506878905693,

:P

如果你直接用上面的代码计算，计算机一定卡死啦！

下面的代码，秒出！

3、程序员写的，不是码农写的代码

/// <summary>
/// 存储所有n之前的卡塔兰数
/// </summary>
private static List<ulong> catalanList = new List<ulong>();

/// <summary>
/// 计算 n 个卡塔兰数的改进算法
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static ulong Catalan(int n)
{
	catalanList.Clear();
	for (int k = 0; k <= n; k++)
	{
		ulong res = 0;
		if (k <= 1)
		{
			catalanList.Add(1);
		}
		else
		{
			for (int i = 0; i < k; i++)
			{
				res += catalanList[i] * catalanList[k - i - 1];
			}
			catalanList.Add(res);
		}
	}
	return catalanList[n];
}

永远记住所谓的程序优化，只有一个原则，就是：用存储换计算！