Logo
Section 1 / 9

斐波那契数列

找出斐波那契数列中的第 n 个数。

导入

斐波那契数列

找出斐波那契数列中的第 n 个数。

问题描述

实现一个函数，用于找到斐波那契数列中的第 n 个斐波那契数。

斐波那契数列是一组称为斐波那契序列的数字，其中每个数字是前两个数字之和，从 0 和 1 开始。

斐波那契数的定义如下：

  • F0=0F_0 = 0
  • F1=1F_1 = 1
  • Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}，当 n≥2n \geq 2

根据上述定义，从第 0 项开始的前 10 个斐波那契数为：0,1,1,2,3,5,8,13,21,340, 1, 1, 2, 3, 5, 8, 13, 21, 34。

示例输入

18

期望输出

121

自行尝试

C++

1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int GetFibonacci(int n) {
7	//TODO: 写你的代码
8	return -1;
9}

Java

1// 导入所需函数
2import java.util.*;
3
4class Fib {
5	static int getFibonacci(int n) {
6		// TODO: 写你的代码
7		return -1;
8	}
9}

Python

1def get_fibonacci(n):
2  #TODO: 写你的代码
3  return -1

JS

1let getFibonacci = function(n) {  
2  // TODO: 写你的代码
3  return -1;
4};

Ruby

1def get_fibonacci(n)
2  # TODO: 写你的代码
3  return -1
4end

Go

1package main
2import (
3	"fmt"
4	"strconv"
5	"encoding/json"
6)
7
8func GetFibonacci(n int) int {
9	// TODO: 写你的代码
10	return -1
11}

解法 1：递归

获取第 n 个斐波那契数的一种简单方法是实现递推关系。该解法实现简单但效率极低。 让我们看看如何使用递归方法计算第 4 个斐波那契数：

C++

1#include <iostream>
2#include <vector>
3using namespace std;
4
5int GetFibonacci(int n) {
6
7	// 基础情况：n = 0 和 n = 1
8	if (n == 0 || n == 1) {
9		return n;
10	}
11	// 实现斐波那契递推关系
12	return GetFibonacci(n - 1) + GetFibonacci(n - 2);
13}
14
15int main() {
16	vector<int> inputs = {1, 5, 7, 10}; 
17	
18	for (int i = 0; i < inputs.size(); i++){ 
19		cout << i+1 << ".  GetFibonacci(" << inputs[i] << ") = " << GetFibonacci(inputs[i]) << endl;
20    	cout << "------------------------------------------------------------------------------------------------------\n" << endl;
21	}
22}

Java

1// 导入所需函数
2import java.util.*;
3
4class Fib {
5	static int getFibonacci(int n) {
6		// 基础情况：n = 0 和 n = 1
7		if (n == 0 || n == 1) {
8			return n;
9		}
10
11		// 实现斐波那契递推关系
12		return getFibonacci(n - 1) + getFibonacci(n - 2);
13	}
14
15	public static void main(String[] args) {
16		int[] inputs = {1, 5, 7, 10};
17		for (int i = 0; i < inputs.length; i++) {
18			System.out.println(i+1 + ".  getFibonacci(" + inputs[i] + ") = " + getFibonacci(inputs[i]));
19			System.out.println(
20					"------------------------------------------------------------------------------------------------------\n");
21		}
22	}
23}

Python

1def get_fibonacci(n):
2	# 基础情况：n = 0 和 n = 1
3  if n == 0 or n == 1:
4    return n
5	
6	# 实现斐波那契递推关系
7  return get_fibonacci(n - 1) + get_fibonacci(n - 2)
8
9def main():
10	inputs = [1, 5, 7, 10]
11	for i in range(len(inputs)):
12		print(str(i + 1) + ".  get_fibonacci(" + str(inputs[i]) + ") = " + str(get_fibonacci(inputs[i])))
13		print("------------------------------------------------------------------------------------------------------\n")
14
15if __name__ == '__main__':
16    main()

JS

1let getFibonacci = function(n) {
2
3  // 基础情况：n = 0 和 n = 1
4  if (n === 0 || n === 1) {
5      return n;
6  }
7
8  // 实现斐波那契递推关系
9  return getFibonacci(n - 1) + getFibonacci(n - 2);
10};
11  
12let inputs = [1, 5, 7, 10]
13
14for (let i = 0; i < inputs.length; i++){
15  console.log(i+1 + ".  getFibonacci(" + (inputs[i]) + ") = " + getFibonacci(inputs[i]));
16  console.log("------------------------------------------------------------------------------------------------------\n");
17}

