C++数据结构算法(四)递推与递归

简介: C++数据结构算法(四)递推与递归

递推思想简介:

递推,意思就是用已经有的信息一点点推出想要知道的信息。


比如,平面上有一个机器人,一开始在坐标(0,0)处,第一秒向东移动一米,第二秒向南移动两米,第三秒向西移动三米,第四秒向北移动四米……机器人一直按照这个规律移动下去。由于我们知道了最开始的时候机器人的位置,我们就可以一秒一秒地推算出接下来每一个时刻机器人的位置。这就是递推。


显然,如果我们用人脑去模拟一个递推算法,是比较简单的,因为“根据已有信息推出未知信息”是我们常用的思考方式,符合直觉。


如果用电脑运行递推算法,我们应该考虑使用循环。我们可以在循环的过程中使用数组和临时变量记录下来每一步递推的过程和结果。比如在刚刚的机器人例子中,我们可以使用数组来记录每一秒结束时机器人的具体位置,使用临时变量来记录机器人当前的朝向。这和我们使用人脑模拟递推算法的区别不大。


递推思想:


根据已有的东西一点点地推出未知的东西。


使用递推解题三步骤:


数学建模

找出递推式和初始条件

写出代码。

张爽的青蛙(斐波那契)问题:地上有nn个石头从左到右排成一排,张爽同学养的青蛙要从第一个石头跳到最后一个石头上,每次可以选择向右跳一格或者跳两格,问总共有多少种不同的走法?


递推式:f[n] = f[n-1] + f[n-2];


初始条件:f[1] = f[2] = 1。因为从1走到1只有一种方案(呆在原地不动),从1走到2也只有一种方案(走一格);


完整代码:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353; // 答案对998244353取模。
int k, f[1000010];
int main() {
    cin >> k;
    f[1] = f[2] = 1; // 初始条件
    for( int i = 3; i <= k; ++i )
        f[i] = (f[i-1] + f[i-2]) % MOD; // 递推式,记得取模
    cout << f[k] << endl;
    return 0;
}

卡特兰数问题:由nn对括号组成的括号序列,有多少种是合法的括号序列?


递推式:f[n] = f[0] * f[k-1] + ... + f[k-1] * f[0];


初始条件:f[0] = 1,因为0对括号只能组成一种括号序列(空序列);


完整代码:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, f[100010];
int main() {
    cin >> n;
    f[0] = 1; // 初始条件
    for( int i = 1; i <= n; ++i ) { // 求f[i]的值
        for( int k = 0; k < i; ++k ) {
            f[i] += int((long long)f[k] * f[i-k-1] % MOD); // 递推式
            // 注意,两个int相乘的结果可能爆int,因此乘法的过程要转换成long long以避免整数溢出
            f[i] %= MOD; // 记得取模
        }
    }
    cout << f[n] << endl;
    return 0;
}

时间复杂度:O(n^2)。

递推思想:


根据已有的东西一点点地推出未知的东西。


使用递推解题三步骤:


数学建模

找出递推式和初始条件

写出代码。

错位排列问题:有nn个信封和nn个信件,第ii个信件属于第ii个信封,我们想知道,有多少种不同的方法,使得没有任何一个信件被装入正确的信封中?


递推式:f[n] = (n-1)(f[n-1] + f[n-2]);


初始条件:f[1] = 0,因为只有1个信件和信封的时候,没有办法错位排列;f[2] = 1,只有2个信件和信封的时候,只有一种方法(交叉放)。


完整代码:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int f[1000010], n;
int main() {
    cin >> n;
    f[1] = 0; // 初始条件
    f[2] = 1;
    for( int i = 3; i <= n; ++i ) {
        f[i] = (long long)(i-1) * (f[i-1] + f[i-2]) % MOD;
        // 注意取模,并且小心乘法会爆int
    }
    cout << f[n] << endl;
    return 0;
}


杨辉三角(二维递推)问题:从nn个不同的物品中选取mm个,有多少种不同的选择方法?这是一个经典的组合数问题,而本题需要你解决一个更难的问题:给出k,你需要输出一个(k+1)*(k+1)(k+1)∗(k+1)的矩阵,其中第ii行第jj列表示,从ii个不同的物品中选jj个,有多少种不同的方法(行和列的标号从0开始)。


