题解 | #斐波那契数列#

解题思路

这是一个斐波那契数列问题：

1. 数列的第一个和第二个数都是
2. 从第三个数开始，每个数等于前面两个数之和
3. 需要求出第 个数的值

解题方法：

1. 如果 ，直接返回
2. 否则，使用两个变量记录前两个数，迭代计算第 个数
3. 注意处理大数问题

代码

#include <iostream>
using namespace std;

int main() {
    int k;
    cin >> k;
    
    if (k <= 2) {
        cout << 1 << endl;
        return 0;
    }
    
    long long a1 = 1, a2 = 1;
    long long result;
    
    for (int i = 3; i <= k; i++) {
        result = a1 + a2;
        a1 = a2;
        a2 = result;
    }
    
    cout << result << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        
        if (k <= 2) {
            System.out.println(1);
            return;
        }
        
        long a1 = 1, a2 = 1;
        long result = 0;
        
        for (int i = 3; i <= k; i++) {
            result = a1 + a2;
            a1 = a2;
            a2 = result;
        }
        
        System.out.println(result);
        sc.close();
    }
}

k = int(input())

if k <= 2:
    print(1)
else:
    a1, a2 = 1, 1
    for i in range(3, k + 1):
        result = a1 + a2
        a1 = a2
        a2 = result
    
    print(result)

算法及复杂度

• 算法：动态规划（迭代）
• 时间复杂度：，其中 是要求的第 个数
• 空间复杂度：，只使用了常数个变量