首页 > 代码库 > SOJ【栈】射击游戏(递推思想)
SOJ【栈】射击游戏(递推思想)
Description
小明很喜欢玩射击游戏。这周末，他完成了数据结构作业之后，又来到了射击娱乐场。他从老板那租了一把步枪和装有N发子弹的弹夹。注意：所有的子弹都从枪口上膛。在射击的过程中，小明每次都有两种选择：从弹夹中取出一颗子弹上膛，或者打一发子弹出去。恰巧，这周二，小明刚上了数据结构中《栈》那一章，于是，他想通过“栈”的数据结构来算出究竟有多少种不同的子弹打出顺序。假设N颗子弹的编号为1,2,…,N。子弹从弹夹中取出的顺序也是从1到N。你可以帮小明解决这个问题吗？
Input
可能有多个测试输入，第一行给出总共的测试输入的个数。
对于每个测试输入，只有一个整数N。
Output
输出一个整数，即所有不同序列的总数目。
Sample Input
3
Sample Output
5
解题想法：
利用递推的思想去考虑这道题：假设现在我有五颗子弹，即d5，我们现在要在d4（四颗子弹的情况上）考虑这个第五颗子弹的位置能放哪里。画图如下：
同理，可以发现只能放在4的前一位和后面所有插入位。
以此类推我们可以得出，当4出现在1号位置时，5有5种插入位置；
当4出现在2号位置时，5有4种插入位置；
当4出现在3号位置时，5有3种插入位置；
当4出现在4号位置时，5有2种插入位置；(至少有两种插入位置)
现在我们要考虑d4与d3的关系了，因为4在不同位置出现的次数(d4)直接对d5产生影响。
同理，我们可以得出当3出现在1号位置时，4有4种插入位置；
当3出现在2号位置时，4有3种插入位置；
当3出现在3号位置时，4有2种插入位置；
d3与d2的关系: 当2出现在1号位置时，3有3种插入位置；
当2出现在2号位置时，3有2种插入位置；
d2与d1的关系: 当1出现在1号位置时，2有两种插入位置；
那么现在我们要做的是如何把这些关系用数学式子表示呢？笔者比较菜，只想到数学的加法算式，
: XX
+ XXX
:+ XXXX
----------------- n-1次加法运算,X为n能插入该位置的次数
为什么想到这个算式呢？举个列子：d3有5种情况：
123，132，213，231，321，
而3在位置1出现1次，位置2出现2次，位置3出现2次;
而出现d2 = 21的排列顺序在d3这里有3种：213,231,321
出现d2 = 12的顺序在d3这里有2种：123,132,列个竖式来观察就清晰了
X2 X2
+ X1 X1 X1
位置1 位置2 位置3
而X1为d2中出现21的次数，X2为d2中出现12的次数，X1=X2=1
而3在位置1出现1次，位置2出现2次，位置3出现2次;正确表示
这种竖式表示使dn与dn-1乃至d2，d1的关系明显化。现在我们可以很容易表示d5了:
11
111
122
22
222
1111
1355
55
555
3333
11111
149(14)(14)
所以d5次数有1+4+9+14+14=42；
给出相应代码(本人菜鸟，难免代码难看，若有想法的可以在评论贴出代码，一起学习哈)
1 #include<iostream> 2 using std::cout; 3 using std::cin; 4 using std::endl; 5 6 7 int main() { 8 int n, t; 9 cin >> t;10 while (t--) {11 cin >> n;12 int s[500] = {0};13 int d[500][500] = {0};14 long long int sum = 0;15 s[1] = 1;16 for (int k = 2; k <= n; k++) {17 for (int i = 1; i < n; i++) {18 for (int j = 1; j <= i + 1; j++) {19 d[i][j] = s[i];20 }21 }22 for (int i = 1; i < n; i++) {23 s[i] = 0;24 }25 for (int j = 1; j < n; j++) {26 for (int i = 1; i < n; i++) {27 s[j] += d[i][j];28 }29 }30 s[k] = 1;31 }32 for (int i = 1; i <= n; i++) {33 sum+= s[i];34 }35 cout << sum << endl;36 }37 return 0;38 }
SOJ【栈】射击游戏(递推思想)