В R вычисляют фибоначчи с помощью динамического программирования - PullRequest
Новая
       39

В R вычисляют фибоначчи с помощью динамического программирования

0 голосов
/ 06 февраля 2019

Я пытался написать функцию для вычисления n-го числа Фибоначчи в R. Я могу сделать это рекурсивно. 

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])
}

1 Ответ

0 голосов
/ 06 февраля 2019

Проблема с вашим решением состоит в том, что ваш вектор поиска всегда является локальным для среды фрейма вызова, и новые решения не распространяются вплоть до вызывающих, то есть изменения вектора поиска теряются при возврате функции.Чтобы сделать постоянную переменную а-ля статической переменной в 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

См. этот пост для получения дополнительной информации.

...