牛客考试题复习

青旅半醒 2023-09-24 13:36 39阅读 0赞

## 题目 ##

【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：  
输入:

> 15

输出:

> 2

### 答案 ###

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<math.h>
    int main()
    {
        
    	int n = 0;
    	scanf("%d", &n);
    	int f1 = 0;
    	int f2 = 1;
    	int f3 = f2 + f1;       
    	while (1)
    	{
        
    		if (n == f2)
    		{
        
    			printf("0\n");     //因为输入的n大于等于1，所以n也可能一开始等于f2，n=f2就只需要0步变换
    		}
    		else if (n < f2)     
    		{
        
    			if (abs(n - f2) < abs(n - f1))              //abs为求绝对值函数
    			{
        
    				printf("%d\n", abs(n - f2));
    			}
    			else
    			{
        
    				printf("%d\n", abs(n - f1));
    			}
    		}
    		f1 = f2;                //n大于f2，循环会一直执行下去，直到n处于f1跟f2之间，随后做差求出最小的步数
    		f2 = f3;
    		f3 = f1 + f2;
    	}
    	return 0;
    }

![在这里插入图片描述][8e6e07eb0a2a4d40a627d57e2ffa8dc5.png]

#### 第一次接触的想法 ####

#include<stdio.h>
    int main()
    {
        
    int n=0;
    int a=1;
    int i=0;
    int num=1;
    int arr[10000]={
        0};
    int j=0;
    int y=0;
    scanf("%d",&n);
    for(i=0;num<=1000000;i=y)       //Fibonacci数列一个一个找出来放入数组
    {
        
    y=num;
    num+=i;
    arr[j]=num;
    j++;
    }
    int c=0;
    for(c=0;c<j-1;c++)      //遍历数组对比
    if((arr[c]<=n)&&(arr[c+1]>=n))
    {
        
    printf("%d\n",((n-arr[c])>(arr[c+1]-n))?(arr[c+1]-n):(n-arr[c]));
    }
    return 0;
    }

先把Fibonacci数列一个一个找出来,然后遍历数组一个个对比,确实盲目麻烦.

[8e6e07eb0a2a4d40a627d57e2ffa8dc5.png]: https://img-blog.csdnimg.cn/8e6e07eb0a2a4d40a627d57e2ffa8dc5.png