Создайте последовательность чисел Фибоначчи в Scala


  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?

Ответ 1

Существует множество способов определить последовательность Фибоначчи, но мой любимый:

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

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

EDIT: Во-первых, как отметил Луиджи Плинг, "ленивый" в начале был ненужным. Во-вторых, взгляните на его ответ, он в значительной степени сделал то же самое только более элегантно.

Ответ 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)

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

Ответ 3

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

@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) }

scala > fib (75)
res135: Список [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, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 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)

Ответ 4

Здесь еще один подход, снова использующий * 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)

Ответ 5

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

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.

Ответ 6

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

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

Ответ 7

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