題目背景
棧是計算機中經典的數據結構，簡單的說，棧就是限制在一端進行插入刪除操作的線性表。

棧有兩種最重要的操作，即 poppop （從棧頂彈出一個元素）和 pushpush （將一個元素進棧）。

棧的重要性不言自明，任何一門數據結構的課程都會介紹棧。寧寧同學在復習棧的基本概念時，想到了一個書上沒有講過的問題，而他自己無法給出答案，所以需要你的幫忙。

題目描述

寧寧考慮的是這樣一個問題：一個操作數序列， 1,2,…,n1,2,…,n （圖示為1到3的情況），棧 AA 的深度大于 nn 。

現在可以進行兩種操作，

將一個數，從操作數序列的頭端移到棧的頭端（對應數據結構棧的 pushpush 操作）

將一個數，從棧的頭端移到輸出序列的尾端（對應數據結構棧的 poppop 操作）

使用這兩種操作，由一個操作數序列就可以得到一系列的輸出序列，下圖所示為由 1 2 3123 生成序列 2 3 1231 的過程。

（原始狀態如上圖所示）

你的程序將對給定的 nn ，計算并輸出由操作數序列 1,2,…,n1,2,…,n 經過操作可能得到的輸出序列的總數。

輸入輸出格式
輸入格式：
輸入文件只含一個整數 n(1≤n≤18)n(1≤n≤18)

輸出格式：
輸出文件只有 11 行，即可能輸出序列的總數目

輸入輸出樣例
輸入樣例#1： 復制
3
輸出樣例#1： 復制
5
.
.
.
.
.

分析

該問題等價于求第n項的卡特蘭數，
設第n項的卡特蘭數為h(n)h(n)
則h(n)=c(2n,n)?c(2n,n?1)(n=0,1,2,...)h(n)=c(2n,n)?c(2n,n?1)(n=0,1,2,...)
這個是兩個組合數的減法
.
.
.
.
.
.

程序：

#include<iostream> using namespace std; int main() {int n,c[100][100];cin>>n;for (int i=1;i<=2*n;i++) c[i][1]=c[i][i]=1;for (int i=3;i<=2*n;i++)for (int j=1;j<=i-1;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];cout<<c[2*n][n]-c[2*n][n-1];return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/9499898.html

總結

以上是生活随笔為你收集整理的洛谷 P1044 栈 [卡特兰数]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。