Ch16 回溯法

# 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) ## 回溯法的用途 回溯法適用於想要窮舉所有可能的問題上例如： 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是多少因此沒辦法在寫程式的時候就固定某數量的迴圈 ## 把迴圈放進遞迴裡 以上迴圈包迴圈的作法雖然是對的但苦於不知道總共要用幾個迴圈那麼解決的方法就是把迴圈放進遞迴裡面只要一開始知道總共要遞迴到幾層就能利用遞迴創造出像上面那樣迴圈包迴圈的效果例如 ```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的陣列存放的是列舉出來的答案等到每一格都放好數字了就可以把答案印出來 【學生練習題】 > - [ ] [Green Judge b037: 小數的密碼 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b037) ## 不能重複的問題 如果題目要求每格都互不重複那麼在印出答案時檢查兩兩有沒有相等實在有點太麻煩了例如總共有10格那就要檢查$C^{10}_2=45$次了實在不優因此可以開一個陣列來記錄每個數字是不是已經被用過了如果已經被用過了那就不要用了 【例題】 > 密碼是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); } ``` 【學生練習題】 > - [ ] [Green Judge b038: 法老王的石獅子 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b038) ## 經典題型：八皇后 在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); } ``` 【學生練習題】 > - [ ] [Green Judge b039: 最終兵器X ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b040) ## 經典題型：多個物品內挑數個達成特定目標 有N個物品每個都可以選擇拿或不拿所有被選到的物品希望達成某個特定目標用遞迴函式把這2^N種組合都列出來每次都檢查是否達成目標即可 【例題】 >有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); } ``` 【學生練習題】 > - [ ] [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)