递推式:f[i][j] = f[i-1][j-1] + f[i-1][j];


初始条件:f[i][0] = f[i][i] = 1; // 递推边界条件;


完整代码:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int f[2010][2010] = {0}, k; // 初始化f数组为全0
int main() {
    cin >> k;
    for( int i = 0; i <= k; ++i ) {
        f[i][0] = f[i][i] = 1; // 递推边界条件
        for( int j = 1; j < i; ++j ) {
            f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD; // 递推式,记得取模
        }
        for( int j = 0; j <= k; ++j ) {
            cout << f[i][j] << ' '; // 输出这一整行
        }
        cout << endl;
    }
    return 0;
}

时间复杂度:O(n^2)。

这就是递归


递归简介


递归,简单地来说,就是一个函数自己调用自己。


比如下面的代码,就是一个很简单的递归代码。

#include <bits/stdc++.h>
using namespace std;
void f() {
    f(); // f函数调用自己
}
int main() {
    f();
    return 0;
}

递归是一个函数自己调用自己。


递归的本质是数学归纳法。


我们总是需要从数学归纳法的角度去思考递归,永远不要尝试展开递归过程。


斐波那契数列问题:输入正整数n,使用递归法求出斐波那契数列的第n项,答案对998244353取模。


数学公式:


f(1) = f(2) = 1 // 初始值

f(n) = f(n-1) + f(n-2) // 递归公式

完整代码:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int f( int n ) {
    if( n == 1 || n == 2 ) 
        return 1; // 边界条件
    else 
        return (f(n-1) + f(n-2)) % MOD; // 不要忘记取模
}
int main() {
    int n;
    cin >> n;
    cout << f(n) << endl;
    return 0;
}


求阶乘问题:输入非负整数n,使用递归法求出n的阶乘,答案对998244353取模。


数学公式:


f(0) = 1 // 初始值

f(n) = f(n-1) * n // 递归公式

完整代码:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int f( int n ) {
    if( n == 0 ) 
        return 1;    // 0的阶乘等于1
    else return 
        (long long)f(n-1) * n % MOD; // 注意取模,小心爆int
}
int main() {
    int n;
    cin >> n;
    cout << f(n) << endl;
    return 0;
}

理解递归的三板斧:


确认并牢记这个递归函数的功能,始终不能改。

仔细检查,写对边界条件。

递归调用自己时,放心大胆地用,假设这个函数就是对的。

写递归算法时,要牢记该函数只干一件事情,要写出所有边界条件,要放心大胆地递归调用自己。


递归算法的复杂度往往难以精确把握,只需要根据边界条件的执行次数和递归调用次数估算即可。

相关文章
|
8天前
|
运维 监控 算法
解读 C++ 助力的局域网监控电脑网络连接算法
本文探讨了使用C++语言实现局域网监控电脑中网络连接监控的算法。通过将局域网的拓扑结构建模为图(Graph)数据结构,每台电脑作为顶点,网络连接作为边,可高效管理与监控动态变化的网络连接。文章展示了基于深度优先搜索(DFS)的连通性检测算法,用于判断两节点间是否存在路径,助力故障排查与流量优化。C++的高效性能结合图算法,为保障网络秩序与信息安全提供了坚实基础,未来可进一步优化以应对无线网络等新挑战。
|
18天前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
44 15
|
18天前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
21天前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
45 9
 算法系列之数据结构-二叉树
|
19天前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
38 3
 算法系列之数据结构-Huffman树
|
21天前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
62 22
|
1月前
|
存储 算法 Java
算法系列之递归反转单链表
递归反转链表的基本思路是将当前节点的next指针指向前一个节点,然后递归地对下一个节点进行同样的操作。递归的核心思想是将问题分解为更小的子问题,直到达到基本情况(通常是链表末尾)。
39 5
算法系列之递归反转单链表
|
1月前
|
存储 监控 算法
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
58 15
|
1月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
97 29
|
1月前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
61 12