计算斐波那契数最小差值

[编程题]计算斐波那契数最小差值

热度指数：2899 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个整数 n ，计算 n 与斐波那契数的最小差值(绝对值)

说明：

斐波那契数定义：

从0，1开始后面的数值为前面两者之和, 即第三个数为第一和第二个数之和

形如：0，1，1，2，3，5，8，13，21。。。。其中3为1与2的和，5为2与3的和，8为3与5的和等等

要计算的数值案例：

输入15，与斐波那契数相减，与13相减的绝对值是2，与21相减的绝对值是6，与众多斐波那契数相减的最小差值为2

因此输入15，输出2

数据范围：输入的数满足 $1 \le n \le 1000 \$

输入描述:

输入任意整数

输出描述:

一个整数

示例1

输入

输出

说明

15与“0，1，1，2，3，5，8，13，21。。。。”当中的13差值的绝对值最小，与21的差值为6，与8的差值为7

示例2

输入

输出

说明

斐波那契数列中存在 1 ，因此最小差值是 0

算法知识视频讲解

Python

王子的诱惑

while 1:
    try:
        n=int(input())
        if n==0:
            print(0)
        elif n==1:
            print(0)
        else:
            i,re=2,[0,1,1]
            while re[i]<n:
                re.append(re[i-1]+re[i])
                i+=1
            print(min(abs(re[i-1]-n),abs(re[i]-n)))
    except:
        break

发表于 2020-08-17 17:31:34 回复(0)