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;
}

理解递归的三板斧:


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

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

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

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


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

目录
打赏
0
0
0
0
88
分享
相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
27 15
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
79 29
|
16天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
52 19
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
61 15
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等