Catalan数的一些应用

电玩女神 2022-06-09 10:30 211阅读 0赞

Catalan数：  
令h(0)=1,h(1)=1，catalan数满足递归式：  
h(n)= h(0)\*h(n-1) + h(1)\*h(n-2) + ... + h(n-1)h(0) (其中n>=2),这是n阶递推关系;  
还可以化简为1阶递推关系: 如h(n)=(4n-2)/(n+1)\*h(n-1)(n>1) h(0)=1  
该递推关系的解为：h(n)=C(2n,n)/(n+1) = P(2n,n)/(n+1)! = (2n)!/(n!\*(n+1)!) (n=1,2,3,...)  
  
  
前几项为：  
0：1,  
1：1,  
2：2,   
3：5,   
4：14,   
5：42,   
6：132,   
7：429,   
8：1430,  
9：4862,   
10：16796,   
11：58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …  
  
  
应用有许多：  
1，标准二维表问题  
设 n 是一个正整数, 2\*n 的标准二维表是由正整数 1, 2, ..., 2\*n 组成的2\*n 数组, 该数组的每行从左到右递增, 每列从上到下递增. 2\*n 的标准二维表全体记为 Tab(n). 譬如: 当 n = 3 时 Tab(3) 如下:   
123   124   125  134  135  
456   356   346  256  246  
  
  
2，乘法的次序可能数  
矩阵链乘： P=a0×a1×a2×a3×……×an，共有（n+1）项，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)  
  
  
3，出栈顺序次数问题  
一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?  
  
  
下面的代码是出栈顺序问题的求解，  
输入n，则输出所有进出栈顺序的可能，使用了回溯法。  
如输入2：  
则输出：  
1：+ + - -  
2：+ - + -  
其中 + 代表进栈， -代表出栈

// StackSquence.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    #include <vector>
    
    //#include <stack>
    
    using namespace std;
    
    int num=0; //当前栈中元素个数
    int numOfIn=0; //进栈次数
    //string path=""; //当前路径
    int n = 6;
    int k=0;
    vector<string> path;
    
    void backtrack( int i )
    {
    	if( i> 2*n) 
    	{
    		cout << ++k <<":  ";
    		for( int j=0; j<2*n; j++)
    			cout << path[j];
    		cout << endl;
    		return;
    	}
    
    	//进栈子节点
    	if( numOfIn < n )
    	{	
    		path.push_back("+  ");
    		numOfIn++;
    		num++;
    		backtrack(i+1);
    		path.pop_back();
    		numOfIn--;
    		num--;
    	}
    
    	//出栈子节点
    	if( num > 0 )
    	{
    		path.push_back("- ");
    		num--;
    		backtrack(i+1);
    		path.pop_back();
    		num++;
    	}
    
    
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	while(1)
    	{
    		k=0;
    		cin >> n;
    		backtrack(1);
    	}
    	return 0;
    }