2个斐波那契数的乘积
Product of 2 fibonacci numbers
我的作业：
Given a number, say prod (for product), we search two Fibonacci
numbers F(n) and F(n+1) verifying
F(n) * F(n+1) = prod if F(n) * F(n+1) = prod
Your function productFib takes an integer (prod) and returns an array:
[F(n), F(n+1), True] else
F(m) being the smallest one such as F(m) * F(m+1) > prod
[F(m), F(m+1), False]
Examples:
productFib(714) # should return [21, 34, True],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return [34, 55, False],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
我的代码：
def f(i):
if i == 0 :
return 0
if i == 1 :
return 1
return f(i-2) + f(i-1)
def productFib(prod):
i=1
final1 = 0
final2 = 0
while(f(i)*f(i+1) != prod and f(i)*f(i+1) < prod):
i += 1
final1 = f(i)
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]
我是编程新手；这对于大量运行非常慢。如何降低时间复杂度？
您的 fib 函数每次都从底部重新计算。您应该保存您已经知道的值。我的 python 生锈了，但我认为这样做就可以了：
dict = {}
def f(i):
if dict.has_key(i):
return dict[i]
if i == 0 :
return 0
if i == 1 :
return 1
sum = f(i-2) + f(i-1)
dict[i] = sum
return sum
def productFib(prod):
i=1
final1 = 0
final2 = 0
while(f(i)*f(i+1) != prod and f(i)*f(i+1) < prod):
i += 1
final1 = f(i)
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]
首先，您的 f 函数非常耗时：它计算 f(n) for low n 多次。 Memoize功能：将结果保存在一个列表中，再次计算时只需参考该列表即可。
memo = [1, 1]
def f(i):
global memo
if i >= len(memo):
# Compute all f(k) where k < i
f_of_i = f(i-2) + f(i-1)
memo.append(f_of_i)
return memo[i]
请注意，此序列仍然需要您按数字顺序填写 memo：f(i-2) 在 f(i- 1), 两者都在将 f(i) 添加到列表之前被调用。
用这个 returns 立即调用 f(100000000000000) (10^14)。我还没有尝试过更高的数字。
更新
我运行它以10的幂递增。在10^1650时，它还在全速打印输出，我打断了运行。
改进
通过直接从闭式方程计算 f(i)，您可以做得更好（对于许多应用程序）：
root5 = 5 ** 0.5
phi = (1 + root5) / 2
psi = (1 - root5) / 2
def f(i):
return int(round((phi ** i - psi ** i) / root5))
更多改进
直接计算i的正确值。
f(i) * f(i+1) 非常接近 phi**(2i+1) / 5。
def productFib(prod):
power = math.log(prod*5) / log_phi
i = int(round(power-1, 7)/2) + 1
low = f(i)
high = f(i+1)
# print i, low, high
answer = [low, high, low*high == prod]
return answer
print productFib(714)
print productFib(800)
print productFib(100000000000000000)
输出：
[21, 34, True]
[34, 55, False]
[267914296, 433494437, False]
您可以将以下代码用于您的 ProductFib 函数
def productFib2(prod):
i=0
final1 = f(i)
final2 = f(i+1)
while(final1 * final2 < prod):
i += 1
final1 = final2
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]
您可以通过使用生成器大大提高性能。
def fib():
# Generator that yields the last two fibonacci numbers on each iteration.
# Initialize
np = 0
n = 1
# Loop forever. The main function will break the loop.
while True:
# Calculate the next number
nn = np + n
# Yield the previous number and the new one.
yield n, nn
# Update the generator state.
np = n
n = nn
def product_fib(prod):
# Loop through the generator.
for f_0, f_1 in fib():
# If the product is larger or equal to the product return.
if f_0 * f_1 >= prod:
# The last element in the list is the resut of the equality check.
return [f_0, f_1, f_0 * f_1 == prod]
t0 = perf_counter()
res = productFib(8000000000)
t = perf_counter() - t0
print("Original:", t, res)
t0 = perf_counter()
res = product_fib(8000000000) # 8000000000
t = perf_counter() - t0
print("New:", t, res)
这个的输出是
Original: 0.8113621789962053 [75025, 121393, False]
New: 1.3276992831379175e-05 [75025, 121393, False]
编辑
如果你想要单行。它有效，但不要使用它，它不是真正最实用的解决方案。无论如何第一个更快。
print((lambda prod: (lambda n: next(([a, b, (a * b) == prod] for a, b in ([n.append(n[0] + n[1]), n.pop(0), n][-1] for _ in iter(int, 1)) if (a * b) >= prod)))([0, 1]))(714))
def productFib(prod):
a, b = 0, 1
while prod > a * b:
a, b = b, a + b
return [a, b, prod == a * b]
这里有几个不同的算法，它们的优化程度越来越高（从原始算法开始）。
算法 3 使用带缓存的迭代斐波那契 以及猜测平方根（它应该在斐波那契乘积的两个倍数之间。
计时结果：
Original algorithm: 4.43634369118898
Algorithm 2 (recursive fib): 1.5160450420565503
Algorithm 2 (iter fib): 0.03543769357344395
Algorithm 2 (iter fib + caching): 0.013537414072276377
Algorithm 3 (iter fib + caching + guessing): 0.0017255337946799898
设置：
import timeit
from random import randint
from math import sqrt
from bisect import bisect
cache = [0, 1]
第 N 斐波那契数算法：
def f(n):
"""Recursive solution: O(2^n)"""
if n == 0:
return 0
if n == 1:
return 1
return f(n-2) + f(n-1)
def ff(n):
"""Iterative solution: O(n)"""
a, b = 0, 1
for _ in range(0, n):
a, b = b, a + b
return a
def fff(n):
"""Iterative solution + caching"""
length = len(cache)
if n >= length:
for i in range(length, n+1):
cache.append(cache[i-1] + cache[i-2])
return cache[n]
斐波那契乘积算法：
def pf1(prod):
"""Original algorithm."""
i=1
final1 = 0
final2 = 0
while(f(i)*f(i+1) != prod and f(i)*f(i+1) < prod):
i += 1
final1 = f(i)
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]
def pf2(prod, fib_func):
"""Algorithm 2.
Removes extra logic and duplicate function calls."""
i = 1
guess = 0
while guess < prod:
final1 = fib_func(i)
final2 = fib_func(i + 1)
guess = final1 * final2
i += 1
return [final1, final2, guess == prod]
def pf3(prod, fib_func):
"""Algorithm 3.
Implements square root as a guess."""
guess = sqrt(prod) # Numbers will be near square root
i = 2
while cache[-1] < guess:
fff(i)
i += 1
insertion_spot = bisect(cache, guess)
test1 = cache[insertion_spot-1]
test2 = cache[insertion_spot]
return [test1, test2, (test1 * test2) == prod]
测试与输出：
prods = [randint(3, 99999) for _ in range(1000)] # 1000 random products
print("Original algorithm: ", timeit.timeit("for prod in prods: pf1(prod)", number=1, setup="from __main__ import pf1, prods"))
print("Algorithm 2 (recursive fib): ", timeit.timeit("for prod in prods: pf2(prod, f)", number=1, setup="from __main__ import pf2, prods, f"))
print("Algorithm 2 (iter fib): ", timeit.timeit("for prod in prods: pf2(prod, ff)", number=1, setup="from __main__ import pf2, prods, ff"))
print("Algorithm 2 (iter fib + caching): ", timeit.timeit("for prod in prods: pf2(prod, fff)", number=1, setup="from __main__ import pf2, prods, fff"))
print("Algorithm 3 (iter fib + caching + guessing):", timeit.timeit("for prod in prods: pf3(prod, fff)", number=1, setup="from __main__ import pf3, prods, fff, cache; cache = [0, 1]"))
Python"List"对象的有用时间复杂度：https://wiki.python.org/moin/TimeComplexity
两种方式：慢速方式和快速方式
慢：
def productFib(prod):
i=0
final1 = f(i)
final2 = f(i+1)
while(final1 * final2 < prod):
i += 1
final1 = final2 #this is the same as final1 = f(i) again but, the value is already in memory no need to recalc it
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False] #if non equivilant product
def f(i): #fib(0) == 0 fib(1) == 1
if i == 0 :
return 0
if i == 1 :
return 1
return f(i-2) + f(i-1)
while 循环中产品的输出：
0
1个
2个
6个
15
快：
def productFib(prod):
a, b = 0, 1
while prod > a * b:
1. List item
a, b = b, a + b #a is equal to b and b is equal to the sum of a and b
return [a, b, prod == a * b] #return a and b as well as the conditional if a times b is equal to the product
你不需要检查这里是否有 fib 系列的一部分，因为我们可以简单地在 while 循环中迭代系列，而不必递归调用另一个函数
fib 函数定义为：F(n) = F(n-1) + F(n-2)，其中 F(0) = 0 且 F(1) = 1。因此，您可以使用以下算法生成此函数上面的 while 循环
接着 a = 0, b = 1 接下来 a = 1, b = 1 接下来 a = 1, b = 2 接下来 a = 2, b = 3
接下来 a = 3, b = 5 ...
我的作业：
Given a number, say prod (for product), we search two Fibonacci numbers F(n) and F(n+1) verifying
F(n) * F(n+1) = prod if F(n) * F(n+1) = prodYour function productFib takes an integer (prod) and returns an array:
[F(n), F(n+1), True] elseF(m) being the smallest one such as F(m) * F(m+1) > prod
[F(m), F(m+1), False]Examples:
productFib(714) # should return [21, 34, True], # since F(8) = 21, F(9) = 34 and 714 = 21 * 34 productFib(800) # should return [34, 55, False], # since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
我的代码：
def f(i):
if i == 0 :
return 0
if i == 1 :
return 1
return f(i-2) + f(i-1)
def productFib(prod):
i=1
final1 = 0
final2 = 0
while(f(i)*f(i+1) != prod and f(i)*f(i+1) < prod):
i += 1
final1 = f(i)
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]
我是编程新手；这对于大量运行非常慢。如何降低时间复杂度？
您的 fib 函数每次都从底部重新计算。您应该保存您已经知道的值。我的 python 生锈了，但我认为这样做就可以了：
dict = {}
def f(i):
if dict.has_key(i):
return dict[i]
if i == 0 :
return 0
if i == 1 :
return 1
sum = f(i-2) + f(i-1)
dict[i] = sum
return sum
def productFib(prod):
i=1
final1 = 0
final2 = 0
while(f(i)*f(i+1) != prod and f(i)*f(i+1) < prod):
i += 1
final1 = f(i)
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]
首先，您的 f 函数非常耗时：它计算 f(n) for low n 多次。 Memoize功能：将结果保存在一个列表中，再次计算时只需参考该列表即可。
memo = [1, 1]
def f(i):
global memo
if i >= len(memo):
# Compute all f(k) where k < i
f_of_i = f(i-2) + f(i-1)
memo.append(f_of_i)
return memo[i]
请注意，此序列仍然需要您按数字顺序填写 memo：f(i-2) 在 f(i- 1), 两者都在将 f(i) 添加到列表之前被调用。
用这个 returns 立即调用 f(100000000000000) (10^14)。我还没有尝试过更高的数字。
更新
我运行它以10的幂递增。在10^1650时，它还在全速打印输出，我打断了运行。
改进
通过直接从闭式方程计算 f(i)，您可以做得更好（对于许多应用程序）：
root5 = 5 ** 0.5
phi = (1 + root5) / 2
psi = (1 - root5) / 2
def f(i):
return int(round((phi ** i - psi ** i) / root5))
更多改进
直接计算i的正确值。
f(i) * f(i+1) 非常接近 phi**(2i+1) / 5。
def productFib(prod):
power = math.log(prod*5) / log_phi
i = int(round(power-1, 7)/2) + 1
low = f(i)
high = f(i+1)
# print i, low, high
answer = [low, high, low*high == prod]
return answer
print productFib(714)
print productFib(800)
print productFib(100000000000000000)
输出：
[21, 34, True]
[34, 55, False]
[267914296, 433494437, False]
您可以将以下代码用于您的 ProductFib 函数
def productFib2(prod):
i=0
final1 = f(i)
final2 = f(i+1)
while(final1 * final2 < prod):
i += 1
final1 = final2
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]
您可以通过使用生成器大大提高性能。
def fib():
# Generator that yields the last two fibonacci numbers on each iteration.
# Initialize
np = 0
n = 1
# Loop forever. The main function will break the loop.
while True:
# Calculate the next number
nn = np + n
# Yield the previous number and the new one.
yield n, nn
# Update the generator state.
np = n
n = nn
def product_fib(prod):
# Loop through the generator.
for f_0, f_1 in fib():
# If the product is larger or equal to the product return.
if f_0 * f_1 >= prod:
# The last element in the list is the resut of the equality check.
return [f_0, f_1, f_0 * f_1 == prod]
t0 = perf_counter()
res = productFib(8000000000)
t = perf_counter() - t0
print("Original:", t, res)
t0 = perf_counter()
res = product_fib(8000000000) # 8000000000
t = perf_counter() - t0
print("New:", t, res)
这个的输出是
Original: 0.8113621789962053 [75025, 121393, False]
New: 1.3276992831379175e-05 [75025, 121393, False]
编辑
如果你想要单行。它有效，但不要使用它，它不是真正最实用的解决方案。无论如何第一个更快。
print((lambda prod: (lambda n: next(([a, b, (a * b) == prod] for a, b in ([n.append(n[0] + n[1]), n.pop(0), n][-1] for _ in iter(int, 1)) if (a * b) >= prod)))([0, 1]))(714))
def productFib(prod):
a, b = 0, 1
while prod > a * b:
a, b = b, a + b
return [a, b, prod == a * b]
这里有几个不同的算法，它们的优化程度越来越高（从原始算法开始）。
算法 3 使用带缓存的迭代斐波那契 以及猜测平方根（它应该在斐波那契乘积的两个倍数之间。
计时结果：
Original algorithm: 4.43634369118898
Algorithm 2 (recursive fib): 1.5160450420565503
Algorithm 2 (iter fib): 0.03543769357344395
Algorithm 2 (iter fib + caching): 0.013537414072276377
Algorithm 3 (iter fib + caching + guessing): 0.0017255337946799898
设置：
import timeit
from random import randint
from math import sqrt
from bisect import bisect
cache = [0, 1]
第 N 斐波那契数算法：
def f(n):
"""Recursive solution: O(2^n)"""
if n == 0:
return 0
if n == 1:
return 1
return f(n-2) + f(n-1)
def ff(n):
"""Iterative solution: O(n)"""
a, b = 0, 1
for _ in range(0, n):
a, b = b, a + b
return a
def fff(n):
"""Iterative solution + caching"""
length = len(cache)
if n >= length:
for i in range(length, n+1):
cache.append(cache[i-1] + cache[i-2])
return cache[n]
斐波那契乘积算法：
def pf1(prod):
"""Original algorithm."""
i=1
final1 = 0
final2 = 0
while(f(i)*f(i+1) != prod and f(i)*f(i+1) < prod):
i += 1
final1 = f(i)
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False]
def pf2(prod, fib_func):
"""Algorithm 2.
Removes extra logic and duplicate function calls."""
i = 1
guess = 0
while guess < prod:
final1 = fib_func(i)
final2 = fib_func(i + 1)
guess = final1 * final2
i += 1
return [final1, final2, guess == prod]
def pf3(prod, fib_func):
"""Algorithm 3.
Implements square root as a guess."""
guess = sqrt(prod) # Numbers will be near square root
i = 2
while cache[-1] < guess:
fff(i)
i += 1
insertion_spot = bisect(cache, guess)
test1 = cache[insertion_spot-1]
test2 = cache[insertion_spot]
return [test1, test2, (test1 * test2) == prod]
测试与输出：
prods = [randint(3, 99999) for _ in range(1000)] # 1000 random products
print("Original algorithm: ", timeit.timeit("for prod in prods: pf1(prod)", number=1, setup="from __main__ import pf1, prods"))
print("Algorithm 2 (recursive fib): ", timeit.timeit("for prod in prods: pf2(prod, f)", number=1, setup="from __main__ import pf2, prods, f"))
print("Algorithm 2 (iter fib): ", timeit.timeit("for prod in prods: pf2(prod, ff)", number=1, setup="from __main__ import pf2, prods, ff"))
print("Algorithm 2 (iter fib + caching): ", timeit.timeit("for prod in prods: pf2(prod, fff)", number=1, setup="from __main__ import pf2, prods, fff"))
print("Algorithm 3 (iter fib + caching + guessing):", timeit.timeit("for prod in prods: pf3(prod, fff)", number=1, setup="from __main__ import pf3, prods, fff, cache; cache = [0, 1]"))
Python"List"对象的有用时间复杂度：https://wiki.python.org/moin/TimeComplexity
两种方式：慢速方式和快速方式
慢：
def productFib(prod):
i=0
final1 = f(i)
final2 = f(i+1)
while(final1 * final2 < prod):
i += 1
final1 = final2 #this is the same as final1 = f(i) again but, the value is already in memory no need to recalc it
final2 = f(i+1)
if(final1*final2 == prod):
return [final1,final2,True]
else:
return [final1,final2,False] #if non equivilant product
def f(i): #fib(0) == 0 fib(1) == 1
if i == 0 :
return 0
if i == 1 :
return 1
return f(i-2) + f(i-1)
while 循环中产品的输出： 0 1个 2个 6个 15
快：
def productFib(prod):
a, b = 0, 1
while prod > a * b:
1. List item
a, b = b, a + b #a is equal to b and b is equal to the sum of a and b
return [a, b, prod == a * b] #return a and b as well as the conditional if a times b is equal to the product
你不需要检查这里是否有 fib 系列的一部分，因为我们可以简单地在 while 循环中迭代系列，而不必递归调用另一个函数 fib 函数定义为：F(n) = F(n-1) + F(n-2)，其中 F(0) = 0 且 F(1) = 1。因此，您可以使用以下算法生成此函数上面的 while 循环 接着 a = 0, b = 1 接下来 a = 1, b = 1 接下来 a = 1, b = 2 接下来 a = 2, b = 3 接下来 a = 3, b = 5 ...