当前位置：首页 > news >正文

OJ练习之Fibonacci数列

news 2026/4/16 1:03:06

WY22 Fibonacci数列

入门通过率:36.94% 时间限制:1秒空间限制:32M
知识点：数学模拟

描述

Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, …，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

输入描述：

输入为一个正整数N(1 ≤ N ≤ 1,000,000)

输出描述：

输出一个最小的步数变为Fibonacci数

示例1

输入：

输出：

思路一：

#include<iostream>#include<vector>usingnamespacestd;// 从第2个斐波那契数开始，与这个整数做比较，当大于N的时候，保存这个斐波那契数，同时保存上一个斐波那契数，让N分别于这两个数求差值，哪个小就是哪个// 因为题目中已经说明了是N肯定大于等于1，所以可以从第二个或第三个斐波那契数开始比较intmain(){intN=0;vector<longlong>Fib;// 存斐波那契数intleft=-1;// 记录下标intright=-1;// 记录下标inti=1;// 下标从1开始，从第二个斐波那契数开始比较intmin=0;Fib.push_back(0);Fib.push_back(1);cin>>N;while(true){// 如果i > 1,每次就要更新最新的斐波那契值if(i>1){Fib.push_back(Fib[i-1]+Fib[i-2]);}if(Fib[i]==N){min=0;break;}elseif(Fib[i]>N){right=i;left=i-1;min=Fib[right]-N;if(N-Fib[left]<min){min=N-Fib[left];}break;}else{i++;}}cout<<min;return0;}

思路二：

#include<iostream>#include<vector>usingnamespacestd;// 只保留三个斐波那契数a,b,c，因为初始第三个斐波那契数c也是1，只需要让c与N其对比，直到c大于等于N，就说明N满足 b<=N<=c(数学表示)，那么只需要获得b到N，和N到c距离的最小值即可。intmain(){inta=0,b=1,c=1;intN=0;cin>>N;while(true){if(c<N){a=b;b=c;c=a+b;}else{cout<<min(c-N,N-b);break;}}return0;}

思路二代码简化：

#include<iostream>#include<vector>usingnamespacestd;// 只保留三个斐波那契数a,b,c，因为初始第三个斐波那契数c也是1，只需要让c与N其对比，直到c大于等于N，就说明N满足 b<=N<=c(数学表示)，那么只需要获得b到N，和N到c距离的最小值即可。intmain(){inta=0,b=1,c=1;intN=0;cin>>N;while(c<N){a=b;b=c;c=a+b;}// 走到这里就说明N满足 b<=N<=c(数学表示)cout<<min(c-N,N-b);return0;}