使用Scala函数式求解项目Euler 25

Question

我目前正在使用Project Euler学习Scala。
我被问题25卡住了，java.lang.OutOfMemoryError异常。

问题是:

斐波那契数列中包含1000位数字的第一个项的索引是什么?

我想到了什么:

def fibonacciIndex(numOfDigits: Int): Option[Int] = {
lazy val fibs: LazyList[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
fibs.find(_.toString.length == numOfDigits)
}

我正试图以纯粹的功能方式做到这一点。有没有人有一些建议来改善内存使用?

提前感谢!

---

编辑:我满溢的Int类型。像这样解决:

def fibonacciIndex(numOfDigits: Int): Int = {
lazy val bigFibs: LazyList[BigInt] = BigInt(0) #:: bigFibs.scanLeft(BigInt(1))(_ + _)
bigFibs.indexWhere(_.toString.length == numOfDigits)
}

Answer 1

让我们分几个部分运行你的程序。

lazy val fibs: LazyList[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
fibs.take(100).foreach(println)

它打印:

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
-1323752223
512559680
-811192543
-298632863
-1109825406
-1408458269
1776683621
368225352
2144908973
-1781832971
363076002
-1418756969
-1055680967
1820529360
764848393
-1709589543
-944741150
1640636603
695895453
-1958435240
-1262539787
1073992269
-188547518
885444751
696897233
1582341984
-2015728079
-433386095
1845853122
1412467027
-1036647147
375819880
-660827267
-285007387
-945834654
-1230842041
2118290601
887448560
-1289228135
-401779575
-1691007710
-2092787285
511172301
-1581614984
-1070442683
1642909629
572466946
-2079590721
-1507123775
708252800
-798870975
-90618175
-889489150

你可以看到整数溢出，所以它永远不会输出超过一定数量的数字(11我认为包括-)。所以它继续计算下一个值

另外，LazyList记住它计算的每个值。它是懒惰的，但记忆。这里计算的每个新数字

fibs.find(_.toString.length == numOfDigits)

也会被记住。它会一直运行，直到内存耗尽。

要解决这个问题，您应该将LazyList替换为Iterator或Iterable，并将数字存储为BigInts。