參照計算機演算法設計與分析（第5版）
這個代碼跑在vs2017上的，如果其他ide我不保證一定一樣，本文的初衷在于幫助數學不好的遞回初學者（和用不來斷點的老哥：事實上斷點也不好整，容易看到心態爆炸）用順序閱讀的形式來簡單理解遞回
我的遞回代碼（無重復元素可用）
#include<iostream>
using namespace std;
int res = 0;//數數用
void Swap(char &a, char &b) {
if (a == b)
;
else {
char temp = a;
a = b;
b = temp;
}
}
void Perm(char brr[], int k , int m)
// k：變數，表示運行到第幾個數了 m: 常量，需要排列的陣列
{
if (k == m) {
for (int i = 0; i <= m; i++)
{
cout << brr[i];
}
cout << endl;
res += 1;
}
else {
for (int i = k; i <= m; i++)
{
Swap(brr[k], brr[i]);
Perm(brr, k + 1, m);
Swap(brr[k], brr[i]);
}
}
}
int main() {
char arr[] = "abc";
Perm(arr, 0, 2);
cout << res << endl;
system("pause");
return 0;
}
然后是按步來推導遞回的偽代碼
首先：每一個Perm()的構成為：
輸出：Perm()
if
程序：Perm()
else
for
swap
下一級Perm
swap
for（如果有）
swap
下一級Perm
swap
Perm(arr,k,m)：這個代表進入了下一層函式
Arr:陣列
K:當前的位置
M:需要排列的總長度（從0開始算）
主函式部分：
Char arr[] = ‘abc’
Perm(arr,0,2)
進入Perm_1(arr = ‘abc’,k = 0,m = 2)
Else
For i:0 k:0
無效Swap
Perm_2_1(arr = ‘abc’,k = 1,m = 2):
Else
For i: 1 k:1
無效swap
Perm_3_1(arr = ‘abc’,k = 2,m = 2)
If:cout<<”abc”
無效swap
For i:2 k:1
Swap(2,1)->arr:”acb”
Pern_3_2(arr = ‘acb’,k=2,m=2)
If:cout<<”acb”
Swap(2,1)->arr:’abc’
無效swap
For i:1 k :0
Swap(1,0)->”bac”
Perm_2_2(arr = ‘bac’, k = 1,m = 2)
Else
For i:1 k:1
無效swap
Perm_3_3(arr = ‘bac’,k = 2,m = 2)
If:cout<<”bac”
無效swap
For i:2 k:1
Swap(2,1)->’bca’
Perm_3_4(arr = ‘bca’ , k = 2 , m = 2)
If:cout<<”bca”
Swap(2,1)->‘bac’
Swap(1,0)->”abc”
For i:2 k:0
Swap(2,0)->”cba”
Perm_2_3(arr = ‘cba’, k = 1,m = 2)
Else
For i:1 k:1
無效swap
Perm_3_5(arr = ‘cba’ k = 2, m =2)
If:cout<<”cba”
無效swap
For i:2 k:1
Swap(2,1)->”cab”
Perm_3_6(arr = ‘cab’ k = 2,m = 2)
If:cout<<”cab”
Swap(2,1) ->”cba”
Swap(2,0)->"abc"
Perm_1 結束
主函式 return0
over
補充下介紹，這玩意是個偽代碼，我按縮進形式表現出來的，可以看出來
1：第一個swap的作用：真就是交換，這個應該沒啥問題
2：第二個swap的作用：遞回完了把整個恢復原樣：’abc‘
(不是必要的，但是這是個好習慣，這個全排列不加是可以得到同樣個數但是不同順序的答案，但是dfs這些你咋辦，，)
補充個全排列的個數計算：
(m+1-k):for回圈的個數
當k==m的時候是最后一層（也就是1），這時候就到了perm的if條件，直接輸出
那么第4層就是第一層的(m+1-k)*第二層的(m+1-k)*第三層的(m+1-k)*第四層的(m+1-k) = 4X3X2X1 = 24
說白了就是n！
感覺像是廢話，，因為我是在拿結果推程序hhh
希望能幫到大家，一同學習，有錯誤歡迎指正
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/26456.html
標籤：其他
上一篇：HNUCM2020年湖南省大學生計算機程式設計競賽第1場選拔賽題解
下一篇：永久免費的遠程桌面軟體