Posted on 2006-10-02 20:16
魔のkyo 阅读(889)
评论(1) 编辑 收藏 引用
n个元素顺序入栈(堆栈),问有多少种出栈方式!
例如n=3时，有
push push push pop pop pop
push push pop push pop pop
push push pop pop push pop
push pop push push pop pop
push pop push pop push pop
5种方式。
我本以为找不到有限的数学表达式，于是先写了一个程序用回溯法（剪枝深搜）的思想
#include <stdio.h>
void f(int d);
void Init();
int n,stack_size,ways,i,a[100];
int main ()
{
while(1){
printf("Input n:");
scanf("%d",&n);
if(!n)break;
Init();
f(0);
printf("%d sorts of orders\n",ways);
}
}
inline void Init()
{
stack_size=ways=i=0;
}
void f(int d){
if(d==2*n){
ways++;
for(int i=0;i<2*n;i++){
if(a[i]){
printf("push ");
}
else {
printf("pop ");
}
}
putchar('\n');
}
else {
if(i<n){
stack_size++;
i++;
a[d]=1;
f(d+1);
i--;
stack_size--;
}
if(stack_size>0){
stack_size--;
a[d]=0;
f(d+1);
stack_size++;
}
}
}
今天在知道，原来可以找到数学表示，就是Catalan数。
定义：n个+1和n个-1构成的2n项
a1,a2,...,a2n
其部分和满足
a1+a2+...+ak>=0 (k=1,2,...2n)
的数列的个数等于第n个Catalan数
Cn=(2n C n)/(n+1) (n>=0)
(2n C n)表示(2n)!/(n!×n!)