Ruby 中的斐波那契数列（递归）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12178642/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fibonacci sequence in Ruby (recursion)
提问by Maputo
I'm trying to implement the following function, but it keeps giving me the stack level too deep (SystemStackError)error.
我正在尝试实现以下功能，但它一直给我stack level too deep (SystemStackError)错误。
Any ideas what the problem might be ?
任何想法可能是什么问题？
def fibonacci( n )
[ n ] if ( 0..1 ).include? n
( fibonacci( n - 1 ) + fibonacci( n - 2 ) ) if n > 1
end
puts fibonacci( 5 )
回答by Pritesh Jain
Try this
尝试这个
def fibonacci( n )
return n if ( 0..1 ).include? n
( fibonacci( n - 1 ) + fibonacci( n - 2 ) )
end
puts fibonacci( 5 )
# => 5
check this post too Fibonacci One-Liner
也检查这篇文章Fibonacci One-Liner
and more .. https://web.archive.org/web/20120427224512/http://en.literateprograms.org/Fibonacci_numbers_(Ruby)
还有更多.. https://web.archive.org/web/20120427224512/http://en.literateprograms.org/Fibonacci_numbers_(Ruby)
You have now been bombarded with many solutions :)
您现在已经被许多解决方案轰炸了:)
regarding problem in ur solution
关于你的解决方案中的问题
you should return nif its 0or 1
你应该返回n如果0还是1
and addlast two numbers not last and next
而add最后两个数字不过去和未来
New Modified version
新修改版
def fibonacci( n )
return n if n <= 1
fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55
One liner
一个班轮
def fibonacci(n)
n <= 1 ? n : fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55
回答by Ruben Lopez
Here is something I came up with, I find this more straight forward.
这是我想出的东西，我觉得这更直接。
def fib(n)
n.times.each_with_object([0,1]) { |num, obj| obj << obj[-2] + obj[-1] }
end
fib(10)
回答by Victor Moroz
This is not the way you calculate fibonacci, you are creating huge recursive tree which will fail for relatively small ns. I suggest you do something like this:
这不是您计算斐波那契的方式，您正在创建巨大的递归树，该树对于相对较小的ns会失败。我建议你做这样的事情：
def fib_r(a, b, n)
n == 0 ? a : fib_r(b, a + b, n - 1)
end
def fib(n)
fib_r(0, 1, n)
end
p (0..100).map{ |n| fib(n) }
回答by Bijan
This approach is fast and makes use of memoization:
这种方法很快，并利用了记忆：
fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }
fib[123] # => 22698374052006863956975682
In case you're wondering about how this hash initialization works read here:
如果你想知道这个哈希初始化是如何工作的，请阅读这里：
回答by Dudo
Linear
线性
module Fib
def self.compute(index)
first, second = 0, 1
index.times do
first, second = second, first + second
end
first
end
end
Recursivewith caching
递归缓存
module Fib
@@mem = {}
def self.compute(index)
return index if index <= 1
@@mem[index] ||= compute(index-1) + compute(index-2)
end
end
Closure
关闭
module Fib
def self.compute(index)
f = fibonacci
index.times { f.call }
f.call
end
def self.fibonacci
first, second = 1, 0
Proc.new {
first, second = second, first + second
first
}
end
end
None of these solutions will crash your system if you call Fib.compute(256)
如果您调用，这些解决方案都不会使您的系统崩溃 Fib.compute(256)
回答by iblue
PHI = 1.6180339887498959
TAU = 0.5004471413430931
def fibonacci(n)
(PHI**n + TAU).to_i
end
You don't need recursion.
你不需要递归。
回答by iblue
Recursion's very slow, here's a faster way
递归很慢，这里有一个更快的方法
a = []; a[0] = 1; a[1] = 1
i = 1
while i < 1000000
a[i+1] = (a[i] + a[i-1])%1000000007
i += 1
end
puts a[n]
It's O(1), however you could use matrix exponentiation, here's one of mine's implementation, but it's in java => http://pastebin.com/DgbekCJM, but matrix exp.'s O(8logn) .Here's a much faster algorithm, called fast doubling. Here's a java implementation of fast doubling.
它是 O(1)，但是你可以使用矩阵求幂，这是我的一个实现，但它在 java => http://pastebin.com/DgbekCJM 中，但是矩阵 exp. 的 O(8logn) 。这是一个更快的算法，称为快速加倍。这是快速加倍的java实现。
class FD {
static int mod = 1000000007;
static long fastDoubling(int n) {
if(n <= 2) return 1;
int k = n/2;
long a = fastDoubling(k+1);
long b = fastDoubling(k);
if(n%2 == 1) return (a*a + b*b)%mod;
else return (b*(2*a - b))%mod;
}
Yet, using karatsuba multiplication, both matrix exp. and fast doubling becomes much faster, yet fast doubling beats matrix exp. by a constant factor, well i didn't want to be very thorough here. But i recently did a lot of research on fibonacci numbers and i want my research to be of use to anyone willing to learn, ;).
然而，使用 karatsuba 乘法，两个矩阵 exp。和快速加倍变得更快，但快速加倍击败矩阵 exp。由于一个常数因素，我不想在这里非常彻底。但我最近对斐波那契数进行了大量研究，我希望我的研究对任何愿意学习的人有用，;)。
回答by Peter Prabu
This may help you.
这可能对你有帮助。
def fib_upto(max)
i1, i2 = 1, 1
while i1 <= max
yield i1
i1, i2 = i2, i1+i2
end
end
fib_upto(5) {|f| print f, " "}
回答by mizan rahman
i think this is pretty easy:
我认为这很容易：
def fibo(n) a=0 b=1 for i in 0..n c=a+b print "#{c} " a=b b=c end
end
回答by Rameshwar Vyevhare
We can perform list fibo series using below algorithm
我们可以使用以下算法执行列表 fibo 系列
def fibo(n)
n <= 2 ? 1 : fibo(n-1) + fibo(n-2)
end
We can generate series like below
我们可以生成如下系列
p (1..10).map{|x| fibo(x)}
below is the output of this
下面是这个的输出
=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
