题解 | 斐波那契数列#

解题思路

斐波那契数列的计算有多种方法，这里使用最简单的迭代方法：

特判 $n=1$ 或 $n=2$ 的情况，直接返回 $1$
使用两个变量 $a$ 和 $b$ 分别记录前两个数
迭代 $n-2$ 次，每次计算下一个斐波那契数
最终 $b$ 即为所求的第 $n$ 个斐波那契数

代码

c++
java
python

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    if(n <= 2) {
        cout << 1 << endl;
        return 0;
    }
    
    int a = 1, b = 1;
    for(int i = 3; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    
    cout << b << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        if(n <= 2) {
            System.out.println(1);
            return;
        }
        
        int a = 1, b = 1;
        for(int i = 3; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        
        System.out.println(b);
    }
}

n = int(input())

if n <= 2:
    print(1)
else:
    a, b = 1, 1
    for i in range(3, n + 1):
        a, b = b, a + b
    print(b)

算法及复杂度

算法：迭代法
时间复杂度： $\mathcal{O}(n)$ - 需要迭代 $n-2$ 次
空间复杂度： $\mathcal{O}(1)$ - 只使用了常数个变量