本文主要是介绍PAT(甲级)2020年冬季考试7-1 The Closest Fibonacci Number (20分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
7-1The Closest Fibonacci Number(20分)
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 (≤108 ).
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.
#include<bits/stdc++.h>
using namespace std;
int main() {int a = 0, b = 1, c = 0, N;cin >> N;while (c < N) {c = a + b;a = b;b = c;}printf("%d", abs(N - a) > abs(b - N) ? b : a);
}
这篇关于PAT(甲级)2020年冬季考试7-1 The Closest Fibonacci Number (20分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!