Générer une séquence de nombre de Fibonacci dans Scala [dupliquer]
Cette question a déjà une réponse ici:
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
}
donc le code ci-dessus est mon code pour générer une séquence de Fibonacci en utilisant Scala à une valeur n. Je me demande s'il y a une façon plus élégante de faire cela à Scala?
7 réponses
Il y a plusieurs façons de définir la séquence de Fibonacci, mais mon préféré est celui-ci:
val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }
cela crée un flux qui est évalué de façon paresseuse quand vous voulez un nombre spécifique de Fibonacci.
modifier: Tout d'abord, comme L'a souligné Luigi Plinge, le "paresseux" au début n'était pas nécessaire. Deuxièmement, allez voir sa réponse, il a fait à peu près la même chose que plus élégamment.
C'est un peu plus élégante:
val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
avec Streams vous "prenez" un certain nombre de valeurs, que vous pouvez alors transformer en une liste:
scala> fibs take 10 toList
res42: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
mise à Jour: j'ai écrit un blog ce qui explique plus en détail le fonctionnement de cette solution, et pourquoi vous vous retrouvez avec une séquence de Fibonacci!
pas aussi élégant que Streams, pas paresseux, mais taillecursive et handles BigInt (ce qui est facile à faire avec Luigis scanLeft aussi, mais pas avec tal's zip - peut-être juste pour moi).
@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, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050)
ma version préférée est:
def fibs(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fibs(b, a+b))
Avec les valeurs par défaut, vous pouvez simplement appeler fibs() et obtenir l'infini Stream.
je pense aussi que c'est très lisible, en dépit d'être une doublure.
Si vous voulez juste le premier n alors vous pouvez utiliser takefibs() take n et si vous en avez besoin que d'une liste fibs() take n toList.
Voici encore une autre approche en utilisant * Stream*s sur un intermédiaire n-uplets:
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)
je trouve cette implémentation plus lisible:
def fibonacci: Stream[Int] = {
def loop(a: Int, b: Int): Stream[Int] = (a + b) #:: loop(b, b + a)
loop(0, 1)
}
def fib:Stream[Int] ={
def go(f0: Int, f1:Int): Stream[Int] = {
Stream.cons(f0,go(f1,f0+f1))
}
go(0,1)
}