# Ch16 回溯法 > 搭配[green judge解題系統](http://www.tcgs.tc.edu.tw:1218/) > Special thanks to [台中女中sagit老師](http://www.tcgs.tc.edu.tw/~sagit/index.htm) \<\(\_ \_\)\> ## > 上一章：[動態規劃](https://hackmd.io/s/ByZgGkLpW) > 下一章：[二分搜尋法](https://hackmd.io/s/ByCZ5Yoa7) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z) ## <font color='darkblue'>回溯法的用途</font> 回溯法適用於想要窮舉所有可能的問題上 例如： 1.N格的密碼鎖，每格都是0至9的數字，列出所有密碼的可能 2.N格的密碼鎖，每格都是0至9的數字且互不重複，列出所有密碼的可能 看起來好像可以用迴圈解決 例如N是4的時候，第一題可以寫成 ```cpp= 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; } } } } ``` 第二題可以寫成 ```cpp= 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是多少 因此沒辦法在寫程式的時候就固定某數量的迴圈 ## <font color='darkblue'>把迴圈放進遞迴裡</font> 以上迴圈包迴圈的作法雖然是對的 但苦於不知道總共要用幾個迴圈 那麼解決的方法就是把迴圈放進遞迴裡面 只要一開始知道總共要遞迴到幾層 就能利用遞迴創造出像上面那樣迴圈包迴圈的效果 例如 ```cpp= 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的陣列存放的是列舉出來的答案 等到每一格都放好數字了 就可以把答案印出來 <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b037: 小數的密碼 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b037) ## <font color='darkblue'>不能重複的問題</font> 如果題目要求每格都互不重複 那麼在印出答案時檢查兩兩有沒有相等實在有點太麻煩了 例如總共有10格 那就要檢查$C^{10}_2=45$次了 實在不優 因此可以開一個陣列來記錄每個數字是不是已經被用過了 如果已經被用過了那就不要用了 <font color='darkorange'>【例題】</font> > 密碼是N個不重複的數字 > 每個數字都是0到9之間的數字 > 請列出所有可能 ```cpp= 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); } ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b038: 法老王的石獅子 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b038) ## <font color='darkblue'>經典題型：八皇后</font> 在8\*8的棋盤上放8隻皇后棋 這8隻皇后兩兩不能在同一行、不能在同一列、也不能在同一條斜線上 不然這兩隻皇后會互相殘殺 請列出總共 8! 種排法裡面 所有「不會有皇后互相殘殺」的排法 首先 第一行的皇后可以放在1至8的任何一個位置 第二行的皇后也是試試看1至8，但需要避開會和第一隻皇后殘殺的位置 第三行的皇后則須要避開會和第一隻或第二隻皇后殘殺的位置 因此 我們需要三個陣列來記錄 「這一列是不是已經被某隻皇后佔據了」 「這一條斜線(/)是不是已經被某隻皇后佔據了」 「這一條斜線(\\)是不是已經被某隻皇后佔據了」 ```cpp= 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); } ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b039: 最終兵器X ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b040) ## <font color='darkblue'>經典題型：多個物品內挑數個達成特定目標</font> 有N個物品 每個都可以選擇拿或不拿 所有被選到的物品希望達成某個特定目標 用遞迴函式把這2^N種組合都列出來 每次都檢查是否達成目標即可 <font color='darkorange'>【例題】</font> >有N支放大鏡，每一支的放大倍數都不同 >想要選若干支起來達成M的放大倍率 >請列出所有的選法 用current來表示目前已經放大幾倍了 在函式裡面把「拿第idx支」和「不要拿第idx支」都試試看 ```cpp= 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); } ``` 接著考慮邊界條件 1. 放大倍率達到目標了(current==goal) 2. 每一支都試過了(idx==n) ```cpp= 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 ```cpp= 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); } ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [Green Judge b040: 以物易物 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b040) ## > 上一章：[動態規劃](https://hackmd.io/s/ByZgGkLpW) > 下一章：[二分搜尋法](https://hackmd.io/s/ByCZ5Yoa7) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)