《算法进阶指南》- 0.2递推与递归

2021-12-28 09:19:37


总结：递归、递推提高效率,其他题还好一些，此章解决了我之前对汉诺塔的疑惑，提升了对二进制表示状态的理解，但最后一题分形之城还是有点模糊，在后续学习中常回头。


递归

>递归实现指数型枚举

dfs写法是对于每一位，走两条路：选或者不选，当对n个路口都做出选择时，输出结果。

#include<iostream>
using namespace std;

int n;

void dfs(int u,int state)
{
    if(u == n)
    {
        for(int i = 0;i < n;i++)
         if(state>>i & 1)
          cout<<i + 1<<' ';

        puts("");
        return ;
    }
    //不选
    dfs(u + 1,state);

    //选
    dfs(u + 1,state | 1 << u);
}

int main()
{
    cin>>n;
    dfs(0,0);
    return 0;
}

暴力写法则是枚举所有状态，输出方案。

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    for(int i = 0;i < (1 << n) ;i++)
    {
        for(int j = 0;j < 15;j++)
        {
            if(i >> j & 1) cout<<j + 1<<' ';
        }
        puts("");
    }
    return 0;
}

>递归实现组合型枚举

跟指数型枚举类似，多了一维表示当前选了几个的参数,对于每一个位，选或者不选两条分支，当前已经选了m个时，输出方案。

#include<iostream>
using namespace std;

int n,m;

void dfs(int u,int cnt,int state)
{
    if(cnt == m)
    {
        for(int i = 0;i < n;i++)
         if(state>>i & 1)
          cout<<i + 1<<' ';
        
        puts("");
        return ;
    }
    if(u == n) return ;
    //选
    dfs(u + 1,cnt + 1,state | 1 << u);
    
    //不选
    dfs(u + 1,cnt,state);
    
}

int main()
{
    cin>>n>>m;
    dfs(0,0,0);
    return 0;
}

>递归实现排列型枚举

典型dfs，依次填数，之前没用过的话才能用，依次遍历没用过的，放满了就输出。注意要恢复状态(回溯)

#include<bits/stdc++.h>

using namespace std ;

vector<int> path;

int n;

void dfs(int u,int state)
{
    if(u == n) 
    {
        for(int i = 0;i < n;i++)
         cout<<path[i]<<' ';

        puts("");
        return ;
    }

    for(int i = 0;i < n;i++)
    {
        if(!(state>>i & 1))
        {
            path.push_back(i + 1);
            dfs(u + 1,state | (1 << i));
            path.pop_back();
        }
    }
}

int main()
{
    cin>>n;
    dfs(0,0);
    return 0;
}

>约数之和

等比数列的和可以通过分治，配合快速幂在\(log(c)\)的时间内求出

《算法进阶指南》- 0.2递推与递归

#include<iostream>
using namespace std;

const int mod = 9901;

int qmi(int a,int b)//快速幂
{
    a %= mod;
    int res = 1;
    while(b)
    {
        if(b&1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int sum(int p,int c)//分治求sum
{
    if(c == 0) return 1;
    if(c & 1) return (1 + qmi(p,(c + 1 )/ 2)) % mod * sum(p,(c - 1) / 2) % mod;
    return ((1 + qmi(p,c / 2)) % mod * sum(p,(c / 2) - 1) + qmi(p,c)) % mod;
}
int main()
{
    int a,b;
    cin>>a>>b;

    int res = 1;
    for(int i = 2;i <= a;i++)
    {
        int s = 0;
        while(a % i == 0)
        {
            s++;
            a /= i;
        }
        if(s) res  = res * sum(i,s * b) % mod;
    }
    
    if(!a) res = 0;
    cout<<res<<endl;
    
    return 0;
}

此题有点模糊

>分形之城

根据给的等级，编号找到其对应的坐标，然后根据题目中的等级一进行坐标变换。优质题解 

#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;


typedef long long LL;
typedef pair<LL,LL> PLL;

PLL cacl(LL n,LL m)
{
    /*
      n:等级
      m：编号
    */
    
    if(n == 0) return {0,0};
    LL len = 1ll << (n - 1);//象限边长
    LL cnt = 1ll << (2 * n - 2);//等级n - 1中容量
    PLL pos = cacl(n-1,m % cnt);
    LL x = pos.first,y = pos.second;
    int z = m / cnt;//处于哪个象限
    
    if(z == 0)  return {-y - len,-x + len};
    else if(z == 1) return {x + len,y + len};
    else if(z == 2) return {x + len,y - len};
    return {y - len,x - len};
}


int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        LL N,A,B;
        cin>>N>>A>>B;
        
        auto ac = cacl(N,A-1);
        auto bc = cacl(N,B-1);
        
        double x = ac.first - bc.first, y = ac.second - bc.second;
        printf("%.0lf\n",sqrt(x * x + y * y) * 5);
    }
    return 0;
}

递推

>费解的开关

枚举第一行按哪个的所有状态(\(2^5\)种)，这样按后已经确定第一行。例如：确定状态后，第一行是0，只能通过按第二行来改变成1，这样依次推下去，如果最后一行都为1的话说明是个合法方案，统计最少操作次数。

#include<iostream>
#include<cstring>

using namespace std;

const int INF = 100000;

char g[10][10];
int dx[] = {0,-1,0,1,0}, dy[] = {0,0,1,0,-1};

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 < 5 && b >= 0 && b < 5)
        {
            g[a][b] = '0' + !(g[a][b] - '0');
        }
    }
}

