题目

  • Product of consecutive Fib numbers
    连续Fib数的乘积

描述

  • The Fibonacci numbers are the numbers in the following integer sequence (Fn):
    斐波那契数是以下整数序列（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：
    给定一个数字，比如prod（对于乘积），我们搜索两个斐波那契数F（n）和F（n+1）
  • F(n) * F(n+1) = prod.
  • Your function productFib takes an integer (prod) and returns an array:
    函数productFib接受一个整数（prod）并返回一个数组：
  • [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）=prod，则取决于语言。
    如果您没有找到两个连续的F（n）验证F（n）*F（n+1）=prod，您将返回：
  • [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.
    F（n）是最小的，如F（n）*F（n+1）>prod。

例子

  • productFib(714) # should return (21, 34, true),
  • productFib(800) # should return (34, 55, false),
  • 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},

思路

  • 首先，看到斐波那契数列，就要想到动态规划，所以对于本题来说关键是计算斐波那契数，但是本题和一般求斐波那契数列不一样，这里只需要两个连续的斐波那契数，所以我们的dp数组大小为2即可，每次保存最新的斐波那契数，减少内存
  • 然后得到两个斐波那契数，将这两个数相乘和传入参数对比即可

递归五部曲：

  1. dp数组及其下标的含义

dp[1]:dp[0]和dp[1]分别代表最新的两个斐波那契数

  1. 确定递推公式

val = dp[0] + dp[1]
dp[0] = dp[1]
dp[1] = val

  1. dp初始化

dp[0] = 0,dp[1] = 1

  1. 递归顺序

从左到右即可

  1. 举例

自行

完整代码

def productFib(prod):
    # dp数组
    dp = [0] * 2
    # 初始哈
    dp[0] = 0
    dp[1] = 1
    # 遍历
    while True:
        # 和传入参数进行对比，如果等于就返回Ture，如果大于就返回False，如果小于就动规
        if prod == dp[0] * dp[1]:
            dp.append(True)
            return dp
        elif prod > dp[0] * dp[1]:
            val = dp[0] + dp[1]
            dp[0] = dp[1]
            dp[1] = val
        elif prod < dp[0] * dp[1]:
            dp.append(False)
            return dp