2017网易---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

输入

输出

2

题目链接：https://www.nowcoder.com/practice/18ecd0ecf5ef4fe9ba3f17f8d00d2d66?tpId=85&tqId=29846&tPage=1&rp=1&ru=/ta/2017test&qru=/ta/2017test/question-ranking

法一：存储fibonacci数列到1000000，然后对于输入数据，分别向左和向右遍历，求解最短步数。o(n^2)。代码如下（耗时44ms）：

 1 package fibonacci数列;
 2 
 3 import java.io.BufferedReader;
 4 import java.io.IOException;
 5 import java.io.InputStreamReader;
 6 
 7 public class Main {
 8 
 9     public static void main(String[] args) throws IOException {
10         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
11         String line = in.readLine();
12         int f[] = {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040};
13         int num = Integer.parseInt(line);
14         int r = num + 1, l = num;
15         boolean flag_l = false, flag_r = false;
16         while(true) {
17             //向左
18             int left_l = 0, right_l = 30;
19             while(left_l <= right_l) {
20                 int mid = (right_l + left_l) / 2;
21                 if(f[mid] < l) {
22                     left_l = mid + 1;
23                 }
24                 else if(f[mid] > l) {
25                     right_l = mid - 1;
26                 }
27                 else {
28                     flag_l = true;
29                     break;
30                 }
31             }
32             if(flag_l == true) {
33                 break;
34             }
35             //向右
36             int left_r = 0, right_r = 30;
37             while(left_r <= right_r) {
38                 int mid = (right_r + left_r) / 2;
39                 if(f[mid] < r) {
40                     left_r = mid + 1;
41                 }
42                 else if(f[mid] > r) {
43                     right_r = mid - 1;
44                 }
45                 else {
46                     flag_r = true;
47                     break;
48                 }
49             }
50             if(flag_r == true) {
51                 break;
52             }
53             l--;
54             r++;
55         }
56         if(flag_l == true) {
57             System.out.println(num - l);
58         }
59         else {
60             System.out.println(r - num);
61         }
62     }
63 
64 }

View Code

法二（借鉴）：直接遍历fibonacci，记录输入数据左右两边的数值，一旦右边的数值大于输入的数据，则结束运算。求解min(num-left,right-num)即可。o(n)。代码如下（耗时13ms）：

 1 import java.io.BufferedReader;
 2 import java.io.IOException;
 3 import java.io.InputStreamReader;
 4 
 5 public class Main {
 6 
 7     public static void main(String[] args) throws IOException {
 8         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 9         String line = in.readLine();
10         int x = 0, y = 1;
11         int num = Integer.parseInt(line);
12         int ma = x + y, mi = y;
13         while(ma < num) {
14             y = mi;
15             mi = ma;
16             ma = mi + y;
17         }
18         int res = Math.min(num - mi, ma - num);
19         System.out.println(res);
20     }
21 
22 }

View Code