建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
【動態(tài)規(guī)劃——排列】-創(chuàng)新互聯(lián)
排列
當(dāng)前文章：【動態(tài)規(guī)劃——排列】-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://www.dlmjj.cn/article/dhsooo.html
[題目鏈接]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è)計，專業(yè)設(shè)計，全程項目跟蹤，成都創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)題意思路求將1~n個整數(shù)排成一排有多少種不同的排法
- 共3位數(shù)，有三個能夠存放數(shù)字的位置，用u代表第幾個能存放數(shù)字的位置
- 從第一個位置，即從u=1開始遞歸，從數(shù)字1到3進行考慮所有情況，放過的數(shù)字則不能進行第二次放置
- 當(dāng)放置到最底層，即u=n時，開始返回進行上一層的遞歸（返回現(xiàn)場），同時取消標(biāo)記第三個位置存放的數(shù)
坑點遞歸搜索樹
搜索歷程
實現(xiàn)步驟
- 按照字典序排列
字典序——按照字典中的順序排列，如在英語字典中以a、b、c……z的順序排列，對于數(shù)字則是以1、2、3…n的順序排列
代碼
- 定義兩個數(shù)組，一個為st（state）記錄每個數(shù)的狀態(tài)，即該數(shù)字是否被標(biāo)記，默認st數(shù)組的值為0（沒有被標(biāo)記），當(dāng)被標(biāo)記時，數(shù)組值則為1，另一個為q，記錄每一個填入u位置的數(shù)字
- 在主函數(shù)中定義一個dfs函數(shù)，初始值為1，即u的值，從第一個能夠存放數(shù)字的位置開始
- 當(dāng)u>n，即超出最底層時，說明已經(jīng)數(shù)字已經(jīng)填到了最后一個空，此時可以輸出數(shù)組q中的數(shù)字
- 當(dāng)u沒有到最底層時，利用for循環(huán)從1到n開始給每一個u上的數(shù)賦值
- 判斷賦值的數(shù)是否被標(biāo)記，當(dāng)數(shù)組st的值不為0時，則說明該數(shù)沒有被標(biāo)記，可用，此時將 i 賦值給q[u]（從1到n循環(huán)遍歷每一個位置上被放置的數(shù)字）
- 此時，將數(shù)組st的值改為1，表示上述填過的數(shù)字被標(biāo)記為已使用過，后面不可用
- 繼而利用dfs（u+1）進行下面一層一層的遞歸
- 當(dāng)從每個下一層出來，返回上一層，進行上一個存放數(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，默認值為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); //進行下一層的函數(shù)遞歸
st[i]=0;//從下一層出來往上返回進行上一個存放數(shù)字位置的填空時，此時的數(shù)字狀態(tài)變?yōu)槲幢粯?biāo)記
}
}
}
}
int main ()
{cin>>n;
dfs(1); //定義一個函數(shù)，初始值為1，因為從第一個位置開始填數(shù)字
return 0;
}
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
當(dāng)前文章：【動態(tài)規(guī)劃——排列】-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://www.dlmjj.cn/article/dhsooo.html
