Возвращаемые значения не работают должным образом в Ruby в программе, которая решает последовательность Фибоначчи с помощью динамического программирования

Question

Я новичок в ruby, поэтому, возможно, здесь я делаю очень новичок, но попробовал поискать в Google и не смог выяснить причину, по которой этот код демонстрирует странное поведение.Этот код очень прост и использует базовое динамическое программирование для хранения промежуточного результата в Hash, поэтому он используется позже для ускорения вычислений.

$existingSequence = {0 => 1, 1 => 2}


def fib(n)
  if $existingSequence.has_key? n
    return $existingSequence.values_at n;
  end

  if n == 0
    return 1;
  elsif n == 1
    return 2;
  end

  $existingSequence[n] = fib(n - 1) + fib(n - 2)
  return $existingSequence[n];
end

n = fib(2)
puts n

Я ожидаю, что этот код выведет 3, так как это делает вызовк fib (1) и fib (0), которые возвращают 2 и 1 соответственно, а затем добавляются к 3. Но результат равен 1 и 2.

Answer 1

Немного не по теме, вот забавный способ сделать по сути то же самое, но с использованием механизма значений по умолчанию Hash, чтобы использовать Hash не только для кэширования, но и для вычисления значений:

fibs = { 0 => 0, 1 => 1 }.tap do |fibs|
  fibs.default_proc = ->(fibs, n) { fibs[n] = fibs[n-1] + fibs[n-2] }
end

fibs[9]
# => 34

Примечание: я не придумал это сам, я украл его у здесь .

Answer 2

Hash.values_at возвращает массив, поэтому, когда код выполняет fib(1) + fib(0), он объединяет массивы [2] и [1] вместе, что приводит к ответу [2, 1].Вместо:

return $existingSequence.values_at n;

... вы должны сделать это вместо:

return $existingSequence[n]

Кстати, последовательность Фибоначчи традиционно начинается с 0 и 1, а не с 1 и 2.

Answer 3

Вторая строка fib должна гласить:

return $existingSequence[n]

вместо

return $existingSequence.values_at n

Добавьте puts $existingSequence в конец файла, чтобы увидеть разницу.