请选择 进入手机版 | 继续访问电脑版
  • 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

深度优先搜索的递归实现思路及实例源码(C++)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

摘要:本文简要介绍了深度优先搜索的递归实现思路给出了几个实例的源码

关键字:深度优先,递归,组合,整数划分,连续整数和

递归深度优先的核心思想是对于当前节点(设深度为K),如果该节点合乎结题要求,就遍历当前节点所有可

扩展节点并递归调用搜索方法(进入K+1深度)。算法的基本框架如下:

1.定义数组int x[N],用于记录可用节点的索引,其中N为解空间的长度。

2.定义判断节点是否满足条件的函数

3.定义搜索函数


bool canuse(int k)
{
    if(x[k]满足条件)return true;
    return false;
}
void search(int k)
{
    if(满足条件(例如k到达某一深度)) 输出结果;
    for(int i = 1 to n)//遍历每一个可能的扩展节点
    {
        x[k] = i;
        if(canuse(k)) search(k + 1);

    } 
}

下面给出两个使用上面思想的解决问题的实例

/*
 * 在N个数种选M个数的组合
 * Compiler: VC++ 6.0
 */
#include 

using namespace std;

#define N 9
#define M 5

int array[N]={1,2,3,4,5,6,7,8,9};

int x[N];
bool canuse(int k)
{
    if(k == 0 || k > 0 && x[k] > x[k - 1])
    {
        return true;
    }
    return false;
}

void print()
{
    for(int i = 0; i < M; ++i)
    {
        cout << array[x[i]] << " ";
    }
    cout << endl;
}

void search(int k)
{
    if(k == M)
        print();
    for(int i = 0; i < N; ++i)
    {
        x[k] = i;
        if(canuse(k)) search(k + 1);
    }

}


int main(int argc, char* *argv)
{
    search(0);
    system("pause");
    return 0;
}

/*
 * 采用递归实现的深度搜索算法
 * 编译器: VC++ 6.0
 */

//例一:整数划分
/* 问题描述,如下所示:
   5=5
   5=4+1
   5=3+3
   5=3+2
   5=3+1+1
   5=2+2+1
   5=2+1+1+1
   5=1+1+1+1+1
   一个整数可以表示为其他整数的和,
   要求使用程序输出所有这样的组合
   */
#include 
using namespace std;

#define N 100

int x[N];

void print_result(int k)
{
    cout << "=" << x[0];
    for(int i = 1; i < k; ++i)
        cout << "+" << x[i];
    cout << endl;
}

bool canuse(int depth)
{
    if(depth == 0 || x[depth] <= x[depth -1])
    {
        return true;
    }
    return false;
}

void search(int remainder, int depth)
{
    if(remainder == 0) print_result(depth);
    for(int num_try = remainder; num_try > 0; --num_try)
    {
        x[depth] = num_try;
        if(canuse(depth))
            search(remainder - num_try, depth + 1);
    }
}

int main(int argc, char* *argv)
{
    int n;
    while(cin>>n && n > 0 && n < N)
    {
        search(n, 0);
    }
    return 0;
}

/*
 * 将一个整数表示为连续自然数之和
 * 1+2=3
 * 4+5=9
 * 2+3+4=9
 */

#include 

using namespace std;

#define N 1000
int a[N];
bool canuse(int depth)
{
    if(depth == 0 || a[depth] == a[depth - 1] + 1)
        return true;
    return false;
}

void print(int depth)
{
    for(int i = 0; i < depth; ++i)
        cout << a[i] <<" ";
    cout << endl << endl;
}

void search(__int64 reminder, int depth)
{
    if(reminder == 0 && depth > 1) print(depth);
    for(__int64 i = reminder; i > 0; i--)
    {
        a[depth] = i;
        if(canuse(depth))
            search(reminder - i, depth + 1);
    }
}

鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
中缀表达式转化为后缀表达式[附C++源码](原创)发布时间:2022-05-14
下一篇:
组合算法的递归实现(C版)发布时间:2022-05-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap