# Title Description:

Fibonacci sequence is defined as follows:
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
Therefore, Fibonacci sequence is shaped as: 0, 1, 1, 2, 3, 5, 8, 13,..., the number in Fibonacci sequence is called Fibonacci number. Give you an N, you want to change it into a Fibonacci number. At each step, you can change the current number x to X-1 or X+1. Now give you a number n to find the minimum number of steps needed to change it into Fibonacci number.

# Enter a description:

The input is a positive integer N(1 ≤ N ≤ 1000000)

# Output Description:

Output a minimum step number to Fibonacci number“

# For example:

Input: 15 output: 2

# Program (test case passed):

```#include <iostream>
#include <cmath>
#define N 32 / / estimate 32 in advance to meet the scope of the topic

//fibonacci initialization
int fibonacci_init(int *,int);
//How many steps does it take to calculate the number of Fibonacci from N
int how_many_step(int n, int* arr, int num);

int main() {
using namespace std;
int fib_arr[N];	//Fibonacci series
fibonacci_init(fib_arr, N);
int input;
while (cin >> input) {
int step = how_many_step(input, fib_arr, N);
cout << step << endl;
}
getchar();
return 0;
}

int fibonacci_init(int * arr,int n) {
using namespace std;
if (n < 2)
cout << "Error"<<endl;
arr[0] = 0; arr[1] = 1;
for (int i = 2; i < n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return 0;
}

int how_many_step(int n, int* arr, int num) {
int tmp, ret;
ret = abs(n - arr[0]);
for (int i = 0; i < num; i++) {
tmp = abs(n - arr[i]);
if (tmp < ret)
ret = tmp;
}
return ret;
}
```

# Excellent code of Niuke:

```#include <iostream>
using namespace std;
int main(){
int N,l,r,f0=0,f1=1,f;
cin >> N;
while(1){
f = f0 + f1;
f0 = f1;
f1 = f;
if(f < N) l = N-f;
else{
r = f - N;
break;
}
}
cout << min(l,r) << endl;
return 0;
}
```

Posted on Fri, 31 Jan 2020 09:14:13 -0800 by nuklehed