题解 | 计算斐波那契数最小差值

#include <iostream>
#include <vector>
#include<climits>
using namespace std;

class Solution {
public:
    int minFibonacciDiff(int n) {
        // 生成斐波那契数列
        vector<int> fib;
        fib.push_back(0);
        fib.push_back(1);
        
        // 生成不超过n+1000的斐波那契数
        while (fib.back() <= n + 1000) {
            fib.push_back(fib[fib.size()-1] + fib[fib.size()-2]);
        }
        
        // 找到最小差值
        int minDiff = INT_MAX;
        for (int num : fib) {
            minDiff = min(minDiff, abs(num - n));
            // 如果当前数已经大于n，后面的差值只会更大
            if (num > n) break;
        }
        
        return minDiff;
    }
};

int main() {
    int n;
    cin >> n;
    
    Solution solution;
    cout << solution.minFibonacciDiff(n) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int minFibonacciDiff(int n) {
            // 生成斐波那契数列
            List<Integer> fib = new ArrayList<>();
            fib.add(0);
            fib.add(1);
            
            // 生成不超过n+1000的斐波那契数
            while (fib.get(fib.size()-1) <= n + 1000) {
                fib.add(fib.get(fib.size()-1) + fib.get(fib.size()-2));
            }
            
            // 找到最小差值
            int minDiff = Integer.MAX_VALUE;
            for (int num : fib) {
                minDiff = Math.min(minDiff, Math.abs(num - n));
                // 如果当前数已经大于n，后面的差值只会更大
                if (num > n) break;
            }
            
            return minDiff;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        Solution solution = new Solution();
        System.out.println(solution.minFibonacciDiff(n));
    }
}

def min_fibonacci_diff(n: int) -> int:
    # 生成斐波那契数列
    fib = [0, 1]
    
    # 生成不超过n+1000的斐波那契数
    while fib[-1] <= n + 1000:
        fib.append(fib[-1] + fib[-2])
    
    # 找到最小差值
    min_diff = float('inf')
    for num in fib:
        min_diff = min(min_diff, abs(num - n))
        # 如果当前数已经大于n，后面的差值只会更大
        if num > n:
            break
    
    return min_diff

if __name__ == "__main__":
    n = int(input())
    print(min_fibonacci_diff(n))