Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

Problem 76

Project EulerProblem 76(日本語)です。

076.rb

分割数の問題でした。分割数については『数学ガール (数学ガールシリーズ 1)』で学習していたので、問題を読んだときにすぐにそれと気付きました。第10章では上界の一つが紹介され、エピローグでは一般項を表す式が紹介されています。一般項を使って問題を解こうと思いましたが、非常に難解なので、Wikipediaで漸化式を調べて解答しました。

  • k > n のとき: p(k, n) = 0
  • k = n のとき: p(k, n) = 1
  • それ以外: p(k, n) = p(k+1, n) + p(k, n − k)