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

相关文章

来自专栏小狼的世界

Python 3.6学习笔记(一)

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

962
来自专栏CodeSheep的技术分享

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

20611
来自专栏老马说编程

(29) 剖析String / 计算机程序的思维逻辑

上节介绍了单个字符的封装类Character,本节介绍字符串类。字符串操作大概是计算机程序中最常见的操作了,Java中表示字符串的类是String,本节就来详细...

1935
来自专栏LuckQI

学习Java基础知识,打通面试关~十二接口与抽象类

1034
来自专栏CoXie带你学编程

详解Python 2.x 与 Python 3.x 的区别

如果你是刚接触 Python 的初学者,那你可能是直接学习 Python 3.x 版本。对于 Python 2.x 的版本是不会有所接触。官方也宣布在 2020...

1592
来自专栏猿人谷

C++ 模板学习

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

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

Java 内部类的意义及应用

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

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

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

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

1184
来自专栏小蠢驴iOS专题

python入门_常见正则表达式匹配

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

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

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

1031

扫码关注云+社区