我的下一步是，如果输入不在斐波那契数列中，程序必须给出一个输出，其中的数字在最接近输入的数列中。我不知道如何进行，有人可以帮助我吗？
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
请您参考如下方法:
这是一种使用生成器的简单方法，适用于测试小数。
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's formula首先近似 y:F(y) = n。然后它使用一对与 matrix form 相关的身份。 (它可以在 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 mutable argument用于缓存，但在这里没关系，因为我们希望缓存记住它以前的内容。
在我的速度测试中，默认的可变参数缓存比任何其他形式的缓存都快，但它的缺点是无法从函数外部清除缓存，如果您向函数添加逻辑以清除缓存当您不想清除缓存时，会影响大多数调用的性能。
更新
实际上可以从函数外部清除默认的可变参数缓存。我们可以通过函数的 .__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 https://stackoverflow.com/questions/40682947/fibonacci-in-python
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
