剑指Offer（六）--斐波那契数列
剑指Offer（六）--斐波那契数列
秦怀杂货店
发布于 2022-02-15 13:36:08
发布于 2022-02-15 13:36:08
代码可运行
运行总次数：0
代码可运行
- 直接暴力
- 重复利用结果
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39
百度百科：
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
思路以及解答
斐波那契数列大家都知道：
直接暴力
思路很直接，利用函数进行递归即可。
public class Solution {
public int Fibonacci(int n) {
if(n==0){
return 0;
}else if(n==1){
return 1;
}else{
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
}
重复利用结果
直接递归会造成很多重复的计算，要是我们把计算结果先存起来，使用的时候再调用，那就可以优化，可以算是空间换时间的做法。大学老师似乎说过，几乎所有的递归都可以写成循环形式，个人感觉这也是其中一个例子。
public class Solution {
public int Fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
for (int i = 2; i <= n; i++) {
nums[i] = nums[i - 1] + nums[i - 2];
}
return nums[n];
}
}- END -
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-09-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
