大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 的数列
数据范围:
要求:空间复杂度 ,时间复杂度 ,本题也有时间复杂度 的解法
一个正整数n
输出一个正整数。
4
3
根据斐波那契数列的定义可知,fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3,所以答案为3。
1
1
2
1
package Recursion;
/**
* 题目描述
* 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。
* n<=39
* 思路:
* 在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)
* 用文字来说,就是斐波那契数列列由 0 和 1 开始,之后的斐波那契数列系数就由之前的两数相加。
* 特别指出:0不是第一项,而是第零项。
*/
public class Solution03 {
public static void main(String[] args) {
System.out.println(Fibonacci_2(4));
}
/**
* 用递归直接求解
*
* @param n 斐波那契数列第n项
* @return 斐波那契数列第n项的值
*/
public static int Fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n <= 1) {
return n;
} else {
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
/**
* 迭代方法,用两个变量记录fn-1和fn-2:
*
* @param n 斐波那契数列第n项
* @return 斐波那契数列第n项的值
*/
public static int Fibonacci_2(int n) {
int zero = 0, one = 1, fN = 0;
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
//由zero和one保存中间结果
for (int i = 2; i <= n; i++) {
fN = one + zero;
zero = one;
one = fN;
}
return fN;
}
}
}
public class Solution { public int Fibonacci(int n) { if (n <= 2) return 1; else return Fibonacci(n - 1) + Fibonacci(n - 2); } }
class Solution: def Fibonacci(self , n: int) -> int: # write code here if n == 0: return 0 if n == 1: return 1 return self.Fibonacci(n-1)+self.Fibonacci[n-2]
class Solution: def __init__(self): self.memo=[0] def Fibonacci(self , n: int) -> int: # write code here if n == 0: return 0 if n == 1: self.memo.append(1) return 1 res =self.Fibonacci(n-1)+self.memo[n-2] self.memo.append(res) return res
public class Solution { public int Fibonacci(int n) { int a = 1; int b = 1; while (n-- > 2) { b += a; a = b - a; } return b; } }
const int MAXN=100; class Solution { public: long long f[MAXN]; bool visit[MAXN]; long long Fibonacci(int n){ f[0]=0; f[1]=1; visit[0]=visit[1]=true; if(visit[n]){ return f[n]; } f[n]=Fibonacci(n-2)+Fibonacci(n-1); visit[n]=true; return f[n]; } };
public class Solution { public int Fibonacci(int n) { if(n == 0) return 0; int a = 1; int b = 1; for(int i = 2; i < n; i++){ a = a + b; b = a - b; } return a; } }
# -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): if n==0: return 0; if n==1: return 1; if n>=2: f_list = [0,1] for i in range(2,n+1,1): ai = f_list[i-1] + f_list[i-2] f_list.append(ai) return f_list[-1]
func Fibonacci( n int ) int { // write code here if(n < 2){ return n; } tail := 0 head := 1 for i := 2; i <= n; i++ { tail, head = head, tail + head } return head }