剑指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 条评论
登录 后参与评论

相关文章

来自专栏向治洪

Java泛型和通配符那点事

泛型(Generic type 或者generics)是对 Java 语言的类型系统的一种扩展,以支持创建可以按类型进行参数化的类。可以把类型参数看作是使用参数...

24750
来自专栏猿人谷

C++ 模板学习

1. 模板的概念。 我们已经学过重载(Overloading),对重载函数而言,C++的检查机制能通过函数参数的不同及所属类的不同。正确的调用重载函数。例如,为...

263100
来自专栏web前端教室

JS判断重复数组是否有重复项

大家好,今天我们来讲一下,如何使用javascript判断一个数组之中,是否有相同重复的元素。 在讲之前,先来讲一下思路: 在现实当中,当我们要判断某几个东西...

51990
来自专栏Phoenix的Android之旅

Java 强/弱/软引用

来排列。在JVM运行内存不足时,这三种之中最先被回收的是 弱引用,依次到最后才是强引用(不会被回收)。 但是对于强引用来说,JVM在内存不足时宁可抛出 OOM,...

11320
来自专栏小狼的世界

Python 3.6学习笔记(一)

可以看到,注释以#开头,python的变量不需要任何前缀,行结束不需要结束符号,非常符合我们自然语言的阅读和书写习惯。当语句以:结尾时,缩紧的语句视为代码块。

11920
来自专栏程序员的知识天地

Python正则表达式的7个使用典范

作为一个概念而言,正则表达式对于Python来说并不是独有的。但是,Python中的正则表达式在实际使用过程中还是有一些细小的差别。

12710
来自专栏林冠宏的技术文章

由 System.arraycopy 引发的巩固:对象引用 与 对象 的区别

首先明确一点,System.arraycopy 操作的是数组,效果是深复制。 是不是觉得怎么和你印象的中不一样? 重点来了,对于对象数组,例如: User[]...

14240
来自专栏专注 Java 基础分享

Java 内部类的意义及应用

众所周知,我们的 C++ 程序语言是多继承制的,而多继承明显的好处就是,相对而言只需要写较少的代码即可完成一个类的定义,因为我们可以通过继承其它类来获取别人的实...

34640
来自专栏marsggbo

c++学习笔记之封装篇(上)

一、类对象 假设我们由Tv这个类,定义如下 注意class结尾要加上分号 class Tv() { int width; int hei...

18560
来自专栏CodeSheep的技术分享

Java编程思想学习录(连载之:内部类)

226110

扫码关注云+社区

领取腾讯云代金券