【栈】射击游戏（待更新）

Description

小明很喜欢玩射击游戏。这周末，他完成了数据结构作业之后，又来到了射击娱乐场。他从老板那租了一把步枪和装有N发子弹的弹夹。注意：所有的子弹都从枪口上膛。在射击的过程中，小明每次都有两种选择：从弹夹中取出一颗子弹上膛，或者打一发子弹出去。恰巧，这周二，小明刚上了数据结构中《栈》那一章，于是，他想通过“栈”的数据结构来算出究竟有多少种不同的子弹打出顺序。假设N颗子弹的编号为1,2,…,N。子弹从弹夹中取出的顺序也是从1到N。你可以帮小明解决这个问题吗？

Input

可能有多个测试输入，第一行给出总共的测试输入的个数。

对于每个测试输入，只有一个整数N。

Output

输出一个整数，即所有不同序列的总数目。

Sample Input

Copy sample input to clipboard

Sample Output

Problem Source: 课程上机练习题

解题思路：

法一：公式法2n!/((n+1)n!n!)

#include<iostream>
using std::cout;
using std::cin;
using std::endl;

int main() {
    long long int T, n, tmp1, tmp2, i;
    cin >> T;
    for (; T > 0; T--) {
        cin >> n;
        for (i = 2 * n, tmp1 = 1; i >= (n + 2); i--) tmp1 *= i;
        for (i = n, tmp2 = 1; i >= 1; i--) tmp2 *= i;
        cout << (tmp1 / tmp2) << endl;
    }
}

法二：待更新

#include<iostream>
using namespace std;

int f(int n, int m) {
    if (n == 0)
        return 1;
    if (m == 0)
        return f(n-1, 1);
    return f(n, m-1)+f(n-1, m+1);
}


int main() {
    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        cout << f(n, 0) << endl;
    }
}

（本博文或多或少参考过其他网上资料，但时间已久忘记当初的参考了，在此对他们表示感谢！）

越努力越幸运～