Ruby

1def get_fibonacci(n)
2  # 基础情况：n = 0 和 n = 1
3  return n if n == 0 || n == 1
4  
5  # 实现斐波那契递推关系
6  return get_fibonacci(n - 1) + get_fibonacci(n - 2)
7end
8
9inputs = [1, 5, 7, 10]
10
11inputs.length.times do |i|
12  puts (i + 1).to_s + ".  get_fibonacci(" + inputs[i].to_s + ") = " + get_fibonacci(inputs[i]).to_s
13  puts "------------------------------------------------------------------------------------------------------\n"
14
15end

Go

1package main
2import (
3	"fmt"
4)
5
6func GetFibonacci(n int) int {
7
8	// 基础情况：n = 0 和 n = 1
9	if n == 0 || n == 1 {
10		return n
11	}
12
13	// 实现斐波那契递推关系
14	return GetFibonacci(n - 1) + GetFibonacci(n - 2)
15}
16
17func main() {
18
19   inputs := []int{1, 5, 7, 10} 
20	
21	for i, input := range inputs {
22		fmt.Printf("%d.  GetFibonacci(%d) = %d\n", i + 1, input, GetFibonacci(input))
23    	fmt.Print( "------------------------------------------------------------------------------------------------------\n")
24	}
25}

时间复杂度

我们可以很容易地看出，在时间复杂度方面，以下不等式成立： F(n)=F(n−2)+F(n−2)≤F(n)=F(n−1)+F(n−2)≤F(n)=F(n−1)+F(n−1)F(n) = F(n-2) + F(n-2) \leq F(n) = F(n-1) + F(n-2) \leq F(n) = F(n-1) + F(n-1)

使用递归方法计算 F(n)=F(n−2)+F(n−2)F(n) = F(n-2) + F(n-2) 的时间复杂度为 O(2n2)O(2^{\frac{n}{2}})，而计算 F(n)=F(n−1)+F(n−1)F(n) = F(n-1) + F(n-1) 的时间复杂度为 O(2n)O(2^n)。

因此，该解法的时间复杂度下界为 O(2n2)O(2^{\frac{n}{2}})，上界为 O(2n)O(2^n)。

确切的界限被证明约为 O(1.618n)O(1.618^n)，尽管其证明超出了本课程范围。

空间复杂度

此递归解法的空间复杂度为 O(n)O(n)，因为每次递归调用都会在栈上占用内存，最长的调用栈对应于从 nn 开始，经过 n−1n-1、n−2n-2、n−3n-3，一直到 33、22、11 的调用。

解法 2：迭代

递归解法存在大量重复计算：

在计算 F4F_4 时，F2F_2 被计算了两次。这个问题具有重叠子问题和最优子结构的特性，因此可以使用动态规划。

要计算 FnF_n，我们只需跟踪 Fn−1F_{n-1} 和 Fn−2F_{n-2}，即可得到线性解法。

C++

1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int GetFibonacci(int n) {
7
8	if (n == 0 || n == 1) {
9		return n;
10	}
11
12	// 初始化变量
13	int n_1 = 1; 
14	int n_2 = 0; 
15	int result = 0;
16
17	// 从 2 开始循环，因为我们已经知道 n_1 和 n_2
18	for (int i = 2; i <= n; ++i) {
19		// 计算新的结果
20		result = n_1 + n_2;
21
22		// 更新 n_2 和 n_1
23		n_2 = n_1;
24		n_1 = result;
25	}
26
27	return result;
28}
29
30int main() {
31	vector<int> inputs = {1, 5, 7, 10}; 
32	
33	for (int i = 0; i < inputs.size(); i++){ 
34		cout << i+1 <<".  GetFibonacci(" << inputs[i] << ") = " << GetFibonacci(inputs[i]) << endl;
35    	cout << "------------------------------------------------------------------------------------------------------\n" << endl;
36	}
37}

Java

