递归 从最简单开始 逐步深化的理解 +举例说明 (n的阶乘、斐波那契数列、n个台阶不同走法、蓝桥杯第39级台阶) C++

本文主要是介绍递归 从最简单开始 逐步深化的理解 +举例说明 (n的阶乘、斐波那契数列、n个台阶不同走法、蓝桥杯第39级台阶) C++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

先看三个拓展题目:

一、求n的阶乘(1<n<1000)?

例如n=5;  5的阶乘:5*4*3*2*1=120

//递归
#include<iostream>
using namespace std;
int fun(int n){if(n==1)return 1;elsereturn n*fun(n-1);
}
int main(){int n;cin>>n;cout<<fun(n);return 0;
}//————————————————————————————————————————————————————————————————————————————————————/*
//非递归
#include<iostream>
using namespace std;
int main(){int n,sum=1;cin>>n;while(n>0)sum*=n--;cout<<sum;return 0;
}
*/

 二、求斐波那契数列的第n项是多少?

斐波那契数列:1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765........

规律:前两个数相加等于后面的第三个数(a[i] = a[i-1] + a[i-2] ,其中i>=3);

//递归
#include<iostream>
using namespace std;
int fun(int n){if(n==0)return 0;else if(n==1)return 1;else return fun(n-1)+fun(n-2);
}
int main(){int n;cin>>n;cout<<fun(n);return 0;
}//——————————————————————————————————————————————————————————————————————————— /*
//非递归 
#include<iostream>
using namespace std;
int main(){int n;cin>>n;int aa[n+1];aa[1]=aa[2]=1;for(int i=3;i<=n;i++)aa[i]=aa[i-1]+aa[i-2]; cout<<aa[n];return 0;
}
*/

三、楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
设n阶台阶的走法数为f(n),按照倒推法(从楼梯最上面,倒推过来,从n-1台阶到第n台阶的走法,和从n-2到第n台阶的走法),显然有当 n>2 时,f(n)=f(n-1)+f(n-2),(特别关键,一定要理解透彻,最好能自己动笔推演一遍才能真正的搞清楚)

输入一个整数n(3<=n<=1000);

输出一个整数表示共有多少种不同的走法。

#include<iostream>
using namespace std;
int fun(int n){if(1==n)return 1;else if(2==n)return 2;elsereturn fun(n-1)+fun(n-2);
} 
int main(){int n;cin>>n;cout<<fun(n)<<endl;return 0;
}//提示:非递归可用排列组合的方法实现,过程略显复杂,代码省略

(39阶台阶,102334155)

-------------------------------------------------上主菜 -------------------------------------------------------------

四、第39级台阶
小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!
站在台阶前,他突然又想着一个问题:

如果我每一步 只能迈上1个或2个台阶。先迈左脚,然后左右交替,
最后一步是迈右脚,也就是说共要走偶数步(不同点)

那么,上完39级台阶, 有多少种不同的,上法呢?
请你利用计算机的优势,帮助小明寻找答案。

要求提交的是个整数。
注意:不要提交解答过程,或其它的辅助说明文字。

(答案:51167078)

#include<iostream>
using namespace std;
int ans=0; 
void fun(int step,int s){     //step表示还剩余多少步(台阶),s表示走了多少步,if(step<0)return;else if(0==step &&s%2==0)ans++;else{fun(step-1,s+1);fun(step-2,s+1);}	
} 
int main(){fun(39,0);cout<<ans<<endl;return 0;
}//提示:非递归可用排列组合的方法实现,过程略显复杂,代码省略

非递归:运用排列组合的方法

注:102334155 / 2 = 51167077.5 ==> 51167078

总结:

  • 由一、二可以看出递归不一定就比非递归简单,其实一、二递归算法的效率远远低于非递归,数据稍微大一点就能明显感觉出来,递归要好几秒甚至十多秒才能出答案,非递归却依然还是一两秒就能出答案;
  • 由三、四可以知道:递归对于一些比较复杂问题还是很好用的(要不然怎么说高手都用递归呢),当然,好用基本都只是在于代码量简单了,就是有些废脑子,容易烧坏脑袋;
  • 由这四个递归程序(逐渐复杂)可以很好的帮助理解递归的原理,对递归很困惑的小伙伴很有帮助,值得研究;
  • ………………+++++…………
  • 其他总结,还请有想法的读者能共享出自己的总结经验,大家共同进步。

这篇关于递归 从最简单开始 逐步深化的理解 +举例说明 (n的阶乘、斐波那契数列、n个台阶不同走法、蓝桥杯第39级台阶) C++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/233357

相关文章

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++ Primer 标准库vector示例详解

《C++Primer标准库vector示例详解》该文章主要介绍了C++标准库中的vector类型,包括其定义、初始化、成员函数以及常见操作,文章详细解释了如何使用vector来存储和操作对象集合,... 目录3.3标准库Vector定义和初始化vector对象通列表初始化vector对象创建指定数量的元素值

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::