Generowanie ciągu liczby Fibonacciego w Scali [duplikat]
To pytanie ma już odpowiedź tutaj:
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
}
Więc powyższy kod jest moim kodem do generowania ciągu Fibonacciego przy użyciu Scali do wartości n
. Zastanawiam się, czy jest bardziej elegancki sposób, aby to zrobić w Scali?
7 answers
Istnieje wiele sposobów definiowania ciągu Fibonacciego, ale moim ulubionym jest ten:
val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }
Tworzy to strumień, który jest oceniany leniwie, gdy chcemy mieć określoną liczbę Fibonacciego.
Edytuj: Po pierwsze, jak zauważył Luigi Plinge, "leniwy" na początku był niepotrzebny. Po drugie, spójrz na jego odpowiedź, zrobił to samo tylko bardziej elegancko.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-03-26 06:07:42
To jest nieco bardziej eleganckie:
val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
Ze strumieniami "pobierasz" kilka wartości, które następnie możesz przekształcić w listę:
scala> fibs take 10 toList
res42: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
Aktualizacja: napisałem wpis na blogu , który mówi więcej szczegółów na temat tego, jak to rozwiązanie działa, i dlaczego kończy się z ciągiem Fibonacciego!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-05-03 13:10:25
Nie tak eleganckie jak strumienie, nie leniwe, ale tailrecursive i obsługuje BigInt (co jest łatwe do zrobienia z Luigis scanLeft też, ale nie tak z zip Tal - może tylko dla mnie).
@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] = lista(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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-03-26 09:39:31
Moja ulubiona wersja to:
def fibs(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fibs(b, a+b))
Z wartościami domyślnymi można po prostu wywołać fibs()
i uzyskać nieskończoną Stream
.
Myślę również, że jest bardzo czytelny, mimo że jest jednym linerem.
Jeśli chcesz tylko pierwszy n
, możesz użyć take
Jak fibs() take n
, a jeśli potrzebujesz go jako listy fibs() take n toList
.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-03-24 18:03:12
Oto kolejny sposób użycia * Stream *s na krotce pośredniczącej:
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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-03-23 05:22:56
Uważam, że ta implementacja jest bardziej czytelna:
def fibonacci: Stream[Int] = {
def loop(a: Int, b: Int): Stream[Int] = (a + b) #:: loop(b, b + a)
loop(0, 1)
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-07-26 19:39:25
def fib:Stream[Int] ={
def go(f0: Int, f1:Int): Stream[Int] = {
Stream.cons(f0,go(f1,f0+f1))
}
go(0,1)
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-03-19 16:08:47