1124 最近的斐波那契数 – PAT乙级真题

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

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

输入格式：

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

输出格式：

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

输入样例：

305

输出样例：

233

样例解释

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

分析：使用Fn、Fn_1、Fn_2分别表示当前的斐波那契数以及前两项。当Fn与N的绝对值大于等于Fn_1到N的绝对值时，就输出Fn_1的值并结束程序。数是越来越大的，再往后的数字与N的绝对值会越来越大

#include <iostream>
using namespace std;
int main() {
    int N, Fn, Fn_1 = 1, Fn_2 = 1;
    cin >> N;
    for (int i = 2; ; i++) {
        Fn = Fn_1 + Fn_2;
        if (abs(Fn - N) >= abs(Fn_1 - N)) {
            cout << Fn_1;
            return 0;
        }
        Fn_2 = Fn_1;
        Fn_1 = Fn;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int N, Fn, Fn_1 = 1, Fn_2 = 1;

cin >> N;

for (int i = 2; ; i++) {

Fn = Fn_1 + Fn_2;

if (abs(Fn - N) >= abs(Fn_1 - N)) {

cout << Fn_1;

return 0;

}

Fn_2 = Fn_1;

Fn_1 = Fn;

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版