Ruby algorithme de Fibonacci

Voici une méthode que j'ai écrit pour calculer une valeur dans la séquence de Fibonacci:

def fib(n)

    if n == 0
        return 0
    end
    if n == 1
        return 1
    end

    if n >= 2
        return fib(n-1) + (fib(n-2))
    end

end

Il fonctionne uptil n = 14, mais après que je reçois un message disant que le programme est trop long à répondre (je suis en utilisant repl.c'). Quelqu'un sait pourquoi ce qui se passe?

eh bien, avez-vous d'utiliser une fonction récursive? Je pense que votre programme de débordements.

OriginalL'auteur user3769323 | 2014-06-26

  1. 21

    Naïf de fibonacci fait beaucoup de répéter les calculs en fib(14) fib(4) est calculé plusieurs fois.

    Vous pouvez ajouter memoization de votre algorithme pour le rendre beaucoup plus rapide:

    def fib(n, memo = {})
  if n == 0 || n == 1
    return n
  end
  memo[n] ||= fib(n-1, memo) + fib(n-2, memo)
end
fib 14
# => 377
fib 24
# => 46368
fib 124
# => 36726740705505779255899443
    J'ai rêvé que et Ruby la rend possible.
    Très élégant, beau travail.
    de ce qu'on appelle en cache pas, mais au lieu memoization

    OriginalL'auteur Uri Agassi

  2. 9

    Comme d'autres l'ont souligné, la mise en œuvre de la course du temps, croît de façon exponentielle dans n. Il y a beaucoup plus propres implémentations.

    Constructive [O(n) temps d'exécution O(1) de stockage]:

    def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  new, old = 1, 0
  n.times {new, old = new + old, new}
  old
end

    Memoized la récursivité [O(n) temps d'exécution O(n) de stockage]:

    def fib_memo(n, memo)
  memo[n] ||= fib_memo(n-1, memo) + fib_memo(n-2, memo)
end

def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  fib_memo(n, [0, 1])
end

    Récursive des puissances d'une matrice de multiplication à l'aide de carrés la réduction de moitié de la puissance pour quand tu dois juste savoir vraiment grand factorielles comme 1_000_000.fib [O(log n) temps d'exécution et de stockage (sur pile)]:

    def matrix_fib(n)
  if n == 1
    [0,1]
  else
    f = matrix_fib(n/2)
    c = f[0] * f[0] + f[1] * f[1]
    d = f[1] * (f[1] + 2 * f[0])
    n.even? ? [c,d] : [d,c+d]
  end
end

def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  n.zero? ? n : matrix_fib(n)[1]
end

    OriginalL'auteur pjs

  3. 3

    Votre programme a exponentielle d'exécution en raison de la récursivité vous utilisez.

    Développer seulement les appels récursifs quelques niveaux pour vous montrer pourquoi: 

    fib(14) = fib(13) + fib(12)
        = (fib(12) + fib(11)) + (fib(11) + fib (10))
        = (((fib(11) + fib(10)) + (fib(10) + fib(9))) (((fib(10) + fib(9)) + (fib(9) + fib(8)))
        = ... //a ton more calls

    La terrible exécution pourrait être à l'origine de votre blocage de programme, comme l'augmentation de fib(n) par 1 signifie que vous avez une TONNE plus d'appels récursifs

    OriginalL'auteur Kevin L

  4. 2

    votre programme de débordements que Kevin L'a expliqué.

    au lieu de cela, vous pouvez utiliser un algorithme itératif comme ceci:

    def fib (n)
  return 0 if n == 0

  x = 0
  y = 1

  (1..n).each do
    z = (x + y)
    x = y
    y = z
  end

  return y
end

(0..14).map { |n| fib(n) }
# [0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
    Votre code n'est pas exécuté par le façon, il ne devrait pas être un end après la if avant la else, et range n'est pas valide non plus. Je vais modifier votre code pour le faire fonctionner, revenir en arrière et ajuster si vous êtes en désaccord.
    eh bien, j'ai juste écrit avec une tête endormie, je vous serais reconnaissant de le modifier.

    OriginalL'auteur sertsedat

  5. 1

    J'ai essayé de comparer le temps d'exécution des deux méthodes de fibonacci sur repl.il

    require 'benchmark'

def fib_memo(n, memo = {})
  if n == 0 || n == 1
    return n
  end
  memo[n] ||= fib_memo(n-1, memo) + fib_memo(n-2, memo)
end


def fib_naive(n)
  if n == 0 || n == 1
    return n
  end
  fib_naive(n-1) + fib_naive(n-2)
end

def time(&block) 
  puts Benchmark.measure(&block) 
end

time {fib_memo(14)}
time {fib_naive(14)}

    Sortie

    0.000000   0.000000   0.000000 (  0.000008)
0.000000   0.000000   0.000000 (  0.000099)

    Comme vous pouvez le voir, le moteur d'exécution est tout à fait différent. @Uri Agassi a suggéré, l'utilisation memoization. Le concept est expliqué assez bien ici https://stackoverflow.com/a/1988826/5256509

    OriginalL'auteur Hanmaslah