CodeWars打卡（11）

Details:

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.

example:

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

中文大概含义:

看例程秒懂~~

我自己的代码如下:

"""1.0.0版本"""
def Fib_value(num):
    return Fib_value(num-1)+Fib_value(num-2) if num>1 else [0,1][num]

def productFib(prod):
    # your code
    num = 0
    while True:
        a = [Fib_value(num),Fib_value(num+1)]
        if a[0]*a[1]>=prod:
            return [a[0],a[1],a[0]*a[1]==prod]
        num+=1
"""2.0.0版本"""
def productFib(prod):
    # your code
    num = 1
    a=[0,1]
    while True:
        if a[0]*a[1]>=prod:
            return [a[0],a[1],a[0]*a[1]==prod]
        a[0] = a[0] + a[1]
        a = a[::-1]

第一名代码:

def productFib(prod):
  a, b = 0, 1
  while prod > a * b:
    a, b = b, a + b
  return [a, b, prod == a * b]

第四名代码:

def productFib(prod):
    a,b = 0,1
    while a*b < prod:
        a,b = b, b+a
    return [a, b, a*b == prod]

1. 第一名代码和我的2.0.0版本的代码基本一样的,细节处理他的比我代码好太多,不愧是大佬..
2. 第二名和后面的代码都类似了
3. 我的代码1.0.0版本属于常规做法,但是系统显示time out.可能效率太低了,但是实用性和可以移植性好很多,

• 这道题难度系数五级
• 天外有天,人外有人~~