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?
Есть много способов определить последовательность Фибоначчи, но мой любимый - это:
val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }
Это создает поток, который оценивается лениво, когда вам нужно определенное число Фибоначчи.
РЕДАКТИРОВАТЬ: Во-первых, как указал Луиджи Плинге, «ленивый» в начале был ненужным. Во-вторых, посмотрите на его ответ, он сделал то же самое, только более элегантно.
(foo zip bar).map{ t => f(t._1, t._2) }. В Haskell это будет zipWith f foo bar, а в Racket (map f foo bar).
- person Dan Burton; 26.03.2012
(foo zip bar) map f, если f ожидает кортеж, и (foo zip bar) map f.tupled, если f ожидает два параметра.
- person kiritsuku; 26.03.2012
lazy val, если оно определено как локальная переменная, а не как поле объекта/класса. Потому что, когда это поле, компилятор переводит fibs в this.fibs, так что вы можете обойтись без lazy. Мех. Вероятно, лучше сохранить его для согласованности.
- person Luigi Plinge; 16.04.2012
Это немного более элегантно:
val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
С потоками вы «берете» ряд значений, которые затем можете превратить в список:
scala> fibs take 10 toList
res42: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
Обновление: я написал сообщение в блоге, в котором более подробно рассказывается о том, как работает это решение, и почему у вас получается последовательность Фибоначчи!
lazy.
- person Hunter McMillen; 02.04.2013
object или в REPL, то нет. Если это внутри метода, вам нужен lazy.
- person Luigi Plinge; 02.04.2013
Long? Запуск fibs(200) дает отрицательное число. Замена Int на Long вызывает ошибку компиляции.
- person Ébe Isaac; 25.04.2018
Не такой элегантный, как Streams, не ленивый, но tailrecursive и обрабатывает BigInt (что легко сделать и с Luigis scanLeft, но не так с zip от 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) }
scala> fib (75)
res135: List[BigInt] = List(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, 449455288, 44945570212853, 72723460248141, 11766903046099, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 211485077978050)
def fib(n: Int, s: List[BigInt] = List(1, 0)): List[BigInt] = if (n <= 2) s.reverse else fib(n - 1, s(0) + s(1) :: s)
- person Luigi Plinge; 26.03.2012
[Int] слева на [BigInt]! Литералы Int справа преобразуются неявно.
- person Luigi Plinge; 29.03.2012
Моя любимая версия:
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.
Вот еще один подход, снова использующий *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)
Я считаю эту реализацию более разборчивой:
def fibonacci: Stream[Int] = {
def loop(a: Int, b: Int): Stream[Int] = (a + b) #:: loop(b, b + a)
loop(0, 1)
}
