文档章节

斐波那契数列递归实现和优化

cuibin1991
 cuibin1991
发布于 2016/08/16 09:57
字数 180
阅读 2
收藏 0

递归的求解过程存在严重的效率问题,如果想得到f(10),需要先求解f(8)和f(9)。而求解f(9)又要先求解f(8)和f(7),如书中的树形结构:

输入图片说明

树中有很多重复节点,重复节点会随着n的增大而急剧增加,计算量也会随着n增大而急剧增大。

优化:从上往下计算,首先根据f(0)和f(1)算出f(2),再关键f(1)和f(2)算出f(3).....依次算法第n项。这种思路的时间复杂度是O(n)。

递归和优化的代码实现如下:http://www.oschina.net/code/snippet_1051716_58660

© 著作权归作者所有

共有 人打赏支持
cuibin1991
粉丝 2
博文 15
码字总数 2682
作品 0
房山
程序员
斐波那契查找(黄金分割法查找)

什么是斐波那契查找 斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、····,在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n...

serenity
2014/06/20
0
0
科普向 - 趣味的斐波那契数列

1.从一道面试题开始 每个程序员从第一次接触计算机编程语言到真正作为工程师进行项目开发,都一定都见过下面这道题目: 很多个台阶,可以一次走一个台阶,也可以一次走两个台阶,那么走台阶时...

ssssyoki
08/11
0
0
python实现斐波那契数列

斐波那契数列的发明者是意大利数学家昂纳多.斐波那契(Leonardo Fibonacci)。斐波那契数列又被称为黄金分割数列,或兔子数列。它指的是这样一个数列:0 1 1 2 3 5 8 13 21 34 ....在数学上,...

大陌
2017/07/09
0
0
重点汇总-python-gitbook-重要点学习-4-数据结构/编程题

数据结构 - 红黑树 红黑树与AVL的比较: AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多; 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低;...

时间之友
2017/12/21
0
0
斐波那契数

一、题目: 递归和非递归分别实现求第n个斐波那契数。 二、解题思路: 先了解下斐波拉契数列 (1 1 2 3 5 8 13 21 34 55···),第n个斐波那契数等于(n-1)个斐波那契数加上(n-2)个斐波那...

qq_38646470
2017/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

关于Jackson默认丢失Bigdecimal精度问题分析

问题描述 最近在使用一个内部的RPC框架时,发现如果使用Object类型,实际类型为BigDecimal的时候,作为传输对象的时候,会出现丢失精度的问题;比如在序列化前为金额1.00,反序列化之后为1.0...

ksfzhaohui
17分钟前
0
0
vue less安装

$ npm install less less-loader --save 安装成功后修改文件:build>webpack.base.conf.js 在model.rules添加对象: { test: /\.less$/, loader: "style-loader!css-loader!less-loade......

shawnDream
22分钟前
0
0
kolla-ansible部署容器ceph

kolla是从openstack孵化出的一个项目,kolla项目可以制作镜像包括openstack、ceph等容器镜像, ansible是自动化部署工具,执行playbook中的任务。 kolla-ansible是容器部署工具,部署opensta...

zrz11
27分钟前
0
0
【三 异步HTTP编程】 1. 处理异步results

异步results 事实上整个Play框架都是异步的。Play非阻塞地处理每个request请求。 默认的配置适配的正是异步的controller。因此开发者应该尽力避免在在controller中阻塞,如在controller方法中...

Landas
29分钟前
0
0
Android Studio 3.1.4 buildApk遇到问题 Connection reset

打开设置,找到Android Studio选项卡,把下图选项打上勾就ok

lanyu96
30分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部