在 R 中使用动态规划计算斐波那契

Question

我尝试编写一个函数来计算 R 中的第 n 个斐波纳契数。我可以递归地执行此操作。

fibonacci = function(n){
  if (n == 1) {return(1)}
  if (n == 2) {return(2)}

  return(fibonacci(n - 1) + fibonacci(n - 2))
}

我在 R 中找不到任何示例，但从其他语言的指南中我想到了以下内容。然而它似乎并没有运行更快。

fibonacci = function(n, lookup = NULL){
  if (is.null(lookup)) {
    lookup = integer(n + 1)
  }


  if (n == 1) {return(1)}
  if (n == 2) {return(2)}

  lookup[1] = 1
  lookup[2] = 2

  if (lookup[n - 1] == 0) {
    lookup[n - 1] = fibonacci(n - 1, lookup)
  }

  if (lookup[n - 2] == 0) {
    lookup[n - 2] = fibonacci(n - 2, lookup)
  }
  return(lookup[n - 1] + lookup[n - 2])
}

Answer 1

您的解决方案的问题在于您的查找向量始终位于调用框架环境的本地，并且新的解决方案不会传播到调用方，即当函数 returns.为了使持久变量成为 C 中的静态变量，您可以为充当记忆器的函数创建一个属性。这是一种解决方案：

fibonaccid = function(n, init=T){
  if (init) {
    lookup <- integer(n + 1)
    lookup[1] <- 1
    lookup[2] <- 2
  } else {
    lookup <- attr(fibonaccid, ".lookup")
  }

  # ... calculate lookup as before, recurse with fibonaccid(...,init=F)

  attr(fibonaccid, ".lookup") <<- lookup

  return(lookup[n - 1] + lookup[n - 2])
}

这确实运行得更快：

R> system.time(print(fibonacci(35)))
[1] 14930352
   user  system elapsed
  20.923  0.140  21.446

R> system.time(print(fibonaccid(35)))
[1] 14930352
   user  system elapsed
  0.202   0.006   0.209

有关详细信息，请参阅 this post。

在 R 中使用动态规划计算斐波那契

In R calculate fibonnaci using dynamic programing

recursion

r

dynamic-programming

fibonacci