首页 > 编程语言 >算法02 递归算法及其相关问题【C++实现】

算法02 递归算法及其相关问题【C++实现】

时间:2024-06-16 09:31:22浏览次数:28  
标签:02 10 递归 int C++ 偶数 算法 移动 问题

递归

在编程中,我们把函数直接或者间接调用自身的过程叫做递归。

递归处理问题的过程是:通常把一个大型的复杂问题,转变成一个与原问题类似的,规模更小的问题来进行求解。

递归的三大要素

  1. 函数的参数。在用递归解决问题时,要合理地去设计函数的参数,达到当前问题与子问题之间的变化,可以通过参数进行准确地描述。
  2. 递推关系。要能够找到当前问题与子问题之间的联系,能够用子问题去描述当前问题的解。
  3. 递归出口(边界条件)。要找到问题的边界,避免出现无限递归的情况。每次我们在设计递归函数时,第一步就是先判断当前是否已经到达递归出口,若未到达则再继续递归。

偶数的递归定义

现在我们采用递归的方式来定义偶数:

  1. 0是一个偶数。
  2. 一个偶数与2的和是一个偶数。

这里我们在定义偶数时,就使用了偶数的这个概念。

证明10是偶数

现在我们需要使用刚才的定义来证明10是否为偶数。

因为10=8+2,根据第二条定义可以知道,一个偶数与2的和是一个偶数,现在我们只需要证明8是否是偶数即可得到结论。

我们现在用f(10)表示证明10是否为偶数的函数。

则整个的证明过程如下:

f(10) -> f(8) -> f(6) -> f(4) -> f(2) -> f(0),最终我们的问题变成证明0是否为偶数,而定义中已经给出0是偶数,所以我们可以得到2是偶数...依次类推。

f(0) -> f(2) -> f(4) -> f(6) -> f(8) -> f(10) 。

得出10是偶数。

参考代码

#include<bits/stdc++.h>
using namespace std;
bool f(int n){
    if(n==0)//如果n==0,则n是偶数
        return true;
    return f(n-2); //否则证明n-2是否为偶数
}
int main(){
    int n;
    cin>>n;
    cout<<f(n);
    return 0;
}

输入奇数会怎么样?

输入奇数就会无限递归下去,因为我们并没有为n是奇数的情况设计递归出口。如果n=7,就会去求n=5、3、1、-1、-3...一直递归下去。

我们可以在函数中添加,针对奇数情况的递归出口。(当n==1时,返回false)

训练:递归求和

请使用递归的方法,计算1+2+3+...+n的和。

【输入描述】1行:输入一个整数n。

【输出描述】1行:输出一个整数,表示求和的结果。

【样例输入】5

【样例输出】15

参考代码

#include<bits/stdc++.h>
using namespace std;
int sum(int n){
    if(n==1)
        return 1;
    return sum(n-1)+n;  
}
int main(){
    int n;
    cin>>n;
    cout<<sum(n);
    return 0;
}

训练:汉诺塔问题

