Ruby中的Fibonacci序列（递归）
我正在尝试实现以下函数，但它一直给我的stack level too deep (SystemStackError)错误。
任何想法可能是什么问题？
def fibonacci( n ) [ n ] if ( 0..1 ).include? n ( fibonacci( n - 1 ) + fibonacci( n - 2 ) ) if n > 1 end puts fibonacci( 5 )
试试这个
def fibonacci( n ) return n if ( 0..1 ).include? n ( fibonacci( n - 1 ) + fibonacci( n - 2 ) ) end puts fibonacci( 5 ) # => 5
查看这篇文章太Fibonacci One-Liner
以及更多… https://web.archive.org/web/20120427224512/http://en.literateprograms.org/Fibonacci_numbers_(Ruby）
你现在已被许多解决方案轰炸:)
关于你解决方案中的问题
如果0或1你应该返回n
并add最后两个不是最后和下一个的数字
新修改版
def fibonacci( n ) return n if n <= 1 fibonacci( n - 1 ) + fibonacci( n - 2 ) end puts fibonacci( 10 ) # => 55
一个class轮
def fibonacci(n) n <= 1 ? n : fibonacci( n - 1 ) + fibonacci( n - 2 ) end puts fibonacci( 10 ) # => 55
这是我想出的东西，我发现这更直接。
def fib(n) n.times.each_with_object([0,1]) { |num, obj| obj << obj[-2] + obj[-1] } end fib(10)
这不是你计算斐波纳契的方法，你正在创建一个巨大的递归树，它会因相对较小的n而失败。 我建议你这样做：
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) }
线性
module Fib def self.compute(index) first = 0 second = 1 index.times do third = first + second first = second second = third end first end end
递归缓存
module Fib @@mem = {} def self.compute(index) if index <= 1 return index else @@mem[index] ||= compute(index-1) + compute(index-2) end end end
如果你调用Fib.compute(256) ，这些解决方案都不会崩溃你的系统
递归非常慢，这是一种更快的方法
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]
这是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; }
然而，使用karatsuba乘法，矩阵exp。 并且快速加倍变得快得多，但快速加倍节拍矩阵exp。 通过一个恒定的因素，我不想在这里非常彻底。 但我最近做了很多关于斐波纳契数的研究，我希望我的研究对任何愿意学习的人都有用;）。
PHI = 1.6180339887498959 TAU = 0.5004471413430931 def fibonacci(n) (PHI**n + TAU).to_i end
你不需要递归。
这种方法很快并且使用了memoization：
fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] } fib[123] # => 22698374052006863956975682
如果你想知道这个哈希初始化是如何工作的，请阅读：
这可能对你有所帮助。
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, " "}
我觉得这很简单：
def fibo(n) a=0 b=1 for i in 0..nc=a+b print "#{c} " a=bb=c end end
最快和最小的线路解决方案：
fiby = ->(n, prev, i, count, selfy) { i < count ? (selfy.call n + prev, n, i + 1, count, selfy) : (puts n) } fiby.call 0, 1, 0, 1000, fiby
function自拍图案:)
尝试这个oneliner
def fib (n) n == 0 || n == 1 ? n : fib(n-2) + fib(n-1) end print fib(16)
输出：987
我们可以使用以下算法执行列表fibo系列
def fibo(n) n <= 2 ? 1 : fibo(n-1) + fibo(n-2) end
我们可以生成如下系列
p (1..10).map{|x| fibo(x)}
以下是此输出
=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
如果你想为fib编写最快的function算法，它将不会递归。 这是编写解决方案的function方式较少的几次之一。 因为如果你使用类似的东西，堆栈会重复它自己
fibonacci( n - 1 ) + fibonacci( n - 2 )
最终n-1和n-2将创建相同的数字，因此将在计算中进行重复。 对此最快的方法是iteratvily
def fib(num) # first 5 in the sequence 0,1,1,2,3 fib1 = 1 #3 fib2 = 2 #4 i = 5 #start at 5 or 4 depending on wheather you want to include 0 as the first number while i <= num temp = fib2 fib2 = fib2 + fib1 fib1 = temp i += 1 end p fib2 end fib(500)
另一种利用memoization计算斐波那契数的方法：
$FIB_ARRAY = [0,1] def fib(n) return n if $FIB_ARRAY.include? n ($FIB_ARRAY[n-1] ||= fib(n-1)) + ($FIB_ARRAY[n-2] ||= fib(n-2)) end
这确保了每个斐波那契数只被计算一次，大大减少了对fib方法的调用次数。
a = [1, 1] while(a.length < max) do a << a.last(2).inject(:+) end
这将填充系列。 （当max <2时你必须考虑这种情况）
如果只需要第n个元素，则可以使用Hash.new
fib = Hash.new {|hsh, i| hsh[i] = fib[i-2] + fib[i-1]}.update(0 => 0, 1 => 1) fib[10] # => 55
这是一个构建查找表的更简洁的解决方案：
fibonacci = Hash.new do |hash, key| if key <= 1 hash[key] = key else hash[key] = hash[key - 1] + hash[key - 2] end end fibonacci[10] # => 55 fibonacci # => {1=>1, 0=>0, 2=>1, 3=>2, 4=>3, 5=>5, 6=>8, 7=>13, 8=>21, 9=>34, 10=>55}
今天有人问我类似的东西，但他想得到一个给定数字的斐波那契序列数组。 例如，
fibo(5) => [0, 1, 1, 2, 3, 5] fibo(8) => [0, 1, 1, 2, 3, 5, 8] fibo(13) => [0, 1, 1, 2, 3, 5, 8, 13] # And so on...
这是我的解决方案。 它没有使用递归。 如果你正在寻找类似的东西，还有一个解决方案：P
def fibo(n) seed = [0, 1] n.zero? ? [0] : seed.each{|i| i + seed[-1] > n ? seed : seed.push(i + seed[-1])} end
这是Scala中的一个：
object Fib { def fib(n: Int) { var a = 1: Int var b = 0: Int var i = 0: Int var f = 0: Int while(i < n) { println(s"f(${i+1}) -> $f") f = a+b a = b b = f i += 1 } } def main(args: Array[String]) { fib(10) } }
我认为这是最好的答案 ，这是另一个SOpost提出类似问题的回复。
PriteshJ在这里接受的回答是使用天真的斐波纳契递归，这很好，但是一旦超过第40个元素就会变得非常慢。 如果您缓存/记忆先前的值并在递归迭代时传递它们，则会快得多。
已经有一段时间了，但你可以编写一个相当优雅和简单的单行function：
def fib(n) n > 1 ? fib(n-1) + fib(n-2) : n end
这是我用来解决URI Online Judge编程挑战的片段，希望它有所帮助。
def fib(n) if n == 1 puts 0 else fib = [0,1] (n-2).times do fib << fib[-1] + fib[-2] end puts fib.join(' ') end end fib(45)
它输出
# => 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733
加入斐波纳契火车：
定期：
def fib(num) return num if (num < 2) else fib(num-1) + fib(num-2) end
使用缓存：
module Fib @fibs = [0,1] def self.calc(num) return num if (num < 2) else @fibs[num] ||= self.calc(num-1) + self.calc(num-2) end end