Fibonacci series (Netease 2017 school recruitment)

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