[数据结构与算法]蓝桥（一）——递归与递推

一.递归

1.概念

递归是编程技巧，直接体现在代码上 ，即函数自己调用自己，每一层递归调用，传入的参数的值并不完全一样；
递归函数基于自顶向下拆分问题，再自底向上逐层解决问题的思想设计而成，这是所熟知的分而治之的算法思想。——>把问题分解为若干个子问题，从树根到树叶
举例：斐波那契数列
输入一个数n,求其斐波那契值
int Fibonacci(int n){
if(n==1)return 1;
if(n==2)return 2;
return Fibonacci(n-1)+Fibonacci(n-2);
}
一个递归的过程一定对应一棵递归搜索树

时间复杂度：O（2n )

2²⁰ =100w
2^16 ^=65536
2¹⁵ =32768

2.例题

例题1.递归实现指数型枚举

● 每个数选和不选有两种情况，总共2n 种情况，每个方案长度为n
● 时间复杂度：O（n2n )
● 递归最重要的是顺序，把所有方案不重不漏的找出来，从1~n依次考虑每一个数，选或不选->形成一棵二叉搜索树
● 在从子节点返回父结点时（回溯）,需要恢复现场

#include <iostream>
using namespace std;
int n;
const int N=16;
int st[N];//判断位的数是否选中,0表示未考虑，1表示选中，2表示未选中
//u表示当前选到第几个数->对应二叉树的第几层
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++){
            if(st[i]==1){
                printf("%d ",i+1);
            }
        }
        printf("\n");
        return;
    }
    //遍历可能出现的分支
    for(int i=1;i<=2;i++){
        st[u]=i;
        dfs(u+1);
        //恢复现场
        st[u]=0;
    }
    
}

int main(){
    scanf("%d",&n);
    dfs(0);
    return 0;
}

例题2.递归实现排列型枚举

9！=32680
时间复杂度：O(nn!)
顺序1：依次枚举每个数放到哪个位置
顺序2：依次枚举每个位置放哪个数

第0层：n个for循环
第1层：n个for循环n个分支
第2层：n个for循环n(n-1)个分支
…
第n层：n个for循环n!个分支
总共的时间复杂度：n(1+n+…+n!)≤n*(3n!)

#include <iostream>
using namespace std;
const int N=10;
int n;
int st[N];
bool used[N];//判断数字是否被使用过
void dfs(int u);
int main(){
    scanf("%d",&n);
    dfs(0);
    return 0;
}
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;++i){
            printf("%d ",st[i]);
        }
        printf("\n");
    }
    for(int i=1;i<=n;++i){
       if(!used[i]){
           st[u]=i;
           used[i]=true;
           dfs(u+1);
           st[u]=0;
           used[i]=false;
       }
       
    }
    
    
}

例题3.递归实现组合型枚举

排序：只要保证当前新加的数大于前一个数即可

#include <iostream>
using namespace std;
int n,m;
const int N=26;
int st[N];
//bool used[N];
void dfs(int u);
int main(){
    scanf("%d%d",&n,&m);
    dfs(0);
    return 0;
}
void dfs(int u){
   
    if(u==m){ 
        //printf("start\n");
        for(int i=0;i<m;i++){
            printf("%d ",st[i]);
        }
        printf("\n");
    }
    
    for(int i=1;i<=n;i++){
        if(st[u]==0&&(u==0||i>st[u-1])){
            st[u]=i;
            dfs(u+1);
            st[u]=0;
        }
    }
}

优化：剪枝
● 当前选第u个数,已经选了u-1个数，如果把这u-1后面的数都选上了，还小于m，可以直接返回
● (u-1)+(n-st[u-1]+1)<m
● u+n-st[u-1]<m

#include <iostream>
using namespace std;
int n,m;
const int N=26;
int st[N];
//bool used[N];
void dfs(int u,int start);
int main(){
    scanf("%d%d",&n,&m);
    dfs(0,1);
    return 0;
}
void dfs(int u,int start){
    if(u+n-st[u-1]<m)return;
    if(u==m){ 
        for(int i=0;i<m;i++){
            printf("%d ",st[i]);
        }
        printf("\n");
    }
    
    for(int i=start;i<=n;i++){
            st[u]=i;
            dfs(u+1,i+1);
            st[u]=0;
    }
}

例题4.带分数

n=a+b/c a,b,c出现且仅出现一次
法一：
● 全排列划为3段 a|b|c 枚举位数，a,b位数确定后c也确定

