Description

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(n) verifying F(n) * F(n+1) = prodyou will return

[F(n), F(n+1), false] or {F(n), F(n+1), 0} or (F(n), F(n+1), False)

F(n) being the smallest one such as F(n) * F(n+1) > prod.

Some Examples of Return: (depend on the language)

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
-----
productFib(714) # should return [21, 34, true], 
productFib(800) # should return [34, 55, false], 
-----
productFib(714) # should return {21, 34, 1}, 
productFib(800) # should return {34, 55, 0},        
-----
productFib(714) # should return {21, 34, true}, 
productFib(800) # should return {34, 55, false},

Solutions

Julia

using Test


##########################################
# 解法一
##########################################

function product_fib1(prod)
    a, b = big(0), big(1)
    while a * b < prod
        a, b = b, a + b
    end
    return (a, b, a * b == prod)
end
#> product_fib1 (generic function with 1 method)

@test product_fib1(5456077604922913920) == (2971215073, 4807526976, false)
#> Test Passed
#>   Expression: product_fib1(5456077604922913920) == (2971215073, 4807526976, false)
#>    Evaluated: (2971215073, 4807526976, false) == (2971215073, 4807526976, false)


##########################################
# 解法二
##########################################

const M_Fibonacci = [0 1; 1 1]
#> 2×2 Matrix{Int64}:
#>  0  1
#>  1  1

function fib2(n::Int64)::Tuple{Int64,Int64}
    aₙ, aₙ₊₁ = M_Fibonacci^n * [0, 1]
    return aₙ, aₙ₊₁
end
#> fib2 (generic function with 1 method)

function product_fib2(prod::Integer)::Tuple{Int64,Int64,Bool}
    k = 1
    while true
        a, b = fib2(k) .|> big
        @show a * b
        a * b == prod && return (a, b, true)
        a * b > prod && return (a, b, false)
        k += 1
    end
end
#> product_fib2 (generic function with 1 method)

@test product_fib2(5456077604922913920) == (2971215073, 4807526976, false)
#> a * b = 1
#> a * b = 2
#> a * b = 6
#> a * b = 15
#> a * b = 40
#> a * b = 104
#> a * b = 273
#> a * b = 714
#> a * b = 1870
#> a * b = 4895
#> a * b = 12816
#> a * b = 33552
#> a * b = 87841
#> a * b = 229970
#> a * b = 602070
#> a * b = 1576239
#> a * b = 4126648
#> a * b = 10803704
#> a * b = 28284465
#> a * b = 74049690
#> a * b = 193864606
#> a * b = 507544127
#> a * b = 1328767776
#> a * b = 3478759200
#> a * b = 9107509825
#> a * b = 23843770274
#> a * b = 62423800998
#> a * b = 163427632719
#> a * b = 427859097160
#> a * b = 1120149658760
#> a * b = 2932589879121
#> a * b = 7677619978602
#> a * b = 20100270056686
#> a * b = 52623190191455
#> a * b = 137769300517680
#> a * b = 360684711361584
#> a * b = 944284833567073
#> a * b = 2472169789339634
#> a * b = 6472224534451830
#> a * b = 16944503814015855
#> a * b = 44361286907595736
#> a * b = 116139356908771352
#> a * b = 304056783818718321
#> a * b = 796030994547383610
#> a * b = 2084036199823432510
#> a * b = 5456077604922913919
#> a * b = 14284196614945309248
#> Test Passed
#>   Expression: product_fib2(5456077604922913920) == (2971215073, 4807526976, false)
#>    Evaluated: (2971215073, 4807526976, false) == (2971215073, 4807526976, false)