Ruby Fibonacci算法 [英] Ruby Fibonacci algorithm
本文介绍了Ruby Fibonacci算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
以下是我编写的用于计算斐波那契数列中的值的方法:
The following is a method I wrote to calculate a value in the Fibonacci sequence:
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
它可以一直工作到n = 14,但是之后我收到一条消息,说该程序花费了太长时间来响应(我正在使用repl.it).有人知道为什么会这样吗?
It works uptil n = 14, but after that I get a message saying the program is taking too long to respond (I'm using repl.it). Anyone know why this is happening?
推荐答案
天真斐波那契进行了大量重复计算-在fib(14)
fib(4)
中进行了多次计算.
Naive fibonacci makes a lot of repeat calculations - in fib(14)
fib(4)
is calculated many times.
您可以将备忘录添加到算法中以使其更快:
You can add memoization to your algorithm to make it a lot faster:
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
这篇关于Ruby Fibonacci算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文