如何找到最近的斐波那契数列编号？

Question

我的下一步是，如果输入不在斐波那契数列中，则程序必须给出一个输出，该数字的序列中的数字最接近输入。我不知道如何进行，有人可以帮助我吗？

def fibs():
    a,b = 0,1
    yield a
    yield b
    while True:
        a,b = b,a+b
        yield b

n = int(input("please, enter a number: "))
for fib in fibs():
    if n == fib:
        print("Yes! Your number is a Fibonacci number!")
        break
    if fib > n:
        print("No! Your number is not a Fibonacci number!")
        break

Answer 1

这是使用发生器的一种简单方法，可以测试少量数字。

def fibs():
    a,b = 0,1
    yield a
    yield b
    while True:
        a,b = b,a+b
        yield b

def nearest_fib(n):
    ''' If n is a Fibonacci number return True and n
        Otherwise, return False and the nearest Fibonacci number
    '''
    for fib in fibs():
        if fib == n:
            return True, n
        elif fib < n:
            prev = fib
        else:
            # Is n closest to prev or to fib?
            if n - prev < fib - n:
                return False, prev
            else:
                return False, fib

# Test
for i in range(35):
    print(i, nearest_fib(i))

输出

0 (True, 0)
1 (True, 1)
2 (True, 2)
3 (True, 3)
4 (False, 5)
5 (True, 5)
6 (False, 5)
7 (False, 8)
8 (True, 8)
9 (False, 8)
10 (False, 8)
11 (False, 13)
12 (False, 13)
13 (True, 13)
14 (False, 13)
15 (False, 13)
16 (False, 13)
17 (False, 21)
18 (False, 21)
19 (False, 21)
20 (False, 21)
21 (True, 21)
22 (False, 21)
23 (False, 21)
24 (False, 21)
25 (False, 21)
26 (False, 21)
27 (False, 21)
28 (False, 34)
29 (False, 34)
30 (False, 34)
31 (False, 34)
32 (False, 34)
33 (False, 34)
34 (True, 34)

更新资料

这是一种使用Binet公式首先近似y 的更有效方法：F（y）= n。然后，它使用与矩阵形式有关的一对身份（可以在O（log（n））时间中计算F（n））来递归地找到最接近n的斐波那契数。递归非常快，因为它使用缓存来保存已经计算的值。没有缓存，该算法的速度与Rockybilly的速度大致相同。

from math import log, sqrt

def fast_fib(n, cache={0: 0, 1: 1}):
    if n in cache:
        return cache[n]
    m = (n + 1) // 2
    a, b = fast_fib(m - 1), fast_fib(m)
    fib = a * a + b * b if n & 1 else (2 * a + b) * b
    cache[n] = fib
    return fib

logroot5 = log(5) / 2
logphi = log((1 + 5 ** 0.5) / 2)

def nearest_fib(n):
    if n == 0:
        return 0
    # Approximate by inverting the large term of Binet's formula
    y = int((log(n) + logroot5) / logphi)
    lo = fast_fib(y)
    hi = fast_fib(y + 1)
    return lo if n - lo < hi - n else hi

for i in range(35):
    print(i, nearest_fib(i))

输出

0 0
1 1
2 2
3 3
4 5
5 5
6 5
7 8
8 8
9 8
10 8
11 13
12 13
13 13
14 13
15 13
16 13
17 21
18 21
19 21
20 21
21 21
22 21
23 21
24 21
25 21
26 21
27 21
28 34
29 34
30 34
31 34
32 34
33 34
34 34

请注意，对缓存fast_fib使用默认的可变参数，但这没关系，因为我们希望缓存记住其先前的内容。

在我的速度测试中，默认的可变参数高速缓存比任何其他形式的高速缓存都快，但是它的缺点是无法从函数外部清除高速缓存，并且如果您向函数中添加逻辑以清除高速缓存，则会影响性能。为广大的来电时，你不希望清除缓存。

更新资料

它是实际上可以从功能外清除默认可变参数缓存。我们可以通过函数的.__default__属性来访问函数的默认参数（或.func_defaults在旧版本的Python 2中；.__default__在Python 2.6中有效，但在2.5中不可用）。