1// 导入所需函数
2import java.util.*;
3
4class Fib {
5	static int getFibonacci(int n) {
6		if (n == 0 || n == 1) {
7			return n;
8		}
9
10		// 初始化变量
11		int n1 = 1;
12		int n2 = 0;
13		int res = 0;
14
15		// 从 2 开始循环，因为我们已经知道 n1 和 n2
16		for (int i = 2; i <= n; ++i) {
17			// 计算新的结果
18			res = n1 + n2;
19
20			// 更新 n2 和 n1
21			n2 = n1;
22			n1 = res;
23		}
24
25		return res;
26	}
27
28	public static void main(String[] args) {
29		int[] inputs = {1, 5, 7, 10};
30		for (int i = 0; i < inputs.length; i++) {
31			System.out.println(i+1 + ".  getFibonacci(" + inputs[i] + ") = " + getFibonacci(inputs[i]));
32			System.out.println(
33					"------------------------------------------------------------------------------------------------------\n");
34		}
35	}
36}

Python

1def get_fibonacci(n):
2    if n == 0 or n == 1:
3        return n
4
5    # 初始化变量
6    n_1 = 1
7    n_2 = 0
8    res = 0
9
10    # 从 2 开始循环，因为我们已经知道 n_1 和 n_2
11    for i in range(2, n+1):
12        # 计算新的结果
13        res = n_1 + n_2
14
15        # 更新 n_2 和 n_1
16        n_2 = n_1
17        n_1 = res
18
19    return res
20
21
22def main():
23    inputs = [1, 5, 7, 10]
24    for i in range(len(inputs)):
25        print(str(i+1) + ".  get_fibonacci(" +
26              str(inputs[i]) + ") = " + str(get_fibonacci(inputs[i])))
27        print("------------------------------------------------------------------------------------------------------\n")
28
29
30if __name__ == '__main__':
31    main()

JS

1let getFibonacci = function(n) {
2
3  if (n === 0 || n === 1) {
4    return n;
5  }
6  
7  // 初始化变量
8  let n1 = 1;
9  let n2 = 0;
10  let result = 0;
11  
12  // 从 2 开始循环，因为我们已经知道 n1 和 n2
13  for (let i=2; i <= n ; ++i) {
14    // 计算新的结果  
15    result = n1 + n2;
16    n2 = n1;
17    n1 = result;
18  }
19
20  return result;
21};
22  
23let inputs = [1, 5, 7, 10]
24
25for (let i = 0; i < inputs.length; i++){
26  console.log(i+1 + ".  getFibonacci(" + (inputs[i]) + ") = " + getFibonacci(inputs[i]));
27  console.log("------------------------------------------------------------------------------------------------------\n");
28}

Ruby

1def get_fibonacci(n)
2
3  # 基础情况
4  return n if n == 0 || n == 1
5  
6  # 初始化变量
7  n_1, n_2, res = 1, 0, 0
8
9  # 从 2 开始循环，因为我们已经知道 n_1 和 n_2
10  i = 2
11  while i <= n
12    # 计算新的结果
13    res = n_1 + n_2
14
15    # 更新 n_2 和 n_1
16    n_2 = n_1
17    n_1 = res
18    i+=1
19  end
20
21  return res
22end
23
24inputs = [1, 5, 7, 10]
25inputs.length.times do |i|
26  puts (i + 1).to_s + ".  get_fibonacci(" + inputs[i].to_s + ") = " + get_fibonacci(inputs[i]).to_s
27  puts "------------------------------------------------------------------------------------------------------\n"
28end

Go

1package main
2import (
3	"fmt"
4)
5
6func GetFibonacci(n int) int {
7
8	if n == 0 || n == 1 {
9		return n
10	}
11
12	// 初始化变量
13	n1, n2, result := 1, 0, 0
14
15	// 从 2 开始循环，因为我们已经知道 n1 和 n2
16	for i := 2; i <= n; i++ {
17		// 计算新的结果
18		result = n1 + n2
19
20		// 更新 n2 和 n1
21		n2 = n1
22		n1 = result
23	}
24
25	return result
26}
27
28func main() {
29
30   inputs := []int{1, 5, 7, 10} 
31	
32	for i, input := range inputs {
33		fmt.Printf("%d.  GetFibonacci(%d) = %d\n", i + 1, input, GetFibonacci(input))
34    	fmt.Print( "------------------------------------------------------------------------------------------------------\n")
35	}
36}

时间复杂度

该解法的时间复杂度为 O(n)O(n)。

空间复杂度

该解法的空间复杂度为 O(1)O(1)。

回溯法

第 n 个三步斐波那契数