N 个元素的入栈出栈序列总共有多少种？
我们用 0 表示入栈，1 表示出栈
假设有 6 个元素：
则有
0 0 0 0 0 0 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1 0 1
还有其他位置的情况，总共有多种？
我们知道这是一个 12 位的序列
穷举有 2 ^ 12 个序列，有的不能满足栈的入栈和出栈逻辑
也就是说：
任何一个元素，首先需要里面有 6 个 0 和 6 个 1，然后再统计包括它在内的前的 0 个个数是否小于 1 的个数，如果小于则不符合
如果统计到第 12 个元素，如果符合，则是正确的序列。（时间上只需要检测到第 11 个元素）
1 #include <iostream>
2 using namespace std;
3
4 bool test(int k, int n)
5 {
6 int count = 0;
7 int temp = k;
8 for (; temp != 0; temp &= temp - 1, ++count);
9 if (count != n)
10 {
11 return false;
12 }
13
14 int zero = 0;
15 int t = n + n - 1; // 只需要检测到 n + n - 2 位
16 for (int i = 0; i < t; ++i)
17 {
18 if ((k & (1 << i)) == 0)
19 {
20 ++zero;
21 }
22 else
23 {
24 if (--zero < 0)
25 {
26 return false;
27 }
28 }
29 }
30 return true;
31 }
32
33 // n : 元素的个数
34 int foo(int n)
35 {
36 int t = 1 << (n + n);
37 int ret = 0;
38 for (int k = 0; k < t; ++k)
39 {
40 if (test(k, n))
41 {
42 ++ret;
43 // 输出
44 cout << ret << ":" << endl;
45 for (int i = 0; i < n + n; ++i)
46 {
47 if ((k & (1 << i)) == 0)
48 {
49 cout << 0 << ' ';
50 }
51 else
52 {
53 cout << 1 << ' ';
54 }
55 }
56 cout << endl;
57 }
58 }
59 return ret;
60 }
61
62 int main()
63 {
64 int n;
65 while (cin >> n)
66 {
67 cout << foo(n) << endl;
68 }
69 return 0;
70 }
http://www.wming.com/a/articles/devlanguage/c/2011/0101/81478_%E6%8E%A8%E8%8D%90%E5%BC%BA%E5%A5%B8%E9%98%BF%E9%87%8C%E5%B7%B4%E5%B7%B4%E4%B8%80%E4%B8%AA%E7%AC%94%E8%AF%95%E9%A2%98.html
http://topic.csdn.net/u/20091017/01/37370E0B-A736-40A5-8839-D8D0B9FCAADA.html
http://hi.csdn.net/baihacker
http://hi.baidu.com/feixue
http://hi.baidu.com/jumay426/blog/item/50b1ca84b5198726c65cc3f8.html
http://www.cppblog.com/life02/archive/2009/10/17/98851.html
posted on 2011-07-02 13:51
unixfy 阅读(256)
评论(0) 编辑 收藏 引用