排列

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

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

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

思路

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

遞歸搜索樹
搜索歷程

坑點(diǎn)

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

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

1. 定義兩個數(shù)組，一個為st（state）記錄每個數(shù)的狀態(tài)，即該數(shù)字是否被標(biāo)記，默認(rèn)st數(shù)組的值為0（沒有被標(biāo)記），當(dāng)被標(biāo)記時，數(shù)組值則為1，另一個為q，記錄每一個填入u位置的數(shù)字
2. 在主函數(shù)中定義一個dfs函數(shù)，初始值為1，即u的值，從第一個能夠存放數(shù)字的位置開始
3. 當(dāng)u>n，即超出最底層時，說明已經(jīng)數(shù)字已經(jīng)填到了最后一個空，此時可以輸出數(shù)組q中的數(shù)字
4. 當(dāng)u沒有到最底層時，利用for循環(huán)從1到n開始給每一個u上的數(shù)賦值
5. 判斷賦值的數(shù)是否被標(biāo)記，當(dāng)數(shù)組st的值不為0時，則說明該數(shù)沒有被標(biāo)記，可用，此時將 i 賦值給q[u]（從1到n循環(huán)遍歷每一個位置上被放置的數(shù)字）
6. 此時，將數(shù)組st的值改為1，表示上述填過的數(shù)字被標(biāo)記為已使用過，后面不可用
7. 繼而利用dfs（u+1）進(jìn)行下面一層一層的遞歸
8. 當(dāng)從每個下一層出來，返回上一層，進(jìn)行上一個存放數(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，表示被使用過，為1則表示沒有使用過
int q[10];                                      //表示輸出的n個數(shù)字排成的一排
void dfs (int u)
{if (u>n)                            //當(dāng)數(shù)字已經(jīng)填到大于n的空時
    {for(int i=1;i<=n;i++)
        {cout<for(int i=1;i<=n;i++)
        {if (!st[i])              //否則，當(dāng)st[i]沒有被使用過時
            {q[u]=i;              //從1到n循環(huán)遍歷每一次存放數(shù)字的位置
                st[i]=1;    //在當(dāng)前位置存放一個數(shù)后，該數(shù)字狀態(tài)被標(biāo)記為已使用過（字典序要求），后面不可用
                dfs(u+1);   //進(jìn)行下一層的函數(shù)遞歸
                st[i]=0;//從下一層出來往上返回進(jìn)行上一個存放數(shù)字位置的填空時，此時的數(shù)字狀態(tài)變?yōu)槲幢粯?biāo)記
            }
        }
    }
}
int main ()
{cin>>n;
    dfs(1);                                           //定義一個函數(shù)，初始值為1，因?yàn)閺牡谝粋€位置開始填數(shù)字
    return 0;
}

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

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

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

廣告

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