首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7533

最近的斐波那契数 斐波那契数列 Fn 的定义为:对 n ≥ 0 有 F n+2 = F n+1 + F n ,初始值为 F 0 = 0 和 F 1 = 1。所谓…

最近的斐波那契数

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

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

时间限制:1000

内存限制:65536

输入

输入在一行中给出一个正整数 N(≤ 108)。

输出

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

样例输入

305

样例输出

233

提示

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

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;bits/stdc++.h&gt; #include&lt;math.h&gt; using namespace std; int main(){ int n[101]; n[0]=0,n[1]=1; for(int i=2;i&lt;43;i++){ n[i]=n[i-1]+n[i-2]; } int N; cin&gt;&gt;N; int min_diff=9999999; int temp[101]={0},j=0; for(int i=0;i&lt;43;i++){ if(abs(n[i]-N)&lt;min_diff){ min_diff=abs(n[i]-N); temp[j++]=n[i]; } } cout&lt;&lt;temp[j-1]; return 0; }</pre>
这道题暂未补解析。