1. 枚举全排列
2. 枚举位数
3. 判断

#include <iostream>
using namespace std;
const int N=10;
bool used[N];
int st[N];
int cnt;
int target;
int calc(int l,int r){
    int sum=0;
    for(int i=l;i<=r;i++){
        sum=sum*10+st[i];
    }
    //printf("%d\n",sum);
    return sum;
}

void dfs(int u){
    if(u==9){
       for(int i=0;i<7;i++){
           for(int j=i+1;j<8;j++){
               int a=calc(0,i);
               int b=calc(i+1,j);
               int c=calc(j+1,8);
               //c++中除法是整除，所以要转成加减乘判断
               if(a*c+b==c*target)cnt++;
           }
       }
       return;
    }
    
    for(int i=1;i<=9;i++){
       if(!used[i]){
           st[u]=i;
           used[i]=true;
           dfs(u+1);
           used[i]=false;
       }
    }
}
int main(){
    scanf("%d",&target);
    dfs(0);
    printf("%d",cnt);
    return 0;
}

法二：剪枝
● cn=ca+b
● 枚举a和c，b可以直接算出来
注意a<=n ,c小于8位数

1. 先枚举a
2. 对于每一个枚举的a，枚举下c
3. 对于每一个枚举的ac,判断b是否符合条件

#include <iostream>
#include <cstring>
using namespace std;
const int N=10;
bool used[N],backup[N];
int ans,target;
bool check(int a,int c){
    long long b=(long long)c*target-(long long)c*a;
    if(!b)return false;
    memcpy(backup,used,sizeof used);
    
    while(b){
       int x=b%10; 
       b/=10;
       if(!x||backup[x])return false;
       else  backup[x]=true;
    }
    
    for(int i=1;i<=9;i++){
        if(!backup[i])return false;
    }
    return true;
}
void dfs_c(int u,int a,int c){
    if(u>8)return;
    if(a&&c){
        if(check(a,c))ans++;
    }
    for(int i=1;i<=9;i++){
        if(!used[i]){
            used[i]=true;
            dfs_c(u+1,a,c*10+i);
            used[i]=false;
        }
    }
   
  
}
void dfs_a(int u,int a){
    if(a>=target)return;
    if(a)dfs_c(u,a,0);
    for(int i=1;i<=9;i++){
        if(!used[i]){
            used[i]=true;
            dfs_a(u+1,a*10+i);
            used[i]=false;
        }
    }
}

int main(){
    scanf("%d",&target);
    dfs_a(0,0);
    printf("%d",ans);
    return 0;
}

二、递推

1.概念

先解决所有子问题，再用子问题把原问题直接计算出来

2.例题

例题1.简单斐波那契

#include <iostream>
using namespace std;
const int N=50;
int f[N];
int F(int n){
    f[0]=0;
    f[1]=1;
    for(int i=2;i<=n;i++){
        f[i]=f[i-1]+f[i-2];
    }
    return f[n];
}
int main(){
    int n;
    scanf("%d",&n);
    F(n);
    for(int i=0;i<n;i++){
        printf("%d ",f[i]);
    }
    return 0;
}

优化：
#include <iostream>
using namespace std;
int main(){
    int n,a,b,c;
    scanf("%d",&n);
    a=0;
    b=1;
    for(int i=1;i<=n;i++){
        printf("%d ",a);
        c=a+b;
        a=b;
        b=c;
    }
    
    return 0;
}

例题2.费解的开关

宏观：
所有开关问题共同点
● 按法和顺序没有关系
● 每个格子最多只能按一次，按两次相当于没按，还多了两步

1. 枚举第一行的操作
2. 第二行发现能改变开关的位置只有第一行暗的的下一行位置
   ● 上一行为暗的，下一行必须按
   ● 上一行为亮的，下一行不能按
   ● 每一行开关操作完全由上一行灯的亮灭状态唯一确定
3. 操作完之后可以保证前n-1行灯是亮的
   ● 此时如果灯是全亮的说明合法
   ● 灯是全灭的说明不合法
   如果完全暴力解，枚举所有可能，时间复杂度O(2^25)
   细节：
4. 如何枚举第一行操作？
   a. 递归
   b. 二进制转为十进制 对应0~25 -1，所以只需要让i枚举0~31就行，i的第k位为i>>k&1
5. 如何写turn(int x,int y)?
   利用偏移量数组进行遍历
6. 时间复杂度
   32255500
   第一行32种状态25个开关turn5个开关500个数据

