排列

[題目鏈接]https://www.acwing.com/problem/content/825/

成都創(chuàng)新互聯(lián)公司專(zhuān)注于博樂(lè)企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè)公司,商城網(wǎng)站制作。博樂(lè)網(wǎng)站建設(shè)公司,為博樂(lè)等地區(qū)提供建站服務(wù)。全流程按需網(wǎng)站設(shè)計(jì)，專(zhuān)業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，成都創(chuàng)新互聯(lián)公司專(zhuān)業(yè)和態(tài)度為您提供的服務(wù)題意

求將1~n個(gè)整數(shù)排成一排有多少種不同的排法

思路

1. 共3位數(shù)，有三個(gè)能夠存放數(shù)字的位置，用u代表第幾個(gè)能存放數(shù)字的位置
2. 從第一個(gè)位置，即從u=1開(kāi)始遞歸，從數(shù)字1到3進(jìn)行考慮所有情況，放過(guò)的數(shù)字則不能進(jìn)行第二次放置
3. 當(dāng)放置到最底層，即u=n時(shí)，開(kāi)始返回進(jìn)行上一層的遞歸（返回現(xiàn)場(chǎng)），同時(shí)取消標(biāo)記第三個(gè)位置存放的數(shù)

遞歸搜索樹(shù)
搜索歷程

坑點(diǎn)

1. 按照字典序排列
   字典序——按照字典中的順序排列，如在英語(yǔ)字典中以a、b、c……z的順序排列，對(duì)于數(shù)字則是以1、2、3…n的順序排列

實(shí)現(xiàn)步驟

1. 定義兩個(gè)數(shù)組，一個(gè)為st（state）記錄每個(gè)數(shù)的狀態(tài)，即該數(shù)字是否被標(biāo)記，默認(rèn)st數(shù)組的值為0（沒(méi)有被標(biāo)記），當(dāng)被標(biāo)記時(shí)，數(shù)組值則為1，另一個(gè)為q，記錄每一個(gè)填入u位置的數(shù)字
2. 在主函數(shù)中定義一個(gè)dfs函數(shù)，初始值為1，即u的值，從第一個(gè)能夠存放數(shù)字的位置開(kāi)始
3. 當(dāng)u>n，即超出最底層時(shí)，說(shuō)明已經(jīng)數(shù)字已經(jīng)填到了最后一個(gè)空，此時(shí)可以輸出數(shù)組q中的數(shù)字
4. 當(dāng)u沒(méi)有到最底層時(shí)，利用for循環(huán)從1到n開(kāi)始給每一個(gè)u上的數(shù)賦值
5. 判斷賦值的數(shù)是否被標(biāo)記，當(dāng)數(shù)組st的值不為0時(shí)，則說(shuō)明該數(shù)沒(méi)有被標(biāo)記，可用，此時(shí)將 i 賦值給q[u]（從1到n循環(huán)遍歷每一個(gè)位置上被放置的數(shù)字）
6. 此時(shí)，將數(shù)組st的值改為1，表示上述填過(guò)的數(shù)字被標(biāo)記為已使用過(guò)，后面不可用
7. 繼而利用dfs（u+1）進(jìn)行下面一層一層的遞歸
8. 當(dāng)從每個(gè)下一層出來(lái)，返回上一層，進(jìn)行上一個(gè)存放數(shù)字位置的填空時(shí)，此時(shí)的數(shù)字狀態(tài)需被改為未被標(biāo)記的狀態(tài)，即st[i]=0。

代碼

#includeusing namespace std;
int n;                                           //輸入的整數(shù)n
int st[15];                           //判斷數(shù)字狀態(tài)為0還是1，默認(rèn)值為0，表示被使用過(guò)，為1則表示沒(méi)有使用過(guò)
int q[10];                                      //表示輸出的n個(gè)數(shù)字排成的一排
void dfs (int u)
{if (u>n)                            //當(dāng)數(shù)字已經(jīng)填到大于n的空時(shí)
    {for(int i=1;i<=n;i++)
        {cout<for(int i=1;i<=n;i++)
        {if (!st[i])              //否則，當(dāng)st[i]沒(méi)有被使用過(guò)時(shí)
            {q[u]=i;              //從1到n循環(huán)遍歷每一次存放數(shù)字的位置
                st[i]=1;    //在當(dāng)前位置存放一個(gè)數(shù)后，該數(shù)字狀態(tài)被標(biāo)記為已使用過(guò)（字典序要求），后面不可用
                dfs(u+1);   //進(jìn)行下一層的函數(shù)遞歸
                st[i]=0;//從下一層出來(lái)往上返回進(jìn)行上一個(gè)存放數(shù)字位置的填空時(shí)，此時(shí)的數(shù)字狀態(tài)變?yōu)槲幢粯?biāo)記
            }
        }
    }
}
int main ()
{cin>>n;
    dfs(1);                                           //定義一個(gè)函數(shù)，初始值為1，因?yàn)閺牡谝粋€(gè)位置開(kāi)始填數(shù)字
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)標(biāo)題：【動(dòng)態(tài)規(guī)劃——排列】-創(chuàng)新互聯(lián)
URL分享：http://chinadenli.net/article0/dhsooo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開(kāi)發(fā)、品牌網(wǎng)站設(shè)計(jì)、關(guān)鍵詞優(yōu)化、手機(jī)網(wǎng)站建設(shè)、全網(wǎng)營(yíng)銷(xiāo)推廣、網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)