解答
object Fibonacci { def main (args: Array[String]): Unit = { println( "Fibonacci" ) val result = solver(7110) println( result ) } def fib (p: Int, c: Int, n: Int): Option[Int] = { c match { case _ if c == 7110 => Some(n) case _ if c > 7110 => None case _ => fib (c, p+c, n+1) } } def solver (max: Int): (Int,Int) = { val nums = Stream.range(2,max) val pairs = nums.map(x => Array.range(1, x/2+1) zip Array.range(x-1, x/2-1, -1)) pairs.flatMap( ps => ps.find( x => fib(x._1, x._2, 2) != None )).head } }
実行結果
1秒くらいだし、まあ他の人が何分とかかかってたぽいからいいでしょ。
$ time scala Fibonacci Fibonatti (16,70) real 0m1.094s user 0m0.990s sys 0m0.100s
感想
とりあえず自分がOCamlとかに触れてきた期間で関数型と遊ぶ上で学んだことは
- リストをいかに効率的に作るか
- パターンは極端なものから
- 再帰書く前にリスト操作関数使えないか考える
フィボナッチ関数
def fib (p: Int, c: Int, n: Int): Option[Int] = { c match { case _ if c == 7110 => Some(n) case _ if c > 7110 => None case _ => fib (c, p+c, n+1) } }
ぱっと末尾再帰で書いたらこうなった。Optionで返せばとりあえず楽。
判定部分
def solver (max: Int): (Int,Int) = { val nums = Stream.range(2,max) val pairs = nums.map(x => Array.range(1, x/2) zip Array.range(x-1, x/2, -1)) pairs.flatMap( ps => ps.find( x => fib(x._1, x._2, 2) != None )).head }
ここでやってるのは二つの数字の組みあわせの合計は、高々フィボナッチ数列に入っていなければいけない値(今回は7110)なはずなので、合計の予想値のStreamを作る。で、次にある合計値になる数字の組み合わせを合計値ごとに作成する。ここでArray同士のzipにしたのはサイズが固定で大きくないから。あとは各合計値が小さい順に条件を満たす数字がないか探して、見つけたらその値を返す、というだけ。
Streamのheadを取っているから、1個見つかった時点で終わる。Stream.flatMapを使っているのはArray.findがOption[(Int,Int)]を返すためheadでとれないから。
追記
これ7110だったらいいんですが、71107110くらいでやるとjava.lang.OutOfMemoryErrorで落ちてしまいます。Array.rangeではなくて、Stream.rangeをzipしても同じ。つまり
object Fibonacci { def main (args: Array[String]): Unit = { println( "Fibonacci" ) val result = solver(71107110) println( result ) } def fib (value: Int, p: Int, c: Int, n: Int): Option[Int] = { c match { case _ if c == value => Some(n) case _ if c > value => None case _ => fib (c, p+c, n+1) } } def solver (max: Int): (Int,Int) = { val nums = Stream.range(2,max) val pairs = nums.map(x => Stream.range(1, x/2+1) zip Stream.range(x-1, x/2-1, -1)) pairs.flatMap( ps => ps.find( x => fib(max, x._1, x._2, 2) != None )).head } }
としたけれど、結果として
$ scala Fibonacci Fibonatti java.lang.OutOfMemoryError
とでて終了する。Stream使ってるせいかなにかしらないけど、スタックトレース出来ないのが困る。