牛客网 Fibonacci数列

一. 题目

1. 题目

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

数。给你一个

，你想让其变为一个

Fibonacci

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

变为

X-1

或者

X 1

，现在给你一个数

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

Fibonacci

数。

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

N(1 ≤ N ≤ 1,000,000)

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

Fibonacci

数" 示例

输入

输出

2. 原题链接

牛客网 Fibonacci数列

二. 解题思路

1. 思路分析

(1)

找某一个数n变成最近的

Fibonacci

数的最小步数

num

(2)

找到与这个数相邻的两个

Fibonacci

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

abs1，abs2

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

num

(3)

的范围在

(0,1000000)

之间，

是

时最小步数直接就是

，主要是要找到

在哪两个相邻的

Fibonacci

数之间

(4)

已经知道

Fibonacci

数的前两项，后面的

Fibonacci

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

(5)

用两个变量

a、b

记录两个初始的

Fibonacci

数

和

，在一个循环中判断

与

的大小关系

(6)

n大于b

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

Fibonacci

数来更新这两个数，直到

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

2. 代码详解

代码语言：javascript复制

#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。

break fibonacci int 变量递归

0 人点赞