PTA甲级——1176

1176 The Closest Fibonacci Number

原题

The Fibonacci sequence F**n is defined by F**n+2=F**n+1+F**n 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 (≤108).

Output Specification:

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

Sample Input:

1
305

Sample Output:

1
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.

思路

​ 大致题意:给出一个数,需要你找出斐波那切数列中最接近这个数的数。

​ 思路:先预处理前200个左右的斐波那切数列数,然后二分找找就ok了,其实不用二分也ok,数据量不大。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 200;
long long f[N];
int T, n;

int main()
{
ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
f[1] = 1, f[2] = 1;
for(int i = 3; i <= N; i++) f[i] = f[i - 1] + f[i - 2];
long long x;
cin >> x;
if (x == 1)
{
cout << "1\n";
return 0;
}
int l = 1, r = N;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (f[mid] <= x) l = mid;
else r = mid - 1;
}
int a = l, b = l + 1;
if (x - f[a] <= f[b] - x) cout << f[a] << '\n';
else cout << f[b] << '\n';
return 0;
}