汉诺塔(河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

问题建模

我们可以使用4个参数去描述汉诺塔问题。

void Hanoi(int n,char a,char b,char c);

n表示移动的是第n号盘子;

a,b,c分别表示汉诺塔问题中的三个柱子。

我们称a,b,c分别为:起始柱,辅助柱,目标柱。

递归关系

  • 根据游戏规则:想要移动n号盘,则需要先将n-1号盘从a柱移动到b柱。

此时我们的问题变成:Hanoi(n-1, a, c, b);

即:将n-1号盘从a柱出发,借助c柱,移动到b柱。

在这次移动的过程中a,c,b分别为:起始柱,辅助柱,目标柱。

  • 将n-1号盘子移到b柱之后,我们就可以将n号盘子,直接从a移动到c,即:a->c。

到这一步,我们完成了第n号盘子的移动。

接下来我们还需要将n-1号盘子(在b柱),移动到c柱上。

即:Hanoi(n-1, b, a, c);

在这次移动的过程中b,a,c分别为:起始柱,辅助柱,目标柱。

边界条件

当问题变成只有一个盘子时,我们就无须借助辅助柱,

直接从a移动到c柱即可。

参考代码

void Hanoi(int n,char a,char b,char c){
    if(n==1){
        cout<<n<<":"<<a<<"->"<<c<<endl;
        return ;
    }
    else{
        Hanoi(n-1,a,c,b);
        cout<<n<<":"<<a<<"->"<<c<<endl;
        Hanoi(n-1,b,a,c);
    }
}
int main(){
    Hanoi(3,'a','b','c');
    return 0;
}

从C++入门到算法,再到数据结构,查看全部文章请点击icon-default.png?t=N7T8http://www.bigbigli.com/

标签:02,10,递归,int,C++,偶数,算法,移动,问题
From: https://blog.csdn.net/qq_39434533/article/details/139678955

相关文章

  • C++全栈聊天项目(22) 气泡聊天对话框
    气泡聊天框设计我们期待实现如下绿色的气泡对话框对于我们自己发出的信息,我们可以实现这样一个网格布局管理NameLabel用来显示用户的名字,Bubble用来显示聊天信息,Spacer是个弹簧,保证将NameLabel,IconLabel,Bubble等挤压到右侧。如果是别人发出的消息,我们设置这样一个网......
  • 自然资源-《乡村振兴用地政策指南(2023年)》解读
    自然资源-《乡村振兴用地政策指南(2023年)》解读近期,自然资源部办公厅印发《乡村振兴用地政策指南(2023年)》(以下简称《指南》)。作为第一部针对乡村振兴用地政策的“工具包”,《指南》有哪些亮点,将为地方做好乡村振兴用地保障带来哪些便利?自然资源部国土空间用途管制司相关负责......
  • 【C++学习笔记 3】指针
    指针的本质指针实际上就是一个整数,存储着一个内存地址。不必执着于用“类型”的概念区分,那只是为了方便设计出来的,所有的指针,本质上都是一个整数,存储着一个内存的地址。#include<iostream>#defineLOG(x)std::cout<<x<<std::endlintmain(){ intvar=8; ......
  • 2024华为OD机试真题-堆内存申请-(C++/Python)-C卷D卷-100分
    2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++)题目描述有一个总空间为100字节的堆,现要从中新申请一块内存,内存分配原则为:优先紧接着前一块已使用内存,分配空间足够且最接近申请大小的空闲内存。输入描述第1行是1个整数,表示期望申请的内存字节数第2到第N行是用空格......
  • 2024华为OD机试真题-围棋的气-(C++/Python)-C卷D卷-100分
     2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++) 题目描述围棋棋盘由纵横各19条线垂直相交组成,棋盘上一共19x19=361个交点,对弈双方一方执白棋,一方执黑棋,落子时只能将棋子置于交点上。“气”是围棋中很重要的一个概念,某个棋子有几口气,是指其上下左右方向四个相......
  • 程序员必须掌握的算法:编程之路的基石
    作为一名程序员,我深知算法在编程中的重要性。算法不仅是编程的基础,更是我们解决问题、优化程序的关键。下面,我将介绍一些程序员在编程中需要掌握的基本算法,并强调算法在编程中的重要性,同时提供一些实用的算法学习资源。基本算法介绍与实现1.快速排序(QuickSort)快速排序......
  • 第八天 第四章 字符串 part02 151.翻转字符串里的单词 卡码网:55.右旋转字符串
    151.翻转字符串里的单词方法很巧妙,进行了两次反转。其中细节太多了。1.如何处理首个单词前面的空格,以及后面单词之间的空格处理(最重要的部分)。2.单词反转时的下标。classSolution{public:voidreverse(string&s,intleft,intright){......
  • 基因组选择对培育气候适应性作物的意义(2023综述)
    本文来自《基因组选择对培育气候适应性作物的意义》一些研究和观点。重点摘要基因组选择是改善植物复杂性状(如生物和非生物胁迫耐受性)和实现可持续生产的有力工具。基因组选择能够显著提高植物的气候适应性和产量,并且预测准确性高。不同统计模型对预测精度的影响:比较了单因素线......
  • 程序设计与算法(三)C++:第五章poj代码
    课程:北京大学程序设计与算法(三)   MOOCOJ:OpenJudge019:全面的MyString这个题也是有很多的成员函数,我们来从主函数分析一下:MyStrings1("abcd-"),s2,s3("efgh-"),s4(s1);//无参构造,有参构造,复制可以不写 MyStringSArray[4]={"big","me","about","take"......
  • 算法金 | 选择最佳机器学习模型的 10 步指南
    大侠幸会,在下全网同名[算法金]0基础转AI上岸,多个算法赛Top[日更万日,让更多人享受智能乐趣]机器学习和数据科学领域的工作充满挑战和乐趣,在我踏上人工智能探索之路的初期,我对能够参与项目感到无比兴奋。我满怀热情,我急切地想投身于这些项目中。但是,我尝试开展项目,却发现......