参照计算机算法设计与分析(第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 swapPerm(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

希望能帮到大家,一同学习,有错误欢迎指正

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信