Product of consecutive Fib numbers
Codewars Kata 11√
Description
Link: productFib
-简述：本题给定一个数字，问它是哪两个fibonacci数字的乘积
-思路：已知fibonacci数字是如何得到的，根据其进行求解
-难点：while循环简便
The Fibonacci numbers are the numbers in the following integer sequence (Fn):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …
such as
F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
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.
Your function productFib takes an integer (prod) and returns an array:
[F(n), F(n+1), true] or {F(n), F(n+1), 1} or (F(n), F(n+1), True) depending on the language if F(n) * F(n+1) = prod.
If you don’t find two consecutive F(m) verifying F(m) * F(m+1) = prodyou will return
[F(m), F(m+1), false] or {F(n), F(n+1), 0} or (F(n), F(n+1), False) F(m) being the smallest one such as F(m) * F(m+1) > prod.
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 Notes: Not useful here but we can tell how to choose the number n up to which to go: we can use the “golden ratio” phi which is (1 + sqrt(5))/2 knowing that F(n) is asymptotic to: phi^n / sqrt(5). That gives a possible upper bound to n.
You can see examples in “Example test”.
References
http://en.wikipedia.org/wiki/Fibonacci_number
http://oeis.org/A000045
My solution
def productFib(prod):
a = [0,1,1]
b = [0,1,2]
for i in range(2,100):
a[i]=a[i-1]+a[i-2]
a.append(a[i])
i+=1
for j in range(2,100):
b[j]=a[j]*a[j+1]
b.append(b[j])
j+=1
for x in range(0,100):
if prod - b[x] == 0:
return [a[x],a[x+1],True]
else:
x+=1
if prod != b[x]:
for y in range(0, 100):
if prod > b[y] and prod < b[y + 1]:
if prod - b[y] > prod - b[y + 1]:
return [a[y + 1], a[y + 2], False]
elif prod - b[y] < prod - b[y + 1]:
return [a[y], a[y + 1], False]
else:
y += 1
Given solution
def productFib(prod):
a, b = 0, 1
while prod > a * b:
a, b = b, a + b
return [a, b, prod == a * b]
↑↑↑while循环，非常巧妙了
今日心得：心态崩了…答案也太简洁了…我想得好复杂_(:з」∠)_
Points
1 while循环直接求解
