题目描述

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数。

输入：

15

输出：

2

以下是本篇文章正文内容，下面案例可供参考

解题思路

定义

first

，

second

，

cur

，分别代表Fibonacci 数列的前三个数，当

second<=n

时，让

cur=first + second

，

first

，

second

分别往后挪一位，最终判断

second - n

和

n - first

的大小，输出最小的值

画图解释：

代码如下

import java.util.Scanner;

public class Main1 {
    /**
     * 每日一题-Fibonacci 数列步数问题
     * @param args
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int cur = 0;
            int first = 0;
            int second = 1;
            while(second <= n){
                cur = first + second;//当前等于前两项相加
                //分别往后挪一位
                first = second;
                second = cur;
            }
            //System.out.println((second-n)>(n-first)?n-first:second-n);
            System.out.println(Math.min((second - n), (n - first)));
            //输出步数最小的
        }
    }
}