• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 183,  comments - 10,  trackbacks - 0

            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è)序列,有的不能滿(mǎn)足棧的入棧和出棧邏輯
            也就是說(shuō):
            任何一個(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í)間上只需要檢測(cè)到第 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;    // 只需要檢測(cè)到 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)  編輯 收藏 引用

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            亚洲国产成人精品女人久久久 | 九九久久精品无码专区| www.久久精品| 99久久婷婷国产综合精品草原| 91麻精品国产91久久久久| 午夜精品久久久内射近拍高清| 2021最新久久久视精品爱| 亚洲精品午夜国产VA久久成人| 久久电影网2021| 2021国产精品午夜久久| 99精品久久精品一区二区| 日本久久中文字幕| 久久99国产精品99久久| 久久久无码精品亚洲日韩京东传媒| 久久se精品一区二区| 香蕉久久av一区二区三区| 久久99精品久久久久久野外| 久久99国产综合精品| 欧美亚洲国产精品久久久久| 日本道色综合久久影院| 天天躁日日躁狠狠久久| 欧美成人免费观看久久| 久久国产综合精品五月天| 国产精品久久波多野结衣| 亚洲欧美伊人久久综合一区二区| 久久成人18免费网站| 日本福利片国产午夜久久| 国产精品99久久精品| 亚洲国产精品18久久久久久| 亚洲精品午夜国产va久久| 性做久久久久久免费观看| 久久精品综合一区二区三区| 国产亚州精品女人久久久久久 | 久久久无码精品午夜| 成人久久综合网| 久久精品国产亚洲AV无码偷窥| 亚洲中文精品久久久久久不卡| 中文字幕久久亚洲一区| 亚洲色欲久久久久综合网| 一级做a爰片久久毛片看看| 中文字幕无码久久精品青草|