递归算法详解与应用

这篇具有很好参考价值的文章主要介绍了递归算法详解与应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

😽  PREFACE  
 🎁欢迎各位→点赞  👍 + 收藏  ⭐ + 评论  📝  
 📢系列专栏:  蓝桥杯  
 🔊本专栏涉及到的知识点或者题目是算法专栏的补充与应用  
 💪  种一棵树最好是十年前其次是现在

递归

递归实现指数型枚举

递归,算法,排列型枚举,组合型枚举

下面给出原理分析过程图:

递归,算法,排列型枚举,组合型枚举

本质就是数学里面的全排列

#include <iostream>
using namespace std;
const int N = 16;
int n;
int st[N];//表示状态:0代表考虑,1代表选择,2代表不选择

void dfs(int u)
{
    if (u > n)
    {
        for (int i = 1; i <= n; i++)
        {
            if (st[i] == 1)
            {
                printf("%d ", i);
            }
        }
        puts("");
        return;
    }
    else
    {
        st[u] = 1;//选择
        dfs(u + 1);
        st[u] = 0;//回溯

        st[u] = 2;//不选择
        dfs(u + 1);
        st[u] = 0;//回溯
    }
}

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

我们也可以优化一下,不用三个状态去表示,采用bool:

#include <iostream>
using namespace std;
const int N = 16;
int n;
bool vis[N];

void dfs(int u)
{
    if (u > n)
    {
        for (int i = 1; i <= n; i++)
        {
            if (vis[i])
            {
                printf("%d ", i);
            }
        }
        puts("");
        return;
    }
    else
    {
        vis[u] = true;
        dfs(u + 1);

        vis[u] = false;
        dfs(u + 1);
    }
}

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

其实不然,递归顾名思义,先递下去,还要归回来,

针对这里的代码,可能有些人认为不会执行下面的false:

递归,算法,排列型枚举,组合型枚举

dfs(u+1)运行之后不是还有个return吗,这时候就会返回上一级函数,执行下面的false子任务

递归,算法,排列型枚举,组合型枚举

回到递归树上对应的父亲节点,接着遍历父亲的其他儿子。他在这颗子树的遍历中,父亲节点选过的打上标记,子节点才不会选。dfs完相当于把这颗树遍历完了,所以这个树又可以选了。

递归实现排列型枚举

递归,算法,排列型枚举,组合型枚举

下面给出图解分析过程:

递归,算法,排列型枚举,组合型枚举

#include <iostream>
using namespace std;
const int N =10;
int path[N];//保存序列 
int state[N];//数字是否被使用过 
int n;

void dfs(int u)
{
    if(u>n)//数字填完了,输出 
    {
        for(int i=1;i<=n;i++)//输出方案 
        {
            cout<<path[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(!state[i])//如果数字i没有被用过 
            {
                path[u]=i;//放入空位 
                state[i]=1;//数字被用,修改状态 
                dfs(u+1);//填下一位 
                state[i]=0;//回溯,取出i 
            }
        }
    }
}

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

另外需要注意的是本题的时间复杂度是递归,算法,排列型枚举,组合型枚举

下面给出简易的证明:

递归,算法,排列型枚举,组合型枚举

递归实现组合型枚举

递归,算法,排列型枚举,组合型枚举

下面给出图解分析过程:

递归,算法,排列型枚举,组合型枚举

#include <iostream>
using namespace std;
const int N = 30;
int n, m;
int path[N];

void dfs(int u, int s)//u代表当前枚举到哪个位置,s代表当前最小可以从哪个数枚举
{
    if (u + n - s < m)  return;//剪枝:就算将剩下的数全部选中也凑不齐m个数,所以一定没有答案,所以减掉
    if (u == m + 1)
    {
        for (int i = 1; i <= m; i++)   cout << path[i] << " ";
        puts("");
        return;
    }
    else
    {
        for (int i = s; i <= n; i++)
        {
            path[u] = i;
            dfs(u + 1, i + 1);
            path[u] = 0;//回溯
        }
    }
}

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

带分数

递归,算法,排列型枚举,组合型枚举

分析过程:

递归,算法,排列型枚举,组合型枚举

#include <iostream>
using namespace std;
const int N = 10;
int target;//题目条件给的数
int num[N];//用来保存全排列的结果
bool used[N];//生成全排列的过程中标记是否被使用过
int cnt;//计数,最后的输出结果

int calc(int l, int r)//计算num数组中一段的数是多少
{
    int res = 0;
    for (int i = l; i <= r; i++)
    {
        res = res * 10 + num[i];//小学数学的加法进位
    }
    return res;
}


void dfs(int u)//生成全排列
{
    if (u == 9)
    {
        //要把全排列分成三段
        for (int i = 0; i < 7; i++)//这里的i是位置,跟else里面的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 (c * target == a * c + b)
                {
                    cnt++;
                }
            }
        }
        return;
    }
    else
    {
        for (int i = 1; i <= 9; i++)//这里的i是数字
        {
            if (!used[i])
            {
                used[i] = true;//只要进if里面来,就是标记使用
                num[u] = i;
                dfs(u + 1);
                used[i] = false;//回溯,还原现场
            }
        }
    }
}

int main()
{
    cin >> target;
    dfs(0);
    cout << cnt << endl;
    return 0;
}

本题是蓝桥杯某年省赛的原题,下面再给出一个直接调用 next_permutation() 函数的做法,可以代替手写暴搜来枚举全排列,蓝桥杯是可以使用这个函数的

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

const int N = 10;

int target;
int num[N];

int calc(int l, int r) 
{
    int res = 0;
    for (int i = l; i <= r; i++)
    {
        res = res * 10 + num[i];
    }
    return res;
}

