深搜dfs

佚名 6年前 (2019-05-16) 随笔 1428人围观抢沙发百度已收录

今天复习

深搜

即深度优先搜索算法,主要解决的问题是不确定深度的搜索问题.

主要基于的思想是递归的回溯

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

先来一道例题

eg.1 组合数

代码很简单

#include<iostream>
#include<math.h>
#include<iomanip>
#include<stdio.h>
using namespace std;
const int maxn=100007; 
int n,r;
int f[maxn];
void init()
{
    for(int i=1;i<=r;i++){
        f[i]=0;
    }
}
void dfs(int a,int b)
{
    if(b==r){
        for(int i=1;i<=r;i++){
            printf("%3d",f[i]);
        }
        cout<<endl;
        return ;
    }
    for(int i=a+1;i<=n;i++){
        f[b+1]=i;
        dfs(i,b+1);
    }
}
int main()
{
    cin>>n>>r;
    init();
    dfs(0,0);
}

eg.2 自然数拆分

代码很也简单

#include<iostream>
#include<math.h>
#include<iomanip>
#include<stdio.h>
using namespace std;
const int maxn=100007; 
int n,r;
int f[maxn];
int v[maxn];
void dfs(int a,int b,int sum)
{
    if(sum==n){
    //  cout<<n<<"=";
        for(int i=1;i<b;i++){
            cout<<f[i]<<"+";
        }
        cout<<f[b]<<endl;
        return ;
    }
    for(int i=a;i<=n-sum&&i!=n;i++){
        f[b+1]=i;
        dfs(i,b+1,sum+i);
    }
}
int main()
{
    cin>>n;
    dfs(1,0,0);
}