數(shù)據(jù)結構與算法

數(shù)學上的遞推公式

可以推到得出悲雳，過程較為復雜，此處略過
![][1]
[1]: http://latex.codecogs.com/gif.latex?S_n=\sum_{i=0}^{n-1}S_i*S_{n-1-i}

參看：
<a >卡特蘭數(shù)</a>
以下代碼給出了遞推關系：

int countS(int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return 1;
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += countS(i)*countS(n-1-i);
    }
    return sum;
}
```
## 模擬算法
棧每次有兩種情況：入棧和出棧陈哑，但是，不是每種組合都是合法的伸眶。合法的出棧入棧必須滿足以下條件（１表示入棧惊窖，０表示出棧）：
1. 最終出棧和入棧的次數(shù)一樣，也就是０和１的數(shù)量都等于元素的個數(shù)
2. 棧為空時不能有出棧動作厘贼，也就是在任意時刻界酒，已經(jīng)出現(xiàn)的１必須大于等于０出現(xiàn)的次數(shù)
例如：
１１１０００（合法）
１１０００１（不合法）
模擬生成合法序列的 C++ 代碼如下：

```
#include <iostream>
using namespace std;
int m,a[20] = {1}, count0,count1;
void binSeq(int n) {
//邊界條件，輸出合法的序列嘴秸，其中 m 為一半的數(shù)組長度毁欣。
    if (2*m == n) {
        for (int i = 0; i < 2*m ; i++) {
            cout << a[i];
        }
        cout << endl;
        return;
    }
    //條件判斷庇谆，任意時刻1的個數(shù)小于 m 且大于0的個數(shù)
    if (count1 < m && count1 > count0) {
        a[n] = 1;
        count1++;
        binSeq(n+1);
        count1--;
        a[n] = 0;
        count0 ++;
        binSeq(n+1);
        count0 --;
    }
    //當不能所有的元素均已進行過入棧動作
    else if (count1 == m) {
        a[n] = 0;
        count0++;
        binSeq(n+1);
        count0--;
    }
    //當1和0數(shù)量相等即棧為空時，應入棧
    else if (count0 == count1) {
        a[n] = 1;
        count1++;
        binSeq(n+1);
        count1--;
    }
}
int main() {
    cin >> m;//輸入元素個數(shù)
    count0 = 0;
    count1 = 1;//首先必須入棧
    binSeq(1);
    return 0;
}

```
最后的代碼如下所示：
```
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int Size, PopCount, PushCount;//定義變量
vector < int >operation; // we can use 1 to stand for "push", and 0 for "pop"
stack < int >simulation;
//計算 n 個元素出棧順序的個數(shù)
int countS(int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return 1;
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += countS(i)*countS(n-1-i);
    }
    return sum;
}
//主要函數(shù)凭疮，原理與上面的簡化班函數(shù)相同饭耳，不再寫詳細注釋
void binSeq(int n, int *arr)
{
    if (2 * Size == n) {
    vector < int >::iterator Iter;
    int j = 0;
    for (Iter = operation.begin(); Iter != operation.end(); Iter++) {
        if (1 == (*Iter)) {
        simulation.push(arr[j]);
        j++;
        } else {
        cout << simulation.top() << " ";
        simulation.pop();
        }
    }
    cout << endl;
    return;
    }

    if (PushCount < Size && PushCount > PopCount) {
        operation.push_back(1);
        PushCount++;
        binSeq(n + 1, arr);
        operation.pop_back();
        PushCount--;
        operation.push_back(0);
        PopCount++;
        binSeq(n + 1, arr);
        operation.pop_back();
        PopCount--;
    }
    else if (PushCount == Size) {
        operation.push_back(0);
        PopCount++;
        binSeq(n + 1, arr);
        operation.pop_back();
        PopCount--;
    }
    else if (PopCount == PushCount) {
        operation.push_back(1);
        PushCount++;
        binSeq(n + 1, arr);
        operation.pop_back();
        PushCount--;
    }
}

int main()
{
    cout << "Please input the size of sequence:";
    operation.push_back(1);
    cin >> Size;
    cout << "Please input the size of sequence<int>:\n";
    int seq[Size];
    for (int i = 0; i < Size; i++) {
        cin >> seq[i];
    }
    cout << "The anwser is:\n";
    PopCount = 0;
    PushCount = 1;
    binSeq(1, seq);

    cout << "The number of all cases is : " << countS(Size) << endl;
    return 0;
}
```