【每日一题】Fibonacci（斐波那契）数列

Dear 丶 2022-12-26 10:13 135阅读 0赞

**题目来源**  
牛客网  
链接：[斐波那契数列][Link 1]

**题目描述**  
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数"

输入：

> 15

输出：

> 2

**解题思路**  
本题可以通过先找到距离N最近的两个Fibonacci数，这两个数分别取自距离N的最近的左边一个数L和右边一个数R，然后通过函数min(N - L, R - N)找到最小步数。

**代码展示**

#include <iostream>
    using namespace std;
    
    int min(int a, int b)
    {
        
    	if(a < b)
    		return a;
    	else
    		return b;
    }
    
    int main()
    {
        
    	int N, f, l = 0, r = 0, f0 = 0, f1 = 1;
    	cin >> N;
    	while(1)
    	{
        
    		f = f0 + f1;
    		f0 = f1;
    		f1 = f;
    		//找到比N小且距离N最近的数，求出距离
    		if(f < N)
    			l = N - f;
    		//找到比N大且距离N最近的数，求出距离
    		else
    		{
        
    			r = f - N;
    			break;
    		}
    	}
    	cout << min(l, r) << endl;
    	return 0;
    }

[Link 1]: https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=85&&tqId=29846&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关【每日一题】Fibonacci（斐波那契）数列

题目来源牛客网链接：[斐波那契数列][Link 1] 题目描述 Fibonacci数列是这样定义的： F\[0\] = 0 F\[1\] = 1

Dear 丶/ 2022年12月26日 10:13/ 0 赞/ 136 阅读

相关 Fibonacci 斐波那契数列（3种方法）

Fibonacci数列的递推公式为：`Fn=Fn-1+Fn-2`，其中`F1=F2=1`。 -------------------- 输入格式输入包含一个整数n。

傷城~/ 2022年09月10日 03:15/ 0 赞/ 150 阅读

相关斐波那契数列

关于斐波那契数列的解法，本人找到了一种比较简单的方法，结果是正确的，不知道各位有没有另外更好的解法，一起探讨探讨。 import java.util.; pu

╰+攻爆jí腚メ/ 2022年08月01日 12:15/ 0 赞/ 353 阅读

相关 05_斐波那契数列（Fibonacci sequence）

package exercise; / 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又

矫情吗；*/ 2022年07月26日 05:17/ 0 赞/ 152 阅读

相关斐波那契数列

定义：斐波那契数列指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 这个数列从第三项开始，每一项都等于前两项之和。

矫情吗；*/ 2022年07月13日 04:49/ 0 赞/ 307 阅读

相关斐波那契数列

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，

冷不防/ 2022年07月13日 03:19/ 0 赞/ 327 阅读

相关斐波那契数列

class FibIter(object): def __init__(self, lenth): self.lent

一时失言乱红尘/ 2022年05月27日 13:51/ 0 赞/ 324 阅读

相关斐波那契数列

include<iostream> using namespace std; int fibonacci1(int t) { if(t

古城微笑少年丶/ 2022年05月09日 08:58/ 0 赞/ 290 阅读

相关 Java实现斐波那契数列Fibonacci

import java.util.Scanner; public class Main1 { sta

分手后的思念是犯贱/ 2022年01月14日 23:07/ 0 赞/ 197 阅读

相关面试题之斐波那契数列（Fibonacci）系列

\[定理1\] 标准Fibonacci序列（即第0项为0，第1项为1的序列）当N大于1时，一定有f(N)和f(N-1)互质其实，结合“互质”的定义，和一个很经典的算法就可以

╰半夏微凉°/ 2021年10月18日 19:30/ 0 赞/ 623 阅读