我正在尝试实现以下功能，但它一直给我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 )
问问题
68670 次
27 回答
44
试试这个
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)
你现在已经被许多解决方案轰炸了:)
关于你的解决方案中的问题
n如果它0或你应该返回1
最后add两个数字不是最后一个和下一个
新修改版
def fibonacci( n )
return n if n <= 1
fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55
一个班轮
def fibonacci(n)
n <= 1 ? n : fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55
于 2012-08-29T13:07:53.230 回答
19
这是我想出的东西，我觉得这更直接。
def fib(n)
n.times.each_with_object([0,1]) { |num, obj| obj << obj[-2] + obj[-1] }
end
fib(10)
于 2012-09-25T15:57:14.760 回答
13
这种方法很快并且利用了记忆：
fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }
fib[123] # => 22698374052006863956975682
如果您想知道这个哈希初始化是如何工作的，请阅读这里：
于 2017-11-30T19:25:36.147 回答
12
线性
module Fib
def self.compute(index)
first, second = 0, 1
index.times do
first, second = second, first + second
end
first
end
end
带缓存的递归
module Fib
@@mem = {}
def self.compute(index)
return index if index <= 1
@@mem[index] ||= compute(index-1) + compute(index-2)
end
end
关闭
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
如果您致电，这些解决方案都不会使您的系统崩溃Fib.compute(256)
于 2014-07-02T21:46:28.717 回答
11
这不是您计算斐波那契的方式，您正在创建巨大的递归树，它将在相对较小n的 s 中失败。我建议你这样做：
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) }
于 2012-08-29T14:56:19.600 回答
5
递归很慢，这里有一个更快的方法
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。由于一个恒定的因素，我不想在这里非常彻底。但我最近对斐波那契数进行了很多研究，我希望我的研究对任何愿意学习的人有用，;)。
于 2013-02-17T14:01:24.790 回答
4
这可能会对您有所帮助。
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, " "}
于 2014-03-06T05:22:02.940 回答
4
我认为这很容易：
def fibo(n) a=0 b=1 for i in 0..n c=a+b print "#{c} " a=b b=c end
end
于 2014-12-06T19:46:05.210 回答
4
我们可以使用以下算法执行列表 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]
于 2015-08-24T05:59:24.460 回答
4
试试这个oneliner
def fib (n)
n == 0 || n == 1 ? n : fib(n-2) + fib(n-1)
end
print fib(16)
输出：987
于 2015-12-01T15:28:03.237 回答
4
PHI = 1.6180339887498959
TAU = 0.5004471413430931
def fibonacci(n)
(PHI**n + TAU).to_i
end
你不需要递归。
于 2016-09-06T12:17:06.980 回答
3
最快和最小的生产线解决方案：
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
功能自拍模式:)
于 2014-03-23T18:12:03.190 回答
2
a = [1, 1]
while(a.length < max) do a << a.last(2).inject(:+) end
这将填充a系列。（你必须考虑 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
于 2014-08-01T09:20:07.490 回答
2
这是构建查找表的更简洁的解决方案：
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}
于 2015-07-01T05:39:53.217 回答
2
这是我在 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
于 2017-06-03T15:42:00.517 回答
2
加入斐波那契火车：
常规的：
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
于 2017-07-29T11:34:55.773 回答
2
完后还有 ;）
def fib(n)
f = Math.sqrt(5)
((((1+f)/2)**n - ((1-f)/2)**n)/f).to_i
end
添加一些缓存也会很方便
def fibonacci
@fibonacci ||= Hash.new {|h,k| h[k] = fib k }
end
所以我们可以得到它
fibonacci[3] #=> 2
fibonacci[10] #=> 55
fibonacci[40] #=> 102334155
fibonacci #=> {3=>2, 10=>55, 40=>102334155}
于 2019-05-02T08:45:26.977 回答
1
如果你想为 fib 编写最快的函数算法，它不会是递归的。这是编写解决方案的功能性方式较慢的少数几次之一。因为如果你使用类似的东西，堆栈会重复它自己
fibonacci( n - 1 ) + fibonacci( n - 2 )
最终 n-1 和 n-2 将创建相同的数字，因此将在计算中进行重复。最快的方法是迭代
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)
于 2014-06-14T05:35:55.207 回答
1
利用记忆化计算斐波那契数的另一种方法：
$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 方法的调用次数。
于 2014-10-10T01:55:08.880 回答
1
今天有人问我类似的问题，但他想得到一个给定数字的斐波那契数列数组。例如，
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
于 2015-09-11T21:48:05.757 回答
1
这是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)
}
}
于 2016-07-25T07:24:32.640 回答
1
我认为这是最好的答案，这是另一个 SO 帖子提出类似问题的回应。
这里接受的答案PriteshJ使用朴素的斐波那契递归，这很好，但是一旦超过第 40 个元素，它就会变得非常慢。如果您缓存/记忆以前的值并在递归迭代时传递它们，速度会快得多。
于 2016-09-20T23:53:31.850 回答
1
已经有一段时间了，但是您可以编写一个相当优雅且简单的单行函数：
def fib(n)
n > 1 ? fib(n-1) + fib(n-2) : n
end
于 2017-02-23T14:16:51.020 回答
1
1) 示例，其中最大元素 < 100
def fibonachi_to(max_value)
fib = [0, 1]
loop do
value = fib[-1] + fib[-2]
break if value >= max_value
fib << value
end
fib
end
puts fibonachi_to(100)
输出：
0
1
1
2
3
5
8
13
21
34
55
89
2) 示例，其中 10 个元素
def fibonachi_of(numbers)
fib = [0, 1]
(2..numbers-1).each { fib << fib[-1] + fib[-2] }
fib
end
puts fibonachi_of(10)
输出：
0
1
1
2
3
5
8
13
21
34
于 2019-11-20T17:39:51.737 回答
0
Ruby Fiber的一个不错的小介绍-
def fibs x, y
Fiber.new do
while true do
Fiber.yield x
x, y = y, x + y
end
end
end
上面我们创建了一个无限的fibs数字流，以非常有效的方式计算。一个不只是puts一个无限的流，所以我们必须编写一个小函数来从我们的流中收集有限数量的项目，take-
def take t, n
r = []
while n > 0 do
n -= 1
r << t.resume
end
r
end
最后让我们看看100序列中的第一个数字，从0和开始1-
puts (take (fibs 0, 1), 100)
0
1
1
2
3
5
8
13
21
34
55
.
.
.
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
于 2021-02-11T17:13:54.433 回答
0
这个使用记忆和递归：
def fib(num, memo={})
return num if num <= 1
if memo[num]
return memo[num]
else
memo[num] = fib(num - 2, memo) + fib(num - 1, memo)
end
end
于 2021-07-07T04:38:13.337 回答
0
使用矩阵求幂：
不要使用递归，因为堆栈会累积，并且您将在计算机无法再处理的某个点达到限制。那就是stack level too deep (SystemStackError)你看到的。改用矩阵求幂：
def fib(n)
(Matrix[[1,1],[1,0]] ** n)[1,0]
end
fib(1_000_000) #this is too much for a recursive version
于 2022-01-27T17:17:22.880 回答