Description

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

Input

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

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

Output

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

Sample Input

 Copy sample input to clipboard

13

Sample Output

5

Problem Source: 课程上机练习题

解题思路：

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

#include
     
      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
     
      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;    }}
     

 

 

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