Niu Ke's question -- Fibonacci series

Topic link ：Fibonacci The sequence

Title Description

describe
Fibonacci Sequence is defined like this ：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
therefore ,Fibonacci A sequence of numbers is like this ：0, 1, 1, 2, 3, 5, 8, 13, …, stay Fibonacci The numbers in a sequence are called Fibonacci Count . To give you one N, You want it to be a Fibonacci Count , At each step you can put the current number X Turn into X-1 perhaps X+1, Now I'll give you a number N How many steps does it take at least to change into Fibonacci Count .
Input description ：
The input is a positive integer N(1 ≤ N ≤ 1,000,000)
Output description ：
Output a minimum number of steps to Fibonacci Count "

Topic analysis

Each number in the Fibonacci sequence is the sum of the first two numbers , A number is given in the question N, It is necessary to calculate at least how many times to add or subtract to make it a Fibonacci number , Here is the solution to the problem ：
Find the distance N The last two Fibonacci series , namely N The two Fibonacci numbers on the left and right of , And then calculate the distance , The smaller value is the minimum number of steps and the Fibonacci number is the final result . There are two ways to calculate Fibonacci sequence, recursion and iteration , Here the Fibonacci sequence is calculated recursively . The code implementation is as follows ：

Code implementation

#include<iostream>
using namespace std;

int Fib(int n)
{
    
	if (n == 1|| n == 2)
	{
    
		return 1;
	}
	return Fib(n - 1) + Fib(n - 2);
}


int main()
{
    
	int n = 0;
	cin >> n;// Enter a positive integer N
	int i = 1;
	//int fib = Fib(i);
	while (Fib(i) <= n)// Find out the ratio n The big one Fib Value stops 
	{
    
		i++;
	}
	int min1 = Fib(i) - n;
	int min2 = n - Fib(i - 1);
	if (min1 < min2)
	{
    
		cout << min1 << endl;

	}
	else
	{
    
		cout << min2 << endl;

	}
	
	return 0;
}