• <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>

            生成排列的算法(POJ - 1256 和 POJ百練 - 1833)

            題目1描述:
            輸入:一個(gè)序列s,該序列里面可能會(huì)有同樣的字符,不一定有序
            輸出:打亂輸入中的序列,可能產(chǎn)生的所有新的序列
            題目2描述:
            輸入:一個(gè)序列s,該序列里面可能會(huì)有同樣的字符,不一定有序 和 一個(gè)整數(shù)k
            輸出:該序列往后計(jì)算第k個(gè)序列,所有序列是以字典序排序的

            如果會(huì)有序搜索的童鞋自然而然能立刻做出來(lái)第一個(gè)題目,可是第二個(gè)題目在s較長(zhǎng)的情況下,卻需要用模擬而不是搜索...
            大家都知道STL里面有個(gè)泛函模版, prev_permutation和next_permutation,用法也很簡(jiǎn)單,實(shí)現(xiàn)的就是題目2的功能...
            但是算法最好得靠自己想出來(lái),自己想出來(lái)的才是自己的,碰到新的問(wèn)題才能產(chǎn)生思想的火花...

            廢話少說(shuō),題目1的解法就是深搜,不過(guò)需要加上一個(gè)bool數(shù)組標(biāo)記和一個(gè)函數(shù)確定不同字符之間的大小(有可能這個(gè)大小還不是Ascii碼就能決定的),
            大致描述下搜索過(guò)程,比如輸入序列是12345,那么我搜索的過(guò)程大致是第一層按順序選取1-5,進(jìn)入第二層的時(shí)候也是按順序選取1-5,
            以此類推,但是每一層里面都只能選前面的層次沒(méi)有選過(guò)的數(shù),而且因?yàn)橛兄貜?fù)字符,算法還必須保證每一層里面按順序選取的字符必須是升序的,
            熟悉順序搜索和回溯的同學(xué),很自然就會(huì)產(chǎn)生這樣的想法...
            POJ - 1256的代碼如下:
            #include <stdio.h>
            #include <string.h>
            #include <ctype.h>
            #include <stdlib.h>
            #include <algorithm>
            #define MAX (13 + 10)
            using namespace std;
            bool bUsed[MAX];
            char szAns[MAX];
            char szInput[MAX];
            bool CmpChar(char chOne, char chTwo)
            {
                if (abs(chOne - chTwo) != 'a' - 'A')
                {
                    return tolower(chOne) - tolower(chTwo) < 0;
                }
                return chOne - chTwo < 0;
            }
            bool Greater(char chOne, char chTwo)
            {
                if (abs(chOne - chTwo) != 'a' - 'A')
                {
                    return tolower(chOne) - tolower(chTwo) > 0;
                }
                return chOne - chTwo > 0;
            }
            void Gen(int nDepth, int nLen)
            {
                if (nDepth == nLen)
                {
                    szAns[nLen] = '\0';
                    printf("%s\n", szAns);
                    return;
                }
                
                char chLast = '\0';
                for (int i = 0; i < nLen; ++i)
                {
                    if (!bUsed[i] && Greater(szInput[i], chLast))
                    {
                        bUsed[i] = true;
                        szAns[nDepth] = szInput[i];
                        Gen(nDepth + 1, nLen);
                        bUsed[i] = false;
                        chLast = szInput[i];
                    }
                }
            }
            int main()
            {
                int nCases;
                
                scanf("%d", &nCases);
                while (nCases--)
                {
                    scanf("%s", szInput);
                    int nLen = strlen(szInput);
                    sort(szInput, szInput + nLen, CmpChar);
                    Gen(0, nLen);
                }
                
                return 0;
            }
            題目2的解法是模擬,功能類似與STL的那2個(gè)泛型模版函數(shù),算法的大致過(guò)程是想辦法從當(dāng)前序列進(jìn)入下一個(gè)剛好比其大或者剛好比其小的序列...很自然我們想到要把序列后面大的字符交和前面小的字符交換就會(huì)使序列變大,為了使其剛好變大,可以把交換后的字符從交換位置起至最后都排序一下,現(xiàn)在的問(wèn)題是我們?nèi)绾芜x取2個(gè)字符交換...正確的想法是,我們從最后面開(kāi)始往前面看,尋找一個(gè)最長(zhǎng)的遞增序列,找到之后,我們只需要選取遞增序列前面的那個(gè)字符chBefore和遞增序列里面的一個(gè)最小的比chBefore大的字符交換即可...交換之后,將新的遞增序列排序一下即可...
            為什么這樣做了,因?yàn)閺暮笸翱吹倪f增序列,是不能交換2個(gè)字符讓當(dāng)前序列變大的,所以必須選取最長(zhǎng)遞增序列前面的那個(gè)字符交換...

            POJ百練 - 1833 的代碼如下:
            #include <stdio.h>
            #include <string.h>
            #include <algorithm>
            #define MAX (1024 + 10)
            using namespace std;
            int nInput[MAX];
            void GetNext(int* nInput, int nLen)
            {
                int i = nLen - 2;
                while (i >= 0)
                {
                    if (nInput[i] >= nInput[i + 1])
                    {
                        --i;
                    }
                    else
                    {
                        int k = i + 1;
                        for (int j = nLen - 1; j > i; --j)
                        {
                            if (nInput[j] > nInput[i] && nInput[j] < nInput[k])
                            {
                                k = j;
                            }
                        }
                        swap(nInput[i], nInput[k]);
                        sort(nInput + i + 1, nInput + nLen);
                        return;
                    }
                }
                
                sort(nInput, nInput + nLen);
            }
            int main()
            {
                int nCases;
                scanf("%d", &nCases);
                while (nCases--)
                {
                    int nLen;
                    int nK;
                    scanf("%d%d", &nLen, &nK);
                    for (int i = 0; i < nLen; ++i)
                    {
                        scanf("%d", &nInput[i]);
                    }
                    for (int i = 0; i < nK; ++i)
                    {
                        GetNext(nInput, nLen);
                    }
                    for (int i = 0; i < nLen; ++i)
                    {
                        printf("%d%s", nInput[i], i == nLen - 1 ? "\n" : " ");
                    }
                }
                return 0;
            }

            posted on 2011-12-26 15:53 yx 閱讀(1515) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 搜索模擬

            <2011年12月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            導(dǎo)航

            統(tǒng)計(jì)

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學(xué)

            網(wǎng)友

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久久久se色偷偷亚洲精品av| 久久精品国产精品国产精品污 | 欧美精品福利视频一区二区三区久久久精品 | 久久国产成人| 久久婷婷午色综合夜啪| 久久久亚洲欧洲日产国码aⅴ| 国产美女久久久| 7777久久久国产精品消防器材| 色综合久久中文色婷婷| 国内精品人妻无码久久久影院导航| 久久婷婷五月综合色高清| 色欲综合久久躁天天躁| 国产亚洲欧美成人久久片 | 91精品国产91久久久久福利| 九九久久精品无码专区| 天天爽天天狠久久久综合麻豆 | 伊人久久大香线蕉亚洲五月天| 亚洲精品高清国产一久久| 精品久久久无码21p发布| 色综合久久88色综合天天| 久久国产AVJUST麻豆| 99久久精品免费国产大片| 一本一本久久A久久综合精品 | 久久精品国产一区| 久久久免费精品re6| 久久久久亚洲国产| 久久露脸国产精品| 久久人人爽人人爽人人片AV麻豆| 99久久国产综合精品成人影院| 精品国产乱码久久久久久1区2区| 久久九九兔免费精品6| 久久青青草视频| 国内精品伊人久久久久妇| 久久亚洲中文字幕精品一区四| 91精品国产91热久久久久福利 | 四虎影视久久久免费| 人妻精品久久久久中文字幕| 久久综合日本熟妇| 日韩欧美亚洲综合久久| 亚洲中文字幕无码久久2017 | 国内精品欧美久久精品|