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）：

 package fibonacci数列;

 import java.io.BufferedReader;

 import java.io.IOException;

 import java.io.InputStreamReader;

 public class Main {

     public static void main(String[] args) throws IOException {

         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

         String line = in.readLine();

         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};

         int num = Integer.parseInt(line);

         int r = num + 1, l = num;

         boolean flag_l = false, flag_r = false;

         while(true) {

             //向左

             int left_l = 0, right_l = 30;

             while(left_l <= right_l) {

                 int mid = (right_l + left_l) / 2;

                 if(f[mid] < l) {

                     left_l = mid + 1;

                 }

                 else if(f[mid] > l) {

                     right_l = mid - 1;

                 }

                 else {

                     flag_l = true;

                     break;

                 }

             }

             if(flag_l == true) {

                 break;

             }

             //向右

             int left_r = 0, right_r = 30;

             while(left_r <= right_r) {

                 int mid = (right_r + left_r) / 2;

                 if(f[mid] < r) {

                     left_r = mid + 1;

                 }

                 else if(f[mid] > r) {

                     right_r = mid - 1;

                 }

                 else {

                     flag_r = true;

                     break;

                 }

             }

             if(flag_r == true) {

                 break;

             }

             l--;

             r++;

         }

         if(flag_l == true) {

             System.out.println(num - l);

         }

         else {

             System.out.println(r - num);

         }

     }

 }

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

 import java.io.BufferedReader;

 import java.io.IOException;

 import java.io.InputStreamReader;

 public class Main {

     public static void main(String[] args) throws IOException {

         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

         String line = in.readLine();

         int x = 0, y = 1;

         int num = Integer.parseInt(line);

         int ma = x + y, mi = y;

         while(ma < num) {

             y = mi;

             mi = ma;

             ma = mi + y;

         }

         int res = Math.min(num - mi, ma - num);

         System.out.println(res);

     }

 }

巴特西

2017网易---Fibonacci数列

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章