欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【洛谷】P1044 栈

程序员文章站 2022-07-13 11:51:54
...

点击进入【洛谷】P1044 栈

【洛谷】P1044 栈

【洛谷】P1044 栈

【洛谷】P1044 栈


卡特兰数数学原理:
【洛谷】P1044 栈


算法分析:

  • 假设[1…n]有序序列经过一番压栈出栈操作后,数字k是最后一个出栈元素
  • 数字k将整个序列分成了两部分,[1…k-1]均先于k进行操作,[k+1…n]均晚于k进行操作
  • 整个过程可以描述为:在k压栈之前[1…k-1]个元素已经全部压栈并出栈完毕,然后k压栈,存于栈底,之后[k+1…n]个元素同样进行压栈并全部出栈,剩下了k依然留在栈底,最后k才出栈。
  • 如果记i个元素最终获得的序列为f(i)种,则前[1...k-1]个元素为f(k-1)种,后[k+1...n]元素为f(n-k)种,因为前后两部分元素压栈出栈相互独立,可以直接使用乘法原理,则f(k-1)*f(n-k)
  • f(k-1)*f(n-k)表示当第k个元素最后出栈时,共有f(k-1)*f(n-k)种可能
  • 当第 1 个元素最后出栈时,共有f(0)*f(n-1)
  • 当第 2 个元素最后出栈时,共有f(1)*f(n-2)
  • 当第 3 个元素最后出栈时,共有f(2)*f(n-3)
  • 当第n-1个元素最后出栈时,共有f(n-2)*f(1)
  • 当第 n 个元素最后出栈时,共有f(n-1)*f(0)
  • 因此,n个元素的序列,共有f(n)=f(0)*f(n-1) + f(1)*f(n-2) + ....+ f(n-2)*f(1) + f(n-1)*f(0)种可能

总结出递推公式:

  • f(0) = 1;
  • f(1) = 1;
  • f(2) = f(0)*f(1) + f(1)*f(0);
  • f(3) = f(0)*f(2) + f(1)*f(1) * f(2)*f(0);
  • f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ....+ f(n-2)*f(1) + f(n-1)*f(0)

算法设计:
使用数组f[N]存储n个元素的序列压栈出栈操作结果种数,f[0] = 1, f[1] = 1, 然后利用递推公式,循环求出其他值


代码实现:

int main()
{
	int n;
	int f[20] = {0};
	f[0] = 1;
	f[1] = 1;
	
	scanf("%d", &n);
	for(int i=2; i<=n; i++)
		for(int j=0; j<i; j++)
			f[i] += f[j]*f[i-1-j];
	printf("%d", f[n]);
	
	return 0;
}