Генерация последовательности числа Фибоначчи в Scala

Question

  def fibSeq(n: Int): List[Int] = {
    var ret = scala.collection.mutable.ListBuffer[Int](1, 2)
    while (ret(ret.length - 1) < n) {
      val temp = ret(ret.length - 1) + ret(ret.length - 2)
      if (temp >= n) {
        return ret.toList
      }
      ret += temp
    }
    ret.toList
  }

Итак, выше приведен мой код для генерации последовательности Фибоначчи с использованием Scala для значения n, Мне интересно, есть ли более элегантный способ сделать это в Scala?

Answer 1

Есть много способов определить последовательность Фибоначчи, но мой любимый это:

val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }

Это создает поток, который оценивается лениво, когда вам нужно конкретное число Фибоначчи.

РЕДАКТИРОВАТЬ: Во-первых, как указал Луиджи Плинге, "ленивый" в начале было ненужным. Во-вторых, посмотрите на его ответ, он сделал то же самое, только более элегантно.

Answer 2

Это немного элегантнее:

val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)

С помощью Streams вы "берете" несколько значений, которые затем можете превратить в список:

scala> fibs take 10 toList
res42: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

Обновление: я написал пост в блоге, в котором более подробно рассказывается о том, как работает это решение, и почему вы получаете последовательность Фибоначчи!

Answer 3

Не так элегантно, как Streams, не ленивый, но хвостовой рекурсив и обрабатывает BigInt (что легко сделать и с Luigis scanLeft, но не так с молнией Tal - возможно, только для меня).

@tailrec 
def fib (cnt: Int, low: BigInt=0, high: BigInt=1, sofar: List[BigInt]=Nil): List[BigInt] = {
  if (cnt == 0) (low :: sofar).reverse else fib (cnt - 1, high, low + high, low :: sofar) }

скала> фиб (75)
res135: List [BigInt] = Список (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, 1023341531, 16338334, 1641, 8338291, 1655, 841, 1955, 11, 16, 87, 937, 1655, 837, 932, 932, 932, 932, 868, 968, 841, 16, 8, 29, 29, 44, 16, 87, 2941, 1641, 8, 16, 8, 19, 19, 19, 19, с., 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050)

Answer 4

Моя любимая версия:

def fibs(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fibs(b, a+b))

Со значениями по умолчанию вы можете просто позвонить fibs() и получить бесконечное Stream,

Я также думаю, что он хорошо читается, несмотря на то, что он один лайнер.

Если вы просто хотите первый n тогда вы можете использовать take лайк fibs() take nи если вам это нужно в виде списка fibs() take n toList,

Answer 5

Вот еще один подход, снова использующий *Stream* s для промежуточных кортежей:

scala> val fibs = Stream.iterate( (0,1) ) { case (a,b)=>(b,a+b)  }.map(_._1) 
fibs: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> fibs take 10 toList
res68: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

Answer 6

Я считаю эту реализацию более разборчивой:

def fibonacci: Stream[Int] = {
    def loop(a: Int, b: Int): Stream[Int] = (a + b) #:: loop(b, b + a)
    loop(0, 1)
}

Answer 7

def fib:Stream[Int] ={
  def go(f0: Int, f1:Int): Stream[Int] = {
    Stream.cons(f0,go(f1,f0+f1))
  }
  go(0,1)
}