2025.4.18 学习笔记 (递归）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

2025.4.18 学习笔记 (递归）

作者：

jwh , 2025-04-18 19:49:41 · 安徽 , 所有人可见 , 阅读 3

递归

概念：递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规
更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。
int func(传入数值) {
  if (终止条件) return 最小子问题解;
  return func(缩小规模);
}

第一题：递归字符串问题


#include<bits/stdc++.h>
using namespace std;
char CH;

string f( char ch ){
    if ( ch == 'A') return "A";
    string ff = f ( ch-1 );
    return ch + ff + ch + ff + ch;
}

int main()
{
    cin >> CH;
    cout << f( CH );
    return 0;
}

第二题：汉诺塔问题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n;
void solve(int n,char a,char b,char c)
{
    if(n==1) cout<<1<<" "<<a<<" "<<c<<endl;
    else
    {
        solve(n-1,a,c,b);
        cout<<n<<" "<<a<<" "<<c<<endl;
        solve(n-1,b,a,c);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    solve(n,'A','B','C');
    return 0;
}

第三题：求X的Y次方
快速幂的递归写法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int m = 100000007;
ll x,y;
ll solve(ll a,ll b)
{
    if(b==1) return a%m;
    ll ans=solve(a,b/2);
    ans=(ans*ans)%m;
    if(b%2==1) ans=(ans*a)%m;
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>x>>y;
    cout<<solve(x,y);
    return 0;
}

第四题：二进制字符串中的第K位

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,k;
string solve(int n,int k)
{
    if(n==1) return "0";
    int len=(1<<n)-1;
    if(k==len/2+1) return "1";
    if(k<len/2+1) return solve(n-1,k);
    //k在中点之后，对Sn-1先翻转（即reverse）中点之后的所有字符，再反转（即invert）
    //len-k+1对应的是以len/2为中心对称的位置
    //例如： s="abcdefg"  len==7,c:3,e:5   5=7-3+1;3=7-5+1     
    return solve(n-1,len-k+1)=="0"?"1":"0";
}
int main()
{
    cin>>n>>k;
    cout<<solve(n,k);
    return 0;
}

第五题：递归实现排列型枚举

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> q;
bool st[100];
void dfs(int t)
{
    if(t==n)
    {
        for(int i=0;i<q.size();i++) cout<<q[i]<<" ";
        cout<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            q.push_back(i);
            dfs(t+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    dfs(0);
    return 0;
}

第六题：递归实现指数型枚举

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n;
int st[100];
void dfs(int t)
{
    if(t>n)
    {
        for(int i=1;i<=n;i++)
        {
            if(st[i]) cout<<i<<" ";
        }
        cout<<endl;
        return;
    }
    st[t]=false;
    dfs(t+1);
    st[t]=true;
    dfs(t+1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    dfs(1);
    return 0;
}

第七题：递归实现组合型枚举

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
bool st[100];
void dfs(int t,int k)
{
    if(k==m)
    {
        for(int i=1;i<=n;i++)
        {
            if(st[i]) cout<<i<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=t;i<=n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            dfs(i,k+1);
            st[i]=false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    dfs(1,0);
    return 0;
}

第七题：排列1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
bool st[100];
vector<int> q;
void dfs(int k)
{
    if(q.size()==m)
    {
        for(int i=0;i<q.size();i++)
        {
            cout<<char(q[i]+'a');
        }
        cout<<endl;
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            q.push_back(i);
            dfs(k+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        st[i]=true;
        q.push_back(i);
        dfs(1);
        st[i]=false;
        q.pop_back();
    }
    return 0;
}

第八题：排列3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
bool st[100];
vector<int> q;
void dfs(int k)
{
    if(q.size()==m)
    {
        for(int i=0;i<q.size();i++)
        {
            cout<<char(q[i]+'a');
        }
        cout<<endl;
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(!st[i]&&abs(q[q.size()-1]-i)!=1)
        {
            st[i]=true;
            q.push_back(i);
            dfs(k+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        st[i]=true;
        q.push_back(i);
        dfs(1);
        st[i]=false;
        q.pop_back();
    }
    return 0;
}

第九题：排列4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
bool st[100];
vector<int> q;
void dfs(int k)
{
    if(q.size()==m)
    {
        for(int i=0;i<q.size();i++)
        {
            cout<<q[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i]&&__gcd(q[q.size()-1],i)==1)
        {
            st[i]=true;
            q.push_back(i);
            dfs(k+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        st[i]=true;
        q.push_back(i);
        dfs(1);
        st[i]=false;
        q.pop_back();
    }
    return 0;
}

第十题：组合1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
bool st[100];
vector<int> q;
void dfs(int t,int k)
{
    if(q.size()==m)
    {
        for(int i=0;i<q.size();i++)
        {
            cout<<char(q[i]+'a');
        }
        cout<<endl;
        return;
    }
    for(int i=t;i<n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            q.push_back(i);
            dfs(i,k+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        st[i]=true;
        q.push_back(i);
        dfs(i,1);
        st[i]=false;
        q.pop_back();
    }
    return 0;
}

第十一题：组合2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
bool st[100];
vector<int> q;
void dfs(int t,int k)
{
    if(q.size()==m)
    {
        for(int i=0;i<q.size();i++)
        {
            cout<<char(q[i]+'a');
        }
        cout<<endl;
        return;
    }
    for(int i=t;i<n;i++)
    {
        if(!st[i]&&abs(q[q.size()-1]-i)!=1)
        {
            st[i]=true;
            q.push_back(i);
            dfs(i,k+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        st[i]=true;
        q.push_back(i);
        dfs(i,1);
        st[i]=false;
        q.pop_back();
    }
    return 0;
}

第十二题：组合3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
bool st[100];
vector<int> q;
void dfs(int t,int k)
{
    if(q.size()==m)
    {
        for(int i=0;i<q.size();i++)
        {
            for(int j=i+2;j<q.size();j++)
            {
                if(__gcd(q[i],q[j])!=1) return;
            }
        }
        for(int i=0;i<q.size();i++)
        {
            cout<<q[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=t;i<=n;i++)
    {
        if(!st[i]&&__gcd(q[q.size()-1],i)==1)
        {
            st[i]=true;
            q.push_back(i);
            dfs(i,k+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        st[i]=true;
        q.push_back(i);
        dfs(i,1);
        st[i]=false;
        q.pop_back();
    }
    return 0;
}

第十三题：单词接龙
纯dfs过不去，需要进行剪枝操作，每次新加入一个字符串时，判断它与上一个字符串能否配对，不能就直接retrun;

#include<bits/stdc++.h>
using namespace std;
int n;
vector<string> q;
string a[20];
bool st[100];
bool falg=false;
bool solve()
{
    char tail=q[0][q[0].size()-1];
    for(int i=1;i<q.size();i++)
    {
        if(q[i][0]!=tail)
        {
            return false;
        }
        tail=q[i][q[i].size()-1];
    }
    return true;
}
void dfs(int t)
{
    if(falg==true) return;
    if(q.size()>=2)
    {
        string s1=q[q.size()-1];
        string s2=q[q.size()-2];
        if(s2[s2.size()-1]!=s1[0]) return;
    }
    if(t==n)
    {
        if(solve())
        {
            falg=true;
            return;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            q.push_back(a[i]);
            dfs(t+1);
            st[i]=false;
            q.pop_back();   
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    dfs(0);
    if(falg) cout<<1<<endl;
    else cout<<0<<endl;
    return 0;
}

第十四题： K数和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
bool st[100];
vector<int> q;
int a[100];
int ans;
void dfs(int t,int k)
{
    if(q.size()==m)
    {
        int cnt=0;
        for(int i=0;i<q.size();i++)
        {
            cnt+=q[i];
        }
        if(cnt==0) ans++;
        return;
    }
    for(int i=t;i<n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            q.push_back(a[i]);
            dfs(i,k+1);
            st[i]=false;
            q.pop_back();
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++)
    {
        st[i]=true;
        q.push_back(a[i]);
        dfs(i,1);
        st[i]=false;
        q.pop_back();
    }
    cout<<ans<<endl;
    return 0;
}

0 评论

App 内打开