YAMAGUCHI::weblog

土足で窓から失礼いたします。今日からあなたの息子になります。 当年とって92歳、下町の発明王、エジソンです。

変則Fibonacciの問題を解く

はじめに

社内Scala勉強会が発足し、ある方が「この問題を解きましょう」と言ったのでコードを書いてみた。

  • 実行速度
  • Scalaっぽさ(?)

が注目されてたっぽいので書いてみた。

問題

7110を含むフィボナッチ数列で、
初期値の組み合わせが一番小さいものをあげろ。
自然数に限る

解答

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使ってるせいかなにかしらないけど、スタックトレース出来ないのが困る。