Ответ 1

Попробуй это

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

Ответ 2

Вот что я придумал, я нахожу это более прямым.

def fib(n)
  n.times.each_with_object([0,1]) { |num, obj| obj << obj[-2] + obj[-1] }
end
fib(10)

Ответ 3

Это не так, как вы вычисляете фибоначчи, вы создаете огромное рекурсивное дерево, которое не удастся для относительно небольших 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) }

Ответ 4

линейный

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)

Ответ 5

PHI = 1.6180339887498959
TAU = 0.5004471413430931

def fibonacci(n)
  (PHI**n + TAU).to_i
end

Вам не нужна рекурсия.

Ответ 6

Этот подход быстрый и использует запоминание:

fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }

fib[123] # => 22698374052006863956975682

Если вам интересно, как работает инициализация хеша, прочитайте здесь:

https://ruby-doc.org/core/Hash.html#method-c-new

Ответ 7

Рекурсия очень медленная, здесь более быстрый способ

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. по постоянному коэффициенту, ну, я не хотел быть здесь очень основательно. Но недавно я провел много исследований по числу фибоначчи, и я хочу, чтобы мои исследования были полезны для всех, кто хочет учиться ;;).

Ответ 8

Это может вам помочь.

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, " "}

Ответ 9

я думаю, это довольно легко:

def fibo(n) a=0 b=1 for i in 0..n c=a+b print "#{c} " a=b b=c end

end

Ответ 10

Попробуйте это oneliner

def fib (n)
    n == 0 || n == 1 ? n : fib(n-2) + fib(n-1)
end
print fib(16)

Выход: 987

Ответ 11

самый быстрый и самый маленький в линейном решении:

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

функциональный автопортрет :)

Ответ 12

Мы можем выполнять список фибо-рядов, используя алгоритм ниже

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] 

Ответ 13

Если вы хотите написать самый быстрый функционал алгоритма для 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)

Ответ 14

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 

Ответ 15

Другой подход к вычислению чисел фибоначчи, использующих преимущество 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.

Ответ 16

Вот более краткое решение, которое создает таблицу поиска:

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}

Ответ 17

Кто-то спросил меня что-то подобное сегодня, но он хотел получить массив с последовательностью фибоначчи для заданного числа. Например,

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

Ответ 18

Вот один из них в 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)
  }
}

Ответ 19

Я думаю, что это лучший ответ, который был ответом другой должности SO, задающей аналогичный вопрос.

В принятом ответе от PriteshJ здесь используется наивная рекурсия фибоначчи, что прекрасно, но становится чрезвычайно медленным, как только вы пройдете мимо 40-го или около того элемента. Это намного быстрее, если вы кешируете /memoize предыдущие значения и передаете их, когда вы рекурсивно итерации.

Ответ 20

Это было какое-то время, но вы можете написать довольно элегантную и простую однолинейную функцию:

def fib(n)
  n > 1 ? fib(n-1) + fib(n-2) : n
end

Ответ 21

Это фрагмент, который я использовал для решения проблемы программирования в 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

Ответ 22

Присоединение к поезду Фибоначчи:

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

Ответ 23

еще один ;)

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}