剑指offer——面试题9计算斐波纳切第n个数

/**
 * 计算斐波纳切数列的第n个值
 * @author chibozhou
 *
 */
public class Fibonacci {
	/**
	 * 分析:斐波纳切数列的第n个数的值是其前两个数之和,
	 * 因此要计算第n个数就需要计算其前两个数,
	 * 以此类推,直到计算出第0个数为止,
	 * 因此可以使用递归。
	 */
	
	/**
	 * 采用递归的方法
	 */
	public static int fibonacci(int n){
		//健壮性判断
		if(n<0){
			System.out.println("n不能小于0!");
			return 0;
		}
		
		//n==0
		else if(n==0)
			return 0;
		
		//n==1
		else if(n==1)
			return 1;
		
		//n>1
		else
			return fibonacci(n-1) + fibonacci(n-2);
		
	}
	
	
	
	/**
	 * 上述递归的代码虽然简单,但所需的内存空间很大,
	 * 而且在递归的过程中,有很多计算是重复的,比如:
	 * fibonacci(6)=fibonacci(5)+fibonacci(4)
	 * 		fibonacci(5)=fibonacci(4)+fibonacci(3)
	 * 		fibonacci(4)=fibonacci(3)+fibonacci(2)
	 * 由此可见:fibonacci(4)、fibonacci(3)均被重复计算,
	 * 因此递归的方法在时间和空间上的开销都很大!
	 * 是否有比递归更好的办法来实现斐波纳切?
	 */
	
	
	
	/**
	 * 递归之所以开销巨大,是因为它是一个自顶向下的计算过程,
	 * 要计算fibonacci(n),就需要先计算fibonacci(n-1)和fibonacci(n-2),
	 * 而在fibonacci(0)被计算出之前,之前所有的函数都处于在内存中等待的状态,都占用着内存空间;
	 * 因此,如果我们采用自底向上的方式,每完成一个fibonacci函数,就记录下该值,并释放其内存空间,
	 * 就能节约内存空间。
	 * 此外,由于fibonacci(n)是由前两个数相加得到的,
	 * 因此只要将每次计算结果和前一个数记录下来,就能计算出之后值,从而避免了重复计算。
	 * @param n 斐波纳切数列长度
	 * @return 第n个元素值
	 */
	public static int fibonacci_recursion(int n){
		//健壮性判断
		if(n<0){
			System.out.println("n不能小于0");
			return 0;
		}
		
		if(n==0 || n==1)
			return n;
		
		//a1用于存储fibonacci(n-2),a2用于存储fibonacci(n-1),a3用于存储fibonacci(n)
		int a1=0,a2=1,a3=1;
		for(int i=0;i<n-1;i++){
			a3 = a1+a2;
			a1 = a2;
			a2 = a3;
		}
		
		return a3;
	}
	

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xcywt

《大话数据结构》 查找 以及一个简单的哈希表例子

第八章 查找 定义:查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 8.2 查找概论 查找表(Search table):...

50512
来自专栏数值分析与有限元编程

一维变带宽存储刚度矩阵

我们知道,集成之后的整体刚度矩阵是一个对称的稀疏带状矩阵,如图1所示。这样的矩阵包含大量的0元素,占用大量的存储空间。为了节约存储空间,可采取一些方法对刚度矩阵...

3606
来自专栏计算机视觉及音视频工程

Python常用写法理解

663
来自专栏数据结构与算法

洛谷P2503 [HAOI2006]均分数据(模拟退火)

1470
来自专栏数据结构与算法

prufer序列笔记

 prufer序列 度娘的定义 Prufer数列是无根树的一种数列。在组合数学中,Prufer数列由有一个对于顶点标过号的树转化来的数列,点数为n的树转化来的...

3439
来自专栏闻道于事

算法笔记(二)数据结构

1050
来自专栏Java开发者杂谈

依赖数组特性的几种非比较排序算法

前言:   前面所讲的排序算法基本都是需要进行两个数依次比较,这种两个数依次比较的算法不依赖于数组重元素的特性并且有下界Ω(nlogn)。换句话说就是使用比较排...

3987
来自专栏hanlp学习笔记

hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

720
来自专栏用户画像

7.4.1简单选择排序

选择排序的基本思想是:每趟(例如第i趟)在后面 n-i+1(i=1,2,...,n-1)个待排序元素中选取关键字最小的元素,

572
来自专栏C语言及其他语言

[每日一题]连接元音字母

前面我们一起编写了如何定义函数反序输出字符串,连接字符串,今天,我们将来一起学习如何定义函数将两个字符串中的元音字母复制到另一个字符串,然后输出。(传参问题是关...

2827

扫码关注云+社区