N 個(gè)元素的入棧出棧序列總共有多少種？
我們用 0 表示入棧，1 表示出棧
假設(shè)有 6 個(gè)元素：
則有
0 0 0 0 0 0 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1 0 1
還有其他位置的情況，總共有多種？
我們知道這是一個(gè) 12 位的序列
窮舉有 2 ^ 12 個(gè)序列，有的不能滿足棧的入棧和出棧邏輯
也就是說：
任何一個(gè)元素，首先需要里面有 6 個(gè) 0 和 6 個(gè) 1，然后再統(tǒng)計(jì)包括它在內(nèi)的前的 0 個(gè)個(gè)數(shù)是否小于 1 的個(gè)數(shù)，如果小于則不符合
如果統(tǒng)計(jì)到第 12 個(gè)元素，如果符合，則是正確的序列。（時(shí)間上只需要檢測到第 11 個(gè)元素）
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 : 元素的個(gè)數(shù)
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://m.shnenglu.com/life02/archive/2009/10/17/98851.html
posted on 2011-07-02 13:51
unixfy 閱讀(274)
評(píng)論(0) 編輯 收藏 引用