int main() 
{
    cin >> target;
    for (int i = 0; i < 9; i++) 
    {
        num[i] = i + 1;
    }
    int cnt = 0;
    do
    {
        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);
                if (a == 0 || b == 0 || c == 0)//特殊情况,需要单独讨论一下
                {
                    continue;
                }
                if (a * c + b == c * target) 
                {
                    ++cnt;
                }
            }
        }
        // 调用函数生成全排列
    } while (next_permutation(num, num + 9));
    cout << cnt << '\n';
    return 0;
}

  • 为什么 next_permutation() 函数选用do-while循环结构?
    因为你初始化的时候数组是一种情况,直接全排列的话第一种情况直接就少掉了。这也是 next_permutation() 的一个固定方式。

[补充] next_permutation() 函数

另外补充一下 next_permutation() 函数的用法:

对于next_permutation函数,其函数原型为:

#include <algorithm>
bool next_permutation(iterator start,iterator end)

递归,算法,排列型枚举,组合型枚举

如果当前序列不存在下一个排列时,函数返回false,否则返回true

例:将1,2,3,4,5进行全排列

#include <iostream>  
#include <algorithm>  
using namespace std;
int main()
{
    int num[5] = { 1,2,3,4,5 };
    do
    {
        cout << num[0] << " " << num[1] << " " << num[2] <<" "<<num[3]<<" "<<num[4]<< endl;
    } while (next_permutation(num, num + 5));
    return 0;
}

如果将+5改为+2:

#include <iostream>  
#include <algorithm>  
using namespace std;
int main()
{
    int num[5] = { 1,2,3,4,5 };
    do
    {
        cout << num[0] << " " << num[1] << " " << num[2] <<" "<<num[3]<<" "<<num[4]<< endl;
    } while (next_permutation(num, num + 2));
    return 0;
}

递归,算法,排列型枚举,组合型枚举

由此可以看出,next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列,同时并改变num数组的值。

此外,需要强调的是,next_permutation()在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。文章来源地址https://www.toymoban.com/news/detail-426400.html

到了这里,关于递归算法详解与应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 排列(Amn)与组合(Cmn)算法详解

    不区分个体差异和顺序时用Cmn(m小n大),需要区分个体和顺序时候用Amn。 例1:从10个相同的球里取出5个球,不需要区分先后顺序,也不区分其他个体特征,一把抓过去够5个就行,这就是C510(m=5,n=10)。 例2:有10把凳子,需要安排10个人去坐,问有多少种可能性。这里,就需要体

    2024年02月04日
    浏览(40)
  • 【C++】 排列与组合算法详解(进阶篇)

    写在前面 我上次发了一篇题解:C++排列与组合算法详解 最开始,我是抱着水题解的想法写的,但却成为了阅读量 最高 的文章,没有之一。 所以今天咱们来重制一篇文章,介绍几个进阶优化版的算法。 算法1:朴素算法 思路 具体见 C++排列与组合算法详解 缺点 不能将结果取

    2024年02月13日
    浏览(40)
  • AcWing94. 递归实现排列型枚举:输出1~n的全排列

    把 1∼ n n n 这 n n n 个整数排成一行后随机打乱顺序,输出所有可能的次序。 一个整数 n n n 。 按照从小到大的顺序输出所有方案,每行 1 个。 首先,同一行相邻两个数用一个空格隔开。 其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。 1 ≤ n ≤

    2024年02月06日
    浏览(50)
  • 递归实现 组合问题+排列问题(DFS)

    目录 递归实现排列型枚举 递归实现排列类型枚举 II  递归实现组合型枚举 递归实现组合型枚举 II 递归实现指数型枚举 递归实现指数型枚举 II 递归不是循环,递归利用了系统栈,只要是函数都会被系统管理。当执行到函数地址入口时就会为函数在系统栈上分配一块内存。当

    2024年02月15日
    浏览(44)
  • 递归算法学习——全排列

    目录 ​编辑 一,问题描述 1.例子: 题目接口:  二,问题分析和解决 1.问题分析 2.解题代码 首先我们得来先看看全排列的问题描述。全排列问题的问题描述如下: 给定一个不含重复数字的数组  nums  ,返回其  所有可能的全排列  。你可以  按任意顺序  返回答案。 1.例

    2024年02月11日
    浏览(40)
  • 算法--排列组合

    2024年02月16日
    浏览(38)
  • java实现排列组合算法

    我这里只写了组合的算法。         假设现有 M=4 个数据 a,b,c,d。从中随机抽取n个数,n为1—4个数据进行组合。那么数学中的计算组合方式为C(4,1) + C(4,2) + C(4,3) + C(4,4)  = 4 + 6 + 4 + 1 = 15。那么共有15种组合方式。 方案一:此方法容易理解但是效率慢         我的做

    2024年02月13日
    浏览(48)
  • 【算法教程】排列与组合的实现

    在讲排列与组合之前,我们先定义数据元素类型Fruit 对N个不同元素进行排序,总共有多少不同的排列方式? 例子:某水果店有以下水果,请对所有水果进行全排列,请输出所有排列 排列算法的javascript实现模板(DSF,最优解in-place) 测试结果 对N个不同元素进行排序,总共有多少不

    2024年02月07日
    浏览(47)
  • 算法第二期——排列组合(Python)

    目录 排列函数permutations( ) 易错点 组合函数combinations( ) 手写排列和组合代码  1.暴力法/

    2023年04月18日
    浏览(36)
  • 递归算法详解与应用

    本文深入解析了递归算法,包括递归实现指数型枚举、排列型枚举、组合型枚举的原理和代码实现。同时介绍了使用next_permutation()函数来枚举全排列的方法。

    2023年04月27日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包