題目描述
有n個士兵站成一列， 從第1個士兵前面向後望去， 剛好能看到m個士兵， 如果站在後面的士兵身高小於或者等於前面某個士兵的身高， 那麼後面的這個士兵就不能被看到， 問這n個士兵有多少種排列方式， 剛好在觀測位能看到m個士兵？
第一行輸入 n 個士兵和 m 個可以看到的士兵（n >= m）， 第二行輸入 n 個士兵的身高， 輸出為排列方式的種數。
輸入：
4 3
1 1 2 3
輸出：
6
也就是說， 輸入數 n, m (n
我的思路是，
把陣列 a 中的序列所有可能的排列情況列出來然後對每一個可能的情況分析， 如果某種排列能夠恰好使其中可見的數為 m，排列組合
那麼先來考慮一個子問題：
Q：如何輸出一個陣列的所有可能排列方式。
首先回顧一下我們是怎麼進行全排列的。
一個大小為 n 的陣列的全排列有 n! 種，
假設有 3 個各不相同的球，
1 2 3
要將他們放到 3 個不同的盒子中
就有 3! = 3x2x1 種方式， 數學解題的思路如下：
首先把第一個球放到第 1 個盒子中， 再考慮填入第 2 個盒子， 把第 2 個球放入第 2 個盒子， 剩下最後一個球只能放進最後一個盒子了， 這是第一種情況；
然後回到放第 2 個盒子這一步， 同樣的這個盒子可以先放第 3 個球， 這樣第 2 個球就只能放入第 3 個盒子了， 這就是第 2 種情況；
然後再回到填第 1 個盒子的地方， 放入第 2 個球……
這樣總共還有 4 種可能的情況， 那麼總共的排列方式就是 6 種，
這樣所有可能的排列方式就全部列出來了。 可以看到， 實際上將 1 2 3 這個序列中的數交換位置， 可以得到後面的幾種排列。
嘗試交換位置
假設輸入的陣列是a， a[0]=1, a[1]=2, a[2]=3
先嘗試如果單純的用迴圈加上交換陣列數值的方法能否遍歷所有情況：
1 #include 2 using namespace std; 3 int n = 3; 4 5 void print_arr(const int * a) { 6 cout 0; j--) { // inner for 28 swap(a[j], a[j-1]); 29 print_arr(a); 30 } 31 swap(a[0], a[i]); 32 } 33 34 return 0; 35 }得到的結果為：
出現了 7 個序列， 其中只有 5 個是不重複的， 也就是說還少一種情況。
分析其原因：
在 inner for 迴圈結束的時候， 將a[0]與a[i]進行交換，
這樣做實際上是類似於把第2個球放入第1個盒子的步驟， 但是這沒有考慮到此時的陣列已經不是最開始的 1, 2, 3 這樣的序列了。
那麼如果每次找到一個序列後， 將陣列重新設為 1, 2, 3這樣的序列行不行呢？
仔細想一想， 其實也不行， 因為 inner for 裡面的代碼僅僅交換了相鄰兩個數， 這樣就遺漏了很多種情況。
遞迴和回溯
需要遍歷所有情況的話， 最容易想到的應該就是遞迴了。
而且在思考排列球的方法中， 很重要的一點就是
當所有球都放到了盒子中， 要回到前一個盒子的那一步，
這種方法就是回溯。
很容易想到如果是 1 個球放 1 個盒子， 只有 1 種情況， 這是遞迴的終點（也就是把所有球都放到盒子中， 這一次遞迴就結束了）。
那麼， 當序號最後的球（比如序號為 3， 3 個球放入 3 個盒子）放到了第一個盒子中， 而這趟遞迴也結束了。 就認為所有可能的情況都已經遍歷過了， 回溯遞迴也就結束了。
加入一個 bool 型陣列， 用於保存球的使用狀態（true 表示球已經放入盒子裡）。
1 #include 2 #include 3 using namespace std; 4 int n = 3, m; 5 int res = 0; 6 7 void print_arr(const int * a) { 8 cout = n) { 47 break; 48 } 49 b[i] = a[in]; 50 used[in] = true; 51 if( order(a, b, used, i+1) == 1 ) 52 { 53 used[in] = false; 54 in++; 55 } 56 } 57 return 1; 58 } 59 60 int main { 61 int a[n] = {1, 2, 3}; 62 int b[n] = {}; 63 bool used[n] = {false}; 64 order(a, b, used, 0); 65 cout試著運行一下：
果然所有的可能情況都遍歷到了， 並且沒有重複， 沒有遺漏。 然後把代碼中的 n 改為其它數， 給陣列 a 添加相應的元素， 也能夠遍歷所有情況。
到這一步， 全排列就已經實現了。
不過其實這裡的代碼還有改進的地方， 仔細觀察 order(const int*, int *, bool[], int) 這個函數， 能夠發現它的返回值其實並沒有什麼作用， 可以考慮去掉返回值， 將函數類型改為 void， 這樣能夠減少堆疊的記憶體使用。
完成演算法題
現在還需要的一步就是要算出每種可能的排列中， 可見士兵的數量。 用一個 getUncovered(int *a); 函數算出可見的士兵數， 然後比較是否等於 m就可以了。
完整的程式：
1 #include 2 #include 3 using namespace std; 4 int n , m; 5 int res = 0; 6 7 void print_arr(const int * a); 8 int getCoverd(const int * a); 9 10 void print_arr(const int * a) { 11 cout a[point]) { 25 uncovered++; 26 point = i; 27 } 28 } 29 return uncovered; 30 } 31 32 /** 33 * b 需要被分配數值的陣列 34 * i b 陣列中需要被設置的序號 35 * used 用來進行回溯的陣列標誌位元，true 表示 a 陣列中該序號的元素已經被使用 36 * in 現在使用的 a 陣列中的序號 37 * 需要用到遞迴和回溯， 38 * 若 i == n ，意味著 b 陣列所有的元素都被分配了，此時可以嘗試列印陣列 39 * 設置一個標誌位元 in，意味著 b[i] 空格將要被 a[in] 球佔據。 40 * 每一個 b[i] 空格都要迴圈整個 a 中的球。 41 * 但是在 inner 的迴圈過程中 in 的值有可能超過 n，這個時候就需要直接退出迴圈了。 42 */ 43 void order(const int * a, int * b, bool used[], int i) { 44 /* all used */ 45 if(i == n) { 46 print_arr(b); 47 /* 如果滿足條件，進行自訂的處理 */ 48 if( getUncovered(b) == m) { 49 res++; 50 } 51 // return 1; 52 } 53 int in = 0; 54 55 while (in = n) { 64 break; 65 } 66 b[i] = a[in]; 67 used[in] = true; 68 order(a, b, used, i+1); 69 used[in] = false; 70 in++; 71 } 72 } 73 74 int main { 75 cin >> n >> m; 76 77 int a[n] = {}; 78 int b[n] = {}; 79 bool used[n] = {false}; 80 81 for(int i = 0; i > a[i]; 83 } 84 85 order(a, b, used, 0); 86 cout最後進行一個簡單的測試，結果非常棒！
總結把數學問題轉化成程式問題，要多做嘗試，盡可能的用自己熟悉的方法去理解問題，用易於實現的方法一步步地來解決問題實際上最開始我的思路很亂，又想著將陣列 a 中的數賦值到 b 中，又想著 b 中的數應該存放 a 中的哪個數，這樣導致想得太複雜，遞迴演算法的實現也很亂。後來用兩個數 1，2 作為陣列的兩個元素進行調試通過對函數的觀察，改進了函數，去掉了無用的返回值。 然後比較是否等於 m就可以了。
完整的程式：
1 #include 2 #include 3 using namespace std; 4 int n , m; 5 int res = 0; 6 7 void print_arr(const int * a); 8 int getCoverd(const int * a); 9 10 void print_arr(const int * a) { 11 cout a[point]) { 25 uncovered++; 26 point = i; 27 } 28 } 29 return uncovered; 30 } 31 32 /** 33 * b 需要被分配數值的陣列 34 * i b 陣列中需要被設置的序號 35 * used 用來進行回溯的陣列標誌位元，true 表示 a 陣列中該序號的元素已經被使用 36 * in 現在使用的 a 陣列中的序號 37 * 需要用到遞迴和回溯， 38 * 若 i == n ，意味著 b 陣列所有的元素都被分配了，此時可以嘗試列印陣列 39 * 設置一個標誌位元 in，意味著 b[i] 空格將要被 a[in] 球佔據。 40 * 每一個 b[i] 空格都要迴圈整個 a 中的球。 41 * 但是在 inner 的迴圈過程中 in 的值有可能超過 n，這個時候就需要直接退出迴圈了。 42 */ 43 void order(const int * a, int * b, bool used[], int i) { 44 /* all used */ 45 if(i == n) { 46 print_arr(b); 47 /* 如果滿足條件，進行自訂的處理 */ 48 if( getUncovered(b) == m) { 49 res++; 50 } 51 // return 1; 52 } 53 int in = 0; 54 55 while (in = n) { 64 break; 65 } 66 b[i] = a[in]; 67 used[in] = true; 68 order(a, b, used, i+1); 69 used[in] = false; 70 in++; 71 } 72 } 73 74 int main { 75 cin >> n >> m; 76 77 int a[n] = {}; 78 int b[n] = {}; 79 bool used[n] = {false}; 80 81 for(int i = 0; i > a[i]; 83 } 84 85 order(a, b, used, 0); 86 cout最後進行一個簡單的測試，結果非常棒！
總結把數學問題轉化成程式問題，要多做嘗試，盡可能的用自己熟悉的方法去理解問題，用易於實現的方法一步步地來解決問題實際上最開始我的思路很亂，又想著將陣列 a 中的數賦值到 b 中，又想著 b 中的數應該存放 a 中的哪個數，這樣導致想得太複雜，遞迴演算法的實現也很亂。後來用兩個數 1，2 作為陣列的兩個元素進行調試通過對函數的觀察，改進了函數，去掉了無用的返回值。