【Java版oj】day07Fibonacci数列

清疚 2024-03-31 17:29 78阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

--------------------

> ## 一、原题再现 ##
> 
> [Fibonacci数列\_牛客题霸\_牛客网][Fibonacci]
> 
> ### 描述 ###
> 
> 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
> 
> 输入：
> 
> 15
> 
> 输出：
> 
> 2

> ## 二、问题分析 ##
> 
> 本题代码很简单，首先需要明白斐波那契数是前两个数相加得来的数列。本题可以通过先找到距离N最近的两个Fibonacci数，这两个数分别取自距离N的最近的左边一个数L和右边一个数，然后通过比较两个数到N的距离大小得出结果。  
>

> ## 三、完整代码 ##
> 
>     import java.util.*;
>     public class Main {
>         public static void main(String[] args) {
>             Scanner in = new Scanner(System.in);
>             int n = in.nextInt();
>             int fiboBefore = 0;
>             int fiboAfter = 1;
>             int ans = 0;
>             while (n > fiboAfter) {
>                 int tmp = fiboAfter;
>                 fiboAfter = fiboAfter + fiboBefore;
>                 fiboBefore = tmp;
>             }
>             ans = (fiboAfter - n) < (n - fiboBefore) ? (fiboAfter - n) : (n - fiboBefore);
>             System.out.println(ans);
>         }
>     }
> 
> ![5af070ed943642028afa8cc64e97d708.png][]

--------------------

![883e76fdb5ce406a88da1971244bded4.png][]

[Fibonacci]: https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=85&&tqId=29846&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
[5af070ed943642028afa8cc64e97d708.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/84df02e9bf5246e7a07b743c1abcdfc9.png
[883e76fdb5ce406a88da1971244bded4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/535646be8d6e441e9a5c11617e2395cd.png