int work()
{
    int ans = INF;
    for(int k = 0;k < 1 << 5;k++)//枚举第一行按哪个灯
    {
        int res = 0;
        char backup[10][10];
        memcpy(backup,g,sizeof g);

        for(int i = 0;i < 5;i++)
        {
            if(k >> i & 1)
            {
                res++;
                turn(0,i);
            }
        }

        for(int i = 0;i < 4;i++)
         for(int j = 0;j < 5;j++)
         {
             if(g[i][j] == '0')
             {
                 res++;
                 turn(i + 1,j);
             }
         }

        bool is_successful = true;

        for(int j = 0;j < 5;j++)//看下最后一行是否全是1
          if(g[4][j] == '0')
          {
               is_successful = false;
               break;
          }

        if(is_successful) ans = min(ans,res);
        memcpy(g,backup,sizeof g);//复原数组

    }

    if(ans > 6) return -1;

    return ans;
}

int main()
{
    int T;
    cin>>T;

    while(T--)
    {
        for(int i = 0;i < 5;i++) cin>>g[i];
        cout<<work()<<endl;
    }
    return 0;
}

>奇怪的汉诺塔

在四个柱子的情况下，移动j个到b柱。之后只能放在剩下的三个柱子上，这样问题就转化为最基本的汉诺塔问题，把剩下的放到d柱子上，再把那j个放到d柱上，完成一次方案。

最基本的汉诺塔问题，是先把n-1 个圆盘放到b上，然后把最后一个圆盘放到c上，再把n-1个圆盘放到c上，完成，得出递推式为:f[n] = f[n-1] + 1 + f[n-1]
《算法进阶指南》- 0.2递推与递归

#include<iostream>
#include<cstring>
using namespace std;

int d[13],f[13];
int main()
{
    d[1] = 1;
    for(int i = 2;i <= 12 ;i++) d[i] = 1 + d[i-1] * 2;//预处理三柱模式的方案数

    memset(f,0x3f,sizeof f);
    f[1] = 1;
    for(int i = 1;i <= 12;i++)
     for(int j = 0;j < i;j++)
      f[i] = min(f[i],f[j] * 2 + d[i - j]);//四柱模式下,先把j个移动到b柱,然后在三柱子模式下，把剩下的移动到目标柱,然后再把j个移动到目标柱

    for(int i = 1;i <= 12;i++)
     cout<<f[i]<<endl;

    return 0;
}

三个柱子的汉诺塔问题

//汉诺塔方案
#include<iostream>
using namespace std;

int hanoi(int step)
{
   if(step == 1) return 1;
   return hanoi(step - 1) * 2 + 1;
}

int main()
{
    int n;
    cin>>n;
    cout<<hanoi(n)<<endl;
    return 0;
}
//汉诺塔实现
#include<iostream>
using namespace std;

void hanoi(int n,char a,char b,char c)
{
    if(n == 1)
    {
        printf("%c -> %c\n",a,c);
        return ;
    }else {
        //从a柱子移动到b柱
        hanoi(n-1,a,c,b);
        //把n-1个移完之后，把最大的那个移动到c柱
        printf("%c -> %c\n",a,c);
        //把n-1堆移动到c柱
        hanoi(n-1,b,a,c);
    }
}
上一篇：[exaqp]初赛复习大纲


下一篇：关于vector遍历erase的方法记录