排列

[題目鏈接]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個(gè)整數(shù)排成一排有多少種不同的排法

思路

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

遞歸搜索樹
搜索歷程

坑點(diǎn)

1. 按照字典序排列
   字典序——按照字典中的順序排列，如在英語字典中以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（沒有被標(biāo)記），當(dāng)被標(biāo)記時(shí)，數(shù)組值則為1，另一個(gè)為q，記錄每一個(gè)填入u位置的數(shù)字
2. 在主函數(shù)中定義一個(gè)dfs函數(shù)，初始值為1，即u的值，從第一個(gè)能夠存放數(shù)字的位置開始
3. 當(dāng)u>n，即超出最底層時(shí)，說明已經(jīng)數(shù)字已經(jīng)填到了最后一個(gè)空，此時(shí)可以輸出數(shù)組q中的數(shù)字
4. 當(dāng)u沒有到最底層時(shí)，利用for循環(huán)從1到n開始給每一個(gè)u上的數(shù)賦值
5. 判斷賦值的數(shù)是否被標(biāo)記，當(dāng)數(shù)組st的值不為0時(shí)，則說明該數(shù)沒有被標(biāo)記，可用，此時(shí)將 i 賦值給q[u]（從1到n循環(huán)遍歷每一個(gè)位置上被放置的數(shù)字）
6. 此時(shí)，將數(shù)組st的值改為1，表示上述填過的數(shù)字被標(biāo)記為已使用過，后面不可用
7. 繼而利用dfs（u+1）進(jìn)行下面一層一層的遞歸
8. 當(dāng)從每個(gè)下一層出來，返回上一層，進(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，表示被使用過，為1則表示沒有使用過
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]沒有被使用過時(shí)
            {q[u]=i;              //從1到n循環(huán)遍歷每一次存放數(shù)字的位置
                st[i]=1;    //在當(dāng)前位置存放一個(gè)數(shù)后，該數(shù)字狀態(tài)被標(biāo)記為已使用過（字典序要求），后面不可用
                dfs(u+1);   //進(jìn)行下一層的函數(shù)遞歸
                st[i]=0;//從下一層出來往上返回進(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è)位置開始填數(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ù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：【動(dòng)態(tài)規(guī)劃——排列】-創(chuàng)新互聯(lián)
路徑分享：http://weahome.cn/article/dhsooo.html