n的阶乘

1
2
3
4
int F(int n){
if(n == 0) return 1; //递归边界
else return F(n-1)*n; //递归式
}

Fibonacci数列第n项

1
2
3
4
int F(int n){
if(n == 0 || n == 1) return 1; //递归边界
else return F(n-1) + F(n-2); //递归式
}

全排列

  • $n$ 个整数能形成的所有排列,现在要按字典序从小到大输出1到n的全排列
  • 递归的角度考虑
    • 子问题:以1开头的全排列,以2开头的全排列…以n开头的全排列
    • 数组P:存放当前的排列,hashTable[x]:当x在P中时为True
    • 递归过程:假设!!已经填好了P[1]~P[i-1],开始填P[i]
      • 枚举1~n,如果x没有在P中,就填入P[i],设置hashTable[x] = True
      • 处理P[i+1] //即进行递归
      • 递归完成后,将hashTable[x]还原成False,因为还有x还可能填其它位置
    • 递归边界:当i达到n+1时,说明P的1~n都填好了,此时可以把P输出,生成排列,然后return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
const int maxn = 11;
int n, P[maxn];
bool hashTable[maxn];
void genP(int i){ //递归函数描述的是中间第i个状态的过程,每个状态不同点在于参数i不同

if(i == n+1){ //递归的边界
print(P);
return;
}
//当要填入P[i]时,枚举1~n,对于某个数x
for(x=1; x<=n; x++){
if(!hashTable[x]){ //如果不在P中
P[i] = x; //将其填到P中
hashTable[x] = True; //设置为True
genP(i+1); //去填下一个,下一个再不断递归下去
hashTable[x] = False; //填完以后(即解决了P[i]=x时的问题),还原状态,去枚举下一个数
}
}
}
genP(1);

有人是把hashTable[x]写成vis[x] 更具模板化。注意啊!!这个不是vis[i] 是vis[x]记录x是否在这个排列里面!

N皇后

  • n*n个格子放n个皇后,使得n个皇后两两不在同一行,同一列,同一条对角线,问合法方案数
  • 枚举:$n^2$ 个位置中选$n$ 个,枚举量$C_{n^2}^n$
  • 每行放一个,每列只放一个。那么n列肯定每列一个,其对应的行号是1~n的一个排列,比如24135
    • 即只要这个排列确定了,则放置的情况就确定了
    • 问题就转化为1~n的全排列,然后去看每个排列是否合法(因为还需满足不在同一对角线)

  • 不在同一对角线:列号i到j,对应行号P[i]到P[j]
    • 如果在对角线上,则满足$y=x, y=-x$
    • 所以不在同一对角线条件是,排列中任意两个i和j都有:$|i-j|!=|P[i]-P[j]|$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int cnt = 0;
void genP(i){
if(i == n + 1){ //此时排列已生成,开始判断合法
bool flag = false;
for(int i=1; i<=n; i++){
for(int j=i+1; j<=n; j++){
if(abs(i-j) == abs(P[i]-P[j])){
flag = true;
}
}
}
if(flag) cnt++;
return;
}
for(int x = 1; x <= n; x++){
if(!hashTable[x]){
P[i] = x;
hashTable[x] = true;
genP(i+1);
hashTable[x] = false; //x还可能去填其他位置
}
}

}
  • 优化:当放置了一部分皇后后,剩下的皇后怎么放都不可能合法,此时不需要再递归
    • 也可以这样想,前面的代码是全部放完,再去判断是否合法,这里可以每放一个,就判断一下,与前面已经放过的是否有冲突,如果有,就不需要再递归了
    • 之前的皇后j满足: pre<i, 它放置的位置为:P[pre]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int cnt = 0;
void genP(i){
if(i == n + 1){
cnt++;
return;
}
for(int x = 1; x<=n; x++){
if(hashTable[x] == false){
bool flag = true; //当准备放置时,开始判断合法
for(int pre = 1; pre<i; pre++){
if(abs(i-pre) == abs(x - P[pre])){
flag = false;
break;
}
}
if(flag){
P[i] = x;
hashTable[x] = true;
genP(i+1);
hashTable[x] = false;
}
}
}
}

吃糖果

  • 有N块糖果,每天可以吃一块或者两块巧克力,问方案数
  • $f[1]=1,f[2]=2,f[n]=f[n-1]+f[n-2]$
  • 对最后一天来说,有可能只吃了一块,那么方案数为$f(n-1)$
  • 或者两块,即$f(n-2)$

递归解法:(虽然完全没必要)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
using namespace std;
const int maxn = 100;

int f(int n){
if(n == 1 || n == 2) return n;
else return f(n-1)+f(n-2);
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
printf("%d\n",f(n));
}
}

神奇的口袋(子集和问题)

  • 从n个数中选若干个数,使之和为k的方案数

动态规划

$f[i][sum]$ 表示前i项中选若干项,其和为sum

$f[i][sum]=f[i-1][sum]+f[i-1][sum-a[i]]​$

考虑第i项选不选,两种情况如上,然后用递推的方式来解

递归

用一个dfs的模板,选好要变化的参数i和sum,表示此时轮到i状态了,前面的和为sum

用cnt来记录方案数。之前用的int dfs(); 没写出来。原因是什么呢?因为每次dfs返回的值不是方案数,dfs要递归到底以后才能看这个方案好不好。所以不如就void dfs(); 然后到递归边界时,cnt才看加不加1