例如，

d = fast_fib.__defaults__[0]
d.clear()
d.update({0: 0, 1: 1})

这是一些代码（可在Python 2和Python 3上运行），它们针对为此问题提交的某些算法执行时序测试。Rockybilly的版本与我的第一个版本非常相似，只是它避免了保存以前的值。我还使OP的fibs生成器更加紧凑。

道格拉斯（Douglas）的代码适用于小数，或者当参数实际上是斐波那契数时，但是对于大的非斐波那契数，由于缓慢的一对一搜索，它变得非常慢。通过避免重新计算各种数量，我已经能够对其进行一些优化，但这并不会对运行速度产生太大的影响。

在此版本中，我的fast_fib()函数使用了全局缓存，因此可以在测试之间将其清除，以使计时更公平。

#!/usr/bin/env python3

""" Find the nearest Fibonacci number to a given integer

    Test speeds of various algorithms

    See /sf/ask/2847806321/

    Written by PM 2Ring 2016.11.19
    Incorporating code by Rockybilly and Douglas
"""

from __future__ import print_function, division
from math import log, sqrt
from time import time

def fibs():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

def nearest_fib_Rocky(n):
    ''' Find the nearest Fibonacci number to n '''
    fibgen = fibs()
    for fib in fibgen:
        if fib == n:
            return n
        elif fib > n:
            next_fib = next(fibgen)
            return next_fib - fib if 2 * n < next_fib else fib

def nearest_fib_Doug(n):
    a = 5 * n * n
    if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0:
        return n
    c = 1
    while True:
        m = n + c
        a = 5 * m * m
        if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0:
            return m
        m = n - c
        a = 5 * m * m
        if sqrt(a + 4)%1 == 0 or sqrt(a - 4)%1 == 0:
            return m
        c += 1

cache={0: 0, 1: 1}
def fast_fib(n):
    if n in cache:
        return cache[n]
    m = (n + 1) // 2
    a, b = fast_fib(m - 1), fast_fib(m)
    fib = a * a + b * b if n & 1 else (2 * a + b) * b
    cache[n] = fib
    return fib

logroot5 = log(5) / 2
logphi = log((1 + 5 ** 0.5) / 2)

def nearest_fib_PM2R(n):
    if n == 0:
        return 0
    # Approximate by inverting the large term of Binet's formula
    y = int((log(n) + logroot5) / logphi)
    lo = fast_fib(y)
    hi = fast_fib(y + 1)
    return lo if n - lo < hi - n else hi

funcs = (
    nearest_fib_PM2R,
    nearest_fib_Rocky,
    nearest_fib_Doug,
)

# Verify that all the functions return the same result
def verify(lo, hi):
    for n in range(lo, hi):
        a = [f(n) for f in funcs]
        head, tail = a[0], a[1:]
        if not all(head == u for u in tail):
            print('Error:', n, a)
            return False
    else:
        print('Ok')
        return True

def time_test(lo, hi):
    print('lo =', lo, 'hi =', hi)
    for f in funcs:
        start = time()
        for n in range(lo, hi):
            f(n)
        t = time() - start
        print('{0:18}: {1}'.format(f.__name__, t))
    print()

verify(0, 1000)
cache={0: 0, 1: 1}
time_test(0, 1000)

funcs = funcs[:-1]
cache={0: 0, 1: 1}
time_test(1000, 50000)

典型输出

Ok
lo = 0 hi = 1000
nearest_fib_PM2R  : 0.005465507507324219
nearest_fib_Rocky : 0.02432560920715332
nearest_fib_Doug  : 0.45461463928222656

lo = 1000 hi = 50000
nearest_fib_PM2R  : 0.26880311965942383
nearest_fib_Rocky : 1.266334056854248

这些时间是在Linux上运行Python 3.6的旧2GHz 32位计算机上进行的。Python 2.6给出了类似的计时。

FWIW，Rockybilly和我的代码都可以轻松处理非常大的数字。这是的时间输出time_test(10**1000, 10**1000 + 1000)：

nearest_fib_PM2R  : 0.011492252349853516
nearest_fib_Rocky : 7.556792497634888