题目描述

斐波那契数列 F n 的定义为：对 n≥0 有 F n+2 =F n+1​+F n，初始值为F =0 和 F 1 =1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。

本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。

输入格式

输入在一行中给出一个正整数 N（≤10 8 ）。

输出格式

在一行输出与 N 最近的斐波那契数。如果解不唯一，输出最小的那个数。

样例 #1

样例输入 #1

305

样例输出 #1

233

样例解释

部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 12, 21, 34, 55, 89, 144, 233, 377, 610, ... }。可见 233 和 377 到 305 的距离都是最小值 72，则应输出较小的那个解。

C++

#include<bits/stdc++.h>

using namespace std;

int n,dp[100000001],ans;
signed main() {
    cin>>n;
    dp[1]=1;
    for(int i=2;; ++i) {
        //斐波那契 后一项等于前两项的和
        dp[i]=dp[i-1]+dp[i-2];
        //如果刚好比输入的N大，说明当前位是N后一位的斐波那契数
        //取差值最小的，优先选择最小的数
        if(dp[i]>n) {
            ans=(n-dp[i-1] <= dp[i]-n) ? dp[i-1]:dp[i];
            break;
        }
    }
    cout<<ans;
    return 0;
}

Python3/Pypy3

n = int(input())
lst = [0, 1]
while True:
    temp = lst[0] + lst[1]
    lst[0] = lst[1]
    lst[1] = temp
    if temp > n:
        print(lst[0] if (n - lst[0]) <= (lst[1] - n) else lst[1])
        break