ScalaでProject Euler(113)

Problem 76

Project Eulerには再帰に持ち込めば簡単になる問題が多いです。5を分割することを考えます。まず5から4を取ります。残り1なのでその分割数を考えればよいです。次に5から3を取ります。残り2なので2の分割数を取ります。次に5から2を取ります。残り3の分割数を考えるのですが、最大は2という縛りがあります。1を取る場合も4を最大1で分割することを考えます。nを最大mで分割する場合の数をf(n, m)とすると、

f(5, 5) = f(0, 0) + f(1, 1) + f(2, 2) + f(3, 2) + f(4, 1)

となります。またf(0, m)は1と考えます。これでコードが書けるでしょう。68秒でした。

import scala.testing.Benchmark

def num_divs(n :Int) :Int = {
    def f(n :Int, m :Int) :Int =
        if(n == 0)
            1
        else
            Iterator.range(1, m + 1).map(k => f(n - k, k.min(n - k))).sum
    
    f(n, n) - 1
}

def solve() = {
    val N = 100
    println (num_divs(N))
}

object Test extends Benchmark {
    def run() = solve
}

println (Test.runBenchmark(1))