#include <iostream>
#include <cstring>
using namespace std;
const int N=6;
char matrix[N][N],backup[N][N];
int dx[5]={0,1,0,-1,0},dy[5]={1,0,-1,0,0};
void turn(int x,int y){
    for(int i=0;i<5;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<=4&&b>=0&&b<=4){
            //字符类型的'0'转'1',可以利用ascii转化
            matrix[a][b]^=1;
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    
    while(n--){
        
        for(int i=0;i<5;i++){
            cin>>matrix[i];
        }
      
        int ans=10;
        memcpy(backup,matrix,sizeof matrix);
        for(int op=0;op<32;op++){
           
            int step=0;
            
            for(int k=0;k<5;k++){
                if(op>>k&1){
                    turn(0,k);
                    step++;
                }
            }
            for(int i=0;i<4;i++){
                for(int j=0;j<5;j++){
                    if(matrix[i][j]=='0'){
                        turn(i+1,j);
                        step++;
                    }
                }
            }
            bool flag=true;  
            for(int i=0;i<5;i++){
                if(matrix[4][i]=='0'){
                    flag=false;
                    break;
                }
            }
           
            if(flag)ans=min(ans,step);
            memcpy(matrix,backup,sizeof backup);
         
        }
      
        if(ans>6)puts("-1");
        else printf("%d\n",ans);
        
        
    }
    return 0;
    
    
    
}

例题3.翻硬币

法一：
● 给定初始状态和一些操作，问到达目标状态，最少需要操作几步
● 最常用做法bfs，适用于状态数不多的情况
● eg.八数码问题
这道题最多需要step=50,每步有99种选择 共5099 ，太大了
法二：
利用递推简化，类似上一题做法
● 看起来很像dp问题，dp本质也是递推，dp是有向无环最短路
这道题改成一个开关控制3个灯也可以，只要能保证按照顺序按开关，每次只会有一个开关影响某个灯泡

#include <iostream>
using namespace std;
const int N=110;
char str[N],ans[N];
void turn(int i){
    if(str[i]=='o')str[i]='*';
    else str[i]='o';
}
int main(){
    cin>>str;
    cin>>ans;
    int len=sizeof(str);
    int step=0;
    for(int i=0;i<len-1;i++){
        if(str[i]!=ans[i]){
            turn(i);
            turn(i+1);
            step++;
        }
    }
    cout<<step;
    
    
    return 0;
}

例题4.飞行员兄弟

● 按一次直接影响一行一列，每个灯泡可以被非常多的开关控制，很难递推出来
● 但好在数据量较小，可以用暴力枚举 216 =65536

1. 枚举所有方案 0~216 -1，
2. 按照该方案对所有开关进行操作
3. 如果灯泡全亮，记录方案
   时间复杂度：
4. 216 （167+16+16）
   ● 216 种可能（16个开关7个改变+检查16+存储16）≈1000w
5. 输出
   a. 步数最小
   b. 字典序最小
   ● 对棋盘进行标号,棋盘是二维的，利用二进制可以转成一维的
   ● 当某两个数步数相同时（即方案包含的1个数相同时），应当优先枚举1更靠前的
   ● 或者步数相同时答案是否唯一
   0 1 2 3
   4 5 6 7
   8 9 10 11
   12 13 14 15

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=5;
char g[N][N],backup[N][N];
//获取当前位置编号
int get(int x,int y){
    return 4*x+y;
}
void turn_one(int x,int y){
    if(g[x][y]=='-')g[x][y]='+';
    else g[x][y]='-';
}
void turn_all(int x,int y){
    for(int i=0;i<4;i++){
        turn_one(x,i);
        turn_one(i,y);
    }
    turn_one(x,y);
}
int main(){
    for(int i=0;i<4;i++)cin>>g[i];
    vector<PII>ans;
    memcpy(backup,g,sizeof g);
    //枚举2^16种情况
    for(int op=0;op<1<<16;op++){
        vector<PII>temp;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(op>>get(i,j)&1){
                    turn_all(i,j);
                    temp.push_back({i,j});
                }
            }
        }
        //判断所有灯泡是否全亮
        bool flag=true;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(g[i][j]=='+'){
                    flag=false;
                    break;
                }
            }
        }
        if(flag&&(ans.size()==0||ans.size()>temp.size())){
            ans=temp;
        }
        memcpy(g,backup,sizeof backup);
    }
    printf("%d\n",ans.size());
    for(auto t:ans){
        printf("%d %d\n",t.first+1,t.second+1);
    }
    return 0;
}