Я пытаюсь реализовать следующую функцию, но она продолжает давать мне 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)
Теперь вас обрушило множество решений :)
относительно проблемы в решении ур
вы должны вернуть 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
Вот что я придумал, я нахожу это более прямым.
def fib(n)
n.times.each_with_object([0,1]) { |num, obj| obj << obj[-2] + obj[-1] }
end
fib(10)
Это не так, как вы вычисляете фибоначчи, вы создаете огромное рекурсивное дерево, которое не удастся для относительно небольших 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) }
линейный
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)
PHI = 1.6180339887498959
TAU = 0.5004471413430931
def fibonacci(n)
(PHI**n + TAU).to_i
end
Вам не нужна рекурсия.
fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }
fib[123] # => 22698374052006863956975682
Если вам интересно, как работает инициализация хеша, прочитайте здесь:
Рекурсия очень медленная, здесь более быстрый способ
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. по постоянному коэффициенту, ну, я не хотел быть здесь очень основательно. Но недавно я провел много исследований по числу фибоначчи, и я хочу, чтобы мои исследования были полезны для всех, кто хочет учиться ;;).
Это может вам помочь.
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..n c=a+b print "#{c} " a=b b=c end
end
Попробуйте это oneliner
def fib (n)
n == 0 || n == 1 ? n : fib(n-2) + fib(n-1)
end
print fib(16)
Выход: 987
самый быстрый и самый маленький в линейном решении:
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
функциональный автопортрет :)
Мы можем выполнять список фибо-рядов, используя алгоритм ниже
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, он не будет рекурсивным. Это один из немногих раз, когда функциональный способ написать решение медленнее. Поскольку стек повторяется, если вы используете что-то вроде
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)
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
Другой подход к вычислению чисел фибоначчи, использующих преимущество 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.
Вот более краткое решение, которое создает таблицу поиска:
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...
Вот мое решение. Он не использует рекурсию tho. Еще одно решение, если вы ищете нечто подобное: 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)
}
}
Я думаю, что это лучший ответ, который был ответом другой должности SO, задающей аналогичный вопрос.
В принятом ответе от PriteshJ здесь используется наивная рекурсия фибоначчи, что прекрасно, но становится чрезвычайно медленным, как только вы пройдете мимо 40-го или около того элемента. Это намного быстрее, если вы кешируете /memoize предыдущие значения и передаете их, когда вы рекурсивно итерации.
Это было какое-то время, но вы можете написать довольно элегантную и простую однолинейную функцию:
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
Присоединение к поезду Фибоначчи:
Regular:
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
еще один ;)
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}