Description
栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。
Input
就一个数n(0<n<20)。
Output
一个数，即可能输出序列的总数目。
Sample Input
3
Sample Output
5
Solution 1st:
a[i][j] renotes the possible number of the previous j sequences with n = i
(we set a[k][0] = 1 (0 < k <= n), which implies NULL is thought of one possible sequence)
we init that a[1][1] = a[1][0] = 1;
yeild:
a[i][0] = a[i - 1][0];
a[i][j] = a[i][j - 1] + a[i - 1][j]; (1 <= j <= i - 1)
a[i][i] = a[i][i - 1];
the answer wo want to get is a[n][n].
1
#include<iostream>
2using namespace std;
3
4#define MAXN 20
5
6int main()
7
{
8
// init
9 int a[MAXN][MAXN];
10 a[1][1] = a[1][0] = 1;
11
12 // input the total number pushed into the stack(0 < n && n < 20)
13 int n, i, j;
14 cin >> n;
15
16 // run
17 for(i = 2; i <= n; i++)
18
{
19 a[i][0] = a[i - 1][0];
20 for(j = 1; j <= i - 1; j++)
21 {
22 a[i][j] = a[i][j - 1] + a[i - 1][j];
23
}
24 a[i][j] = a[i][j - 1];
25 }
26
27 // ouput the number of possible sequences poped from the stack
28 cout << a[n][n] << endl;
29
30 return 0;
31
}
Solution 2nd:
denote a[n] the number of possible sequences poped from the stack,
denote i the number of the set si poped before the first number pushed '1' poped,
and denote i the number of the set sj poped after the first number pushed '1' poped,
then we can easily get the conlusion that no number in seti is bigger than any number in setj,
we can depart the sequence into two part and caculate them respectively,
hence the possible number is a[i] * a[j] (0 <= i <= n - 1), i.e.
a[n] = a[0]*a[n - 1] + a[1]*a[n - 2] + …… + a[n - 2]*a[1] + a[n - 1]*a[0]
1
#include<iostream>
2
using namespace std;
3
4
#define MAXN 20
5
6
int main()
7
{
8
int a[MAXN];
9
a[0] = 1;
10
int n, i, j;
11
cin >> n;
12
for(i = 1; i <= n; i++)
13
{
14
for(a[i] = 0, j = 0; j < i; j++)
15
a[i] += a[j] * a[i - 1 - j];
16
}
17
for(i = 1; i <= n; i++)
18
cout << "a[" << i << "] = " << a[i] << endl;
19
return 0;
20
}
Solution 3id:
This is Catalan Number :
a[n] = a[0]*a[n - 1] + a[1]*a[n - 2] + …… + a[n - 2]*a[1] + a[n - 1]*a[0]
a[n] = C(n , 2 * n) / (n + 1)