1176 The Closest Fibonacci Number – PAT甲级真题

The Fibonacci sequence Fn is defined by Fn+2=Fn+1+Fn for n≥0, with F0=0 and F1=1. The closest Fibonacci number is defined as the Fibonacci number with the smallest absolute difference with the given integer N.

Your job is to find the closest Fibonacci number for any given N.

Input Specification:

Each input file contains one test case, which gives a positive integer N (≤10^8).

Output Specification:

For each case, print the closest Fibonacci number. If the solution is not unique, output the smallest one.

Sample Input:

305

Sample Output:

233

Hint:

Since part of the sequence is { 0, 1, 1, 2, 3, 5, 8, 12, 21, 34, 55, 89, 144, 233, 377, 610, … }, there are two solutions: 233 and 377, both have the smallest distance 72 to 305. The smaller one must be printed out.

题目大意：为任意给定的整数N找出与之最近的斐波那契数。如果解不唯一，输出最小的那个数

分析：使用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题解离线版