牛客网 Fibonacci数列

一. 题目

1. 题目

数列是这样定义的：

因此，

数列就形如：

在

数列中的数我们称为

数。给你一个

，你想让其变为一个

数，每一步你可以把当前数字

变为

或者

，现在给你一个数

求最少需要多少步可以变为

数。

输入描述: 输入为一个正整数

输出描述: 输出一个最小的步数变为

数" 示例

输入

输出

2. 原题链接

牛客网 Fibonacci数列

二. 解题思路

1. 思路分析

找某一个数n变成最近的

数的最小步数

找到与这个数相邻的两个

数，并求出这个数与二者差值的绝对值

,二者的较小值就是最小步数

的范围在

之间，

是

时最小步数直接就是

，主要是要找到

在哪两个相邻的

数之间

已经知道

数的前两项，后面的

数可以由前两项推出；可以递归或循环得出除前两项的数

用两个变量

记录两个初始的

数

和

，在一个循环中判断

与

的大小关系

时说明不在这两个数之间，借助中间变量得到的新的

数来更新这两个数，直到

在这两个数之间，判断差值的绝对值之后再输出。

2. 代码详解

#include <stdio.h>

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

三. 本题知识与收获

本题是斐波那契数列的应用，当知道所求步数与相邻斐波那契数的关系后，关键就是到输入的数在哪两个相邻的斐波那契数之间。 另一种思路是创建两个变量n1，n2记录n的初始值，两个计数器cnt1、cnt2分别记录左右的步数。每次判断n1、n2是否是斐波那契数。如果有一个是就输出两个计数器的较小值；如果两个都不是，则两个计数器都加1，数n1减1，n2加1。