Project EulerのProblem 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)