1
2
3
4
5
6
7
8
9
10
11
int a[maxn],t, cnt;
void dfs(int i, int sum){
if(i == t){ //递归边界, 当i=t的时候,前面的0到t-1已经算过了
if(sum == 40){
cnt++;
}
return;
}
dfs(i+1, sum); //不选
dfs(i+1, sum+a[i]); //选
}

其实之前我一直在疑惑为什么这两个分支是写在一起的。其实可以把选或者不选看作一个二叉树,dfs(i+1,sum)这个分支就是计算i的所有左子树的方案和,然后dfs(i+1,sum+a[i])就计算i的所有右子树的方案和。反正先这么理解到。有多少分支,就这么写。

类似的题目

  • 能不能从n个数中选若干个数,使之和为k,输出true,false(挑战上的题目)
1
2
3
4
5
6
7
8
9
10
bool dfs(int i, int sum){
if(i == t){ //递归边界
if(sum == 40){
return true;
}
}
if(dfs(i+1, sum)) return true;
if(dfs(i+1, sum+a[i])) return true;
return false;
}

挑战是上面的写法,其实理解起来还行。可以这么想,要使第i个状态return true,就要他的子问题(i+1,sum)或者(i+1,sum+a[i])return true;一直递归下去就是最后sum==40才是true。否则就是false;不过我不喜欢这种写法。感觉有点混乱?

1
2
3
4
5
6
7
8
9
10
bool ans = false;
void dfs(int i, int sum){
if(i == t){ //递归边界
if(sum == 40){
ans = true;
}
}
dfs(i+1, sum);
dfs(i+1, sum+a[i]);
}

只要中间某一个分支能让ans=true,那么ans就一直等于true了。主要是这个的递归返回边界就一个,我觉得比较好理解。。。

状态空间

一个神奇的说法,虽然我现在还理解不了。一个实际问题的各种可能情况构成的集合是状态空间!程序的运行是对状态空间的遍历。算法和数据结构可以通过划分,归纳,提取,抽象来提高程序遍历状态空间的效率。递推和递归就是遍历状态空间的两种方式。

多项式枚举

状态空间规模 $n^k $ 这时候用for循环或者递推。这个还是比较好理解。二重循环,三重循环嘛

指数型枚举

状态空间$k^n$ 。一般用位运算和递归!!!!!

比如说

  • 从1~n个整数中随机选任意多个,输出可能的选择方案。
    • 这就是!!!!!神奇的口袋问题呀!!!
    • 都是选或者不选的问题。
    • 状态数目$2^n$ ,你看,这是不是用递归!!!!

递归的时候改变的参数:i 表示前i个!!!和之前的类型题一模一样。边界也一样。然后用什么存可能的选择方案?vector数组!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> chosen;
void dfs(int i){
if(i == n+1){ //问题边界
for(int i=0;i<chosen.size();i++){
printf("%d ",chosen[i]);
}
return;
}
//不选i!为什么是不选i呢?因为直接就进入了下一个子问题!!!!然后一直递归到边界然后返回到这里才算执行完
dfs(i+1);
//选i!这里就先push进去!
chosen.push_back(i);
dfs(i+1); //然后再进入分支,递归直到边界(这时就产生了一个序列)再返回到这里算执行完这个函数
chosen.pop_back();//回到上一个问题前,要恢复现场,因为上一个问题还要执行第二个分支
}

对了,所谓回溯可不可以理解成在递归函数那个语句之后的语句?我觉得应该可以,因为这就是返回时的位置!

组合型枚举

状态空间$C_n^m$

  • 从1到n个中选择m个,输出可能的选择方案

因为上面的指数型枚举是包括这个组合枚举的。但是我们不是选任意多个,而是m个。当我们选择超出了m个,这时候问题就无解了。或者计时选上剩下的所有数也不够m个。这时我们不用再搜索,直接就return了。

就在dfs函数开头再添加一段

1
2
3
if(choose.size()>m||choose.size()+(n-i+1)<m){
return;
}

所以,如果能及时知道当前问题一定是无解的,就不需要达到问题边界再返回。

这样可以把时间复杂度从$2^n$ 降到$C_n^m$

虽然皇后问题属于组合型枚举,但是!!!状态空间还是太大了!!!要转换成排列型枚举来做!!!

排列型枚举

状态空间$n!$

  • 1~n的全排列

  • 把每个可用的数作为数列中的下一个数,求解“把剩余的n-1个数按照任意次序打乱”这个规模更小的子问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int order[20]; //数列
bool chosen[20]; //这个数是否已被选择
void dfs(int k){
if(k == n+1){
for(int i=1;i<=n;i++){
printf("%d ",order[i]);
}
return;
}
for(int i=1;i<=n;i++){ //去找每个可用的数
if(chosen[i]) continue;
order[k] = i;
chosen[i] = true;
dfs(k+1);
chosen[i] = false;
}
}

分治

  • 把一个问题变成若干规模更小的同类子问题,递归求解子问题,回溯的时候通过它们推导出原问题的解

  • POJ1845:$A^B$ 的所有约数之和mod9901

    • 约数,又称因数,a/b=0 ==>a称为b的倍数,b称为a的约数
    • 质因数:是质数,又是因数

    • 质因数分解: 每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的因数

  • 现在先用分治法求$sum(p,c)=1+p+p^2+…+p^c$

    • 就是求等比数列的和
  • to do