0%

递推和递归

递归与递推

“一个实际问题的遍历,就是对其状态空间的划分,提取,抽象和归纳,实现对状态空间的遍历,并提升效率”

递推和递归,就是从已知的状态空间边缘,求出整个状态空间

枚举形式 规模 方式
多项式 $n^k$ 循环,递推
指数 $k^n$ 递归,位运算
排列 n! 递归,next_permutation
组合 $C^{m}_{n}$ 递归+剪枝

多项式型遍历

十分常见….直接循环

指数型遍历

例题一

从1~n(n<20)这n个整数中随机选任意个,求全部方案

显然,每一个整数都有选或者不选,即方案有$2^n$种,我们可以用二进制位运算辅助求解

如果用递归,就是每次递归中走两条路,进入更小的状态空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int > chosen ;//记录被选择的数
void calc(int x){
if(x==n+1){//边界,打印该方案,然后return
for(int i=0;i<chosen.size();++i){
printf("%d",chosen[i]);
}
puts("");
return;
}

//分支一,不选x,进入下一步
calc(x+1);
//分支二,选x,进入下一步
chosen.push_back(x);
calc(x+1);
//回溯,这个程序是到边界时直接输出,不用保留
chosen.pop_back();
}

组合型遍历

例题一

从1~n中选m个,输出全部方案

把任意情况中的超出m的情况全部剪了,再把不可能达到m的也剪了

就是在指数枚举前加一段

1
2
3
if(chosen.size()>m|| chosen.sixe()+n-x+1<m){
return ;
}

排列型遍历

求1~n的全排列

用一个数组标志当前已经出现的,在递归中注意恢复状态

同时用一个数组记录路径,注意恢复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int order[20];
bool chosen[20];
void calc(int k){//排列中的第k位
if(k==n+1){
for(int i=1;i<=n;++i){
printf("%d",order[i]);
}
puts("");
return ;
}
for(int i=1;i<=n;++i){
if(chosen[i])continue;
order[k]=i;
chosen[i]=1;
calc(k+1);
chosen[i]=0;
order[k]=0;//不写没事
}
}

分治

将一个问题划分为若干同类子问题,并递归求解

分治求等比数列部分和

奇数时,对于

$sum(p,c)=1+p+p^2+…+p^c$

等于

$sum(p,c)=1+p+..+p^{(c-1/2)}+p^{(c+1)/2}+…p^c$

即$sum(p,c)=(1+p^{(c+1)/2})*sum(p,(c-1)/2)$

同理,偶数时有

$sum(p,c)=(1+p^{c/2})*sum(p,c/2-1)+p^c$

(就是把最后一项提出来)

配合快速幂,时间复杂度为$O(logc)$

分形

递归的机器实现