HackMDCh16 回溯法
搭配green judge解題系統
Special thanks to 台中女中sagit老師 <(_ _)>
上一章：動態規劃
下一章：二分搜尋法
回目錄：國立科學園區實驗中學C++程式語言自學講義
回溯法的用途
回溯法適用於想要窮舉所有可能的問題上
例如：
1.N格的密碼鎖，每格都是0至9的數字，列出所有密碼的可能
2.N格的密碼鎖，每格都是0至9的數字且互不重複，列出所有密碼的可能
看起來好像可以用迴圈解決
例如N是4的時候，第一題可以寫成
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
for(int k=0;k<10;k++){
for(int l=0;l<10;l++){
cout<<i<<j<<k<<l<<endl;
}
}
}
}
第二題可以寫成
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
for(int k=0;k<10;k++){
for(int l=0;l<10;l++){
if(i!=j&&i!=k&&i!=l&&j!=k&&j!=l&&k!=l){
cout<<i<<j<<k<<l<<endl;
}
}
}
}
}
但是，如果N是太大的數字
不可能真的就寫出N個迴圈來
而且，因為題目不知道N是多少
因此沒辦法在寫程式的時候就固定某數量的迴圈
把迴圈放進遞迴裡
以上迴圈包迴圈的作法雖然是對的
但苦於不知道總共要用幾個迴圈
那麼解決的方法就是把迴圈放進遞迴裡面
只要一開始知道總共要遞迴到幾層
就能利用遞迴創造出像上面那樣迴圈包迴圈的效果
例如
int ans[100];
void permute(int idx)
{
if(idx==n){
for(int i=0;i<n;i++){ //印答案
cout<<ans[i];
}
cout<<endl;
return;
}
for(int i=0;i<10;i++){ //列舉第idx格可以是哪些數字
ans[idx]=i;
permute(idx+1);
}
}
int main()
{
cin>>n;
permute(0);
}
函式裡面放的是一個迴圈
把答案的第idx個位置從0到9都試過一遍
接著呼叫下一次遞迴來列舉第idx+1個位置的所有可能
ans的陣列存放的是列舉出來的答案
等到每一格都放好數字了
就可以把答案印出來
【學生練習題】
不能重複的問題
如果題目要求每格都互不重複
那麼在印出答案時檢查兩兩有沒有相等實在有點太麻煩了
例如總共有10格
那就要檢查
實在不優
因此可以開一個陣列來記錄每個數字是不是已經被用過了
如果已經被用過了那就不要用了
【例題】
密碼是N個不重複的數字
每個數字都是0到9之間的數字
請列出所有可能
bool used[10];
int ans[100];
void permute(int idx)
{
if(idx==n){
for(int i=0;i<n;i++) cout<<ans[i];
cout<<endl;
return;
}
for(int i=0;i<10;i++){
if(used[i]==0){ //只有「數字i」沒有被使用過時才可以把i放在這格使用
used[i]=1; //把「數字i」標記成已使用
permute(idx+1);
used[i]=0; //把「數字i」標記成未使用
}
}
}
int main()
{
cin>>n;
memset(used, 0, sizeof(used)); // 把 used 陣列全洗成 0
permute(0);
}
【學生練習題】
經典題型：八皇后
在8*8的棋盤上放8隻皇后棋
這8隻皇后兩兩不能在同一行、不能在同一列、也不能在同一條斜線上
不然這兩隻皇后會互相殘殺
請列出總共 8! 種排法裡面
所有「不會有皇后互相殘殺」的排法
首先
第一行的皇后可以放在1至8的任何一個位置
第二行的皇后也是試試看1至8，但需要避開會和第一隻皇后殘殺的位置
第三行的皇后則須要避開會和第一隻或第二隻皇后殘殺的位置
因此
我們需要三個陣列來記錄
「這一列是不是已經被某隻皇后佔據了」
「這一條斜線(/)是不是已經被某隻皇后佔據了」
「這一條斜線(\)是不是已經被某隻皇后佔據了」
bool col_used[100];
bool left_diag_used[100];
bool right_diag_used[100];
int ans[15];
void queen(int row)
{
if(row==n+1){
印出答案
return;
}
for(int col=1;col<=n;col++){
// 如果這個直線或斜線被占據了，就跳過
if(col_used[col]==1) continue;
if(left_diag_used[row+col]==1) continue;
if(right_diag_used[n+row-col]==1) continue;
// 放上本隻皇后
ans[row]=col;
// 標示出這個直線和斜線都被占據了
col_used[col]=1;
left_diag_used[row+col]=1;
right_diag_used[n+row-col]=1;
// 繼續遞迴
queen(row+1);
// 取消，標示出這個直線和斜線都沒被佔據
col_used[col]=0;
left_diag_used[row+col]=0;
right_diag_used[n+row-col]=0;
// 繼續迴圈，試試看把本隻皇后放到別的位置看看
}
}
int main()
{
cin>>n;
memset(col_used, 0, sizeof(col_used));
memset(left_diag_used, 0, sizeof(left_diag_used));
memset(right_diag_used, 0, sizeof(right_diag_used));
queen(0);
}
【學生練習題】
經典題型：多個物品內挑數個達成特定目標
有N個物品
每個都可以選擇拿或不拿
所有被選到的物品希望達成某個特定目標
用遞迴函式把這2^N種組合都列出來
每次都檢查是否達成目標即可
【例題】
有N支放大鏡，每一支的放大倍數都不同
想要選若干支起來達成M的放大倍率
請列出所有的選法
用current來表示目前已經放大幾倍了
在函式裡面把「拿第idx支」和「不要拿第idx支」都試試看
bool selected[30];
int magnify[30];
void solve(int idx, int current)
{
//要拿這支
selected[idx]=1;
solve(idx+1, current*magnify[idx]);
//不要拿這支
selected[idx]=0;
solve(idx+1, current);
}
int main()
{
cin>>n;
cin>>goal;
for(int i=0;i<n;i++) cin>>magnify[i];
solve(0, 1);
}
接著考慮邊界條件
- 放大倍率達到目標了(current==goal)
- 每一支都試過了(idx==n)
bool selected[30];
int magnify[30];
void solve(int idx, int current)
{
if(current==goal){ //放大倍率達到目標
// 印出選了哪幾支
for(int i=0;i<n;i++){
if(selected[i]) cout<<magnify[i]<<" ";
}
cout<<endl;
return;
}
if(idx==n) return; //每一支都試過了
//要拿這支
selected[idx]=1;
solve(idx+1, current*magnify[idx]);
//不要拿這支
selected[idx]=0;
solve(idx+1, current);
}
這時可以再想想
有沒有甚麼地方可以提早知道沒希望了、提早放棄呢?
當目前的放大倍率已經超過目標時
不管後面的怎麼選都不可能成功
因此可以加上檢查current>goal
bool selected[30];
int magnify[30];
void solve(int idx, int current)
{
if(current==goal){ //放大倍率達到目標
for(int i=0;i<n;i++){
if(selected[i]) cout<<magnify[i]<<" ";
}
cout<<endl;
return;
}
if(idx==n) return; //每一支都試過了
if(current>goal) return; //沒希望了
//要拿這支
selected[idx]=1;
solve(idx+1, current*magnify[idx]);
//不要拿這支
selected[idx]=0;
solve(idx+1, current);
}
【學生練習題】
上一章：動態規劃
下一章：二分搜尋法
回目錄：國立科學園區實驗中學C++程式語言自學講義
