牛客网刷题1【最小步数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数。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

int main()
{
     
	int n = 0;
	scanf("%d", &n);
	int a = 0;
	int b = 1;
	int c = 0;
	while (1)
	{
     
		if (n == b)
		{
     
			printf("0\n");
			break;
		}
		else if (n < b)
		{
     
			if (abs(n - a) > abs(b - n))
			{
     
				printf("%d\n", abs(b - n));
			}
			else
			{
     
				printf("%d\n", abs(n - a));
			}
			break;
		}
		c = a + b;
		a = b;
		b = c;
	}
	
	return 0;
}

打印结果

1. 当输入的一个数正好等于 a或者b，那么这个数就是Fibonacci数列上的数，否则即不是Fibonacci数列上的数，
2. 这里我们以我们的条件语句选择 if (n == b)与 else if (n < b)来判断输入的数是否是Fibonacci数列上的数，当然我们也可以用if (n == a)与 else if (n > a)来判断是否是Fibonacci数列上的数。不过题目给定输入范围是(1 ≤ N ≤ 1,000,000)，即从F(1)=1开始，所以我们选择第一种条件语句来判断是否是Fibonacci数列上的数。
3. 当输入的数不是是否是Fibonacci数时，我们计算他到前面a与到后面的b的距离，就能算出他到前面的a近还是到后面的b近。
4. int abs (int n);函数是计算绝对值大小的函数，头文件为#include <stdlib.h>。
5. c = a + b;
   a = b;
   b = c;
   即是Fibonacci数列的本质，我们通过这三个式子来逼近我们输入的n。
6. 我们输入15，距离他成为Fibonacci数，只要减少2变成13就行了。