Euler : Problem 76

Posted by TAKAIY On 2012年1月4日水曜日 0 コメント
100を自然数の和に分割する問題です。

初めは動的計画法のつもりで、1から積み上げていく方法をやってみたのですが、あえなく時間切れ。

Wikipediaでこれが自然数の分割というのだということを知り、とりあえずそこに出ていた式を実装してみたら解けた。







漸化式はこれ


  • p(kn) = 0 if k > n
  • p(kn) = 1 if k = n
  • p(kn) = p(k+1, n) + p(kn − k) otherwise.


と言っても、メモ化してるので、動的計画法には違いない。




- partition-num
Wikipediaの漸化式をそのまま関数にしただけ。 自前のdefn-memoでメモ化している。
clojureのmemoizeは、1.3になっても再帰の中の関数呼び出しには効果が無いようなので、使えません。
また、末尾再帰にもなっていませんが、たかだか100段程度なので、スタックはあふれません。

(partition-num 1 100) とすると答えが出ます。


0 コメント:

コメントを投稿