プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q22:絡まない糸電話。

Q: 同一円周上に等間隔に並んだ子供が、ペアを組んで糸電話する。この時、意図が交差しないようペアを組む必要がある。16人の子供がいた場合、作ることができるペアが何通りあるかを求める。

val memo = scala.collection.mutable.Map(0->1)
def count(num:Int):Int = {
  memo.getOrElse(num, {
      val result = (0 until num).fold(0){(z,a) => z + count(a)*count(num-a-1)}
      memo + (num -> result)
      result
    })
}
count(16/2)