斐波那契数列求第N项递归改进

2024-06-20 09:18

本文主要是介绍斐波那契数列求第N项递归改进,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

递归思路:

int fib(int n) {if ( 2 > n) {return n;}return fib(n-1) + fib(n-2);
}

展开递归计算过程,如下为求第fib(5)的递归过程。
在这里插入图片描述
如上发现好多重复计算过程,时间与空间的消耗也是必然的。
颠倒计算方向,由自顶而下递归,为自底而上迭代(动态规划)
在这里插入图片描述
算法描述为:

int fib(int n) {int f = 0, g = 1;while( --n > 0 ) {g = g + f;f = g - f;}return g;
}

这篇关于斐波那契数列求第N项递归改进的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR

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

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

一种改进的red5集群方案的应用、基于Red5服务器集群负载均衡调度算法研究

转自: 一种改进的red5集群方案的应用: http://wenku.baidu.com/link?url=jYQ1wNwHVBqJ-5XCYq0PRligp6Y5q6BYXyISUsF56My8DP8dc9CZ4pZvpPz1abxJn8fojMrL0IyfmMHStpvkotqC1RWlRMGnzVL1X4IPOa_  基于Red5服务器集群负载均衡调度算法研究 http://ww

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

oracle11.2g递归查询(树形结构查询)

转自: 一 二 简单语法介绍 一、树型表结构:节点ID 上级ID 节点名称二、公式: select 节点ID,节点名称,levelfrom 表connect by prior 节点ID=上级节点IDstart with 上级节点ID=节点值 oracle官网解说 开发人员:SQL 递归: 在 Oracle Database 11g 第 2 版中查询层次结构数据的快速

YOLOv8改进实战 | 注意力篇 | 引入CVPR2024 PKINet 上下文锚点注意力CAAttention

YOLOv8专栏导航:点击此处跳转 前言 YOLOv8 是由 YOLOv5 的发布者 Ultralytics 发布的最新版本的 YOLO。它可用于对象检测、分割、分类任务以及大型数据集的学习,并且可以在包括 CPU 和 GPU 在内的各种硬件上执行。 YOLOv8 是一种尖端的、最先进的 (SOTA) 模型,它建立在以前成功的 YOLO 版本的基础上,并引入了新的功能和改进,以

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本 可以看看之前的版本,两个版本面试用哪个都保过 解法都在代码里,不懂就留言或者私信 class Solution {/**对于之前的解法,我现在提供一共更优的解,但是这种可能会比较难懂一些(思想方面)代码其实是很简洁的,总体思想如下:不需要排序直接把所有数放入map,map的key是当前数字,value是当前数开始的

UVa 10820 Send a Table (Farey数列欧拉函数求和)

这里先说一下欧拉函数的求法 先说一下筛选素数的方法 void Get_Prime(){ /*筛选素数法*/for(int i = 0; i < N; i++) vis[i] = 1;vis[0] = vis[1] = 0;for(int i = 2; i * i < N; i++)if(vis[i]){for(int j = i * i; j < N; j += i)vis[j] =

【UVA】10651-Pebble Solitaire(直接递归或者记忆化)

不知道这个题UVA的数据是怎么的,用2个方法交了,第一次直接递归,第二次记忆化剪枝,时间竟然一样!? 直接郁闷了,简单的二进制表示状态和二进制运算。 14145176 10651 Pebble Solitaire Accepted C++ 0.009 2014-09-04 09:18:21 #include<cstdio>#include<algorithm>#inclu

YOLOv8改进 | Conv篇 | YOLOv8引入DWR

1. DWR介绍 1.1  摘要:当前的许多工作直接采用多速率深度扩张卷积从一个输入特征图中同时捕获多尺度上下文信息,从而提高实时语义分割的特征提取效率。 然而,这种设计可能会因为结构和超参数的不合理而导致多尺度上下文信息的访问困难。 为了降低多尺度上下文信息的绘制难度,我们提出了一种高效的多尺度特征提取方法,将原始的单步方法分解为区域残差-语义残差两个步骤。 在该方法中,多速率深度扩张卷积