『もっとプログラマ脳を鍛える数学パズル』の発売記念に出題したオリジナルクイズ「本の発行部数のパターンは何通り？」。解答して応募してくださった皆さん、ありがとうございました。
正解者の中から抽選で3名に本書をプレゼントしますので、連絡をお待ちください。不正解の方、また抽選に外れてしまった方には連絡いたしませんのでご了承ください。
解答とソースコードの例
さて、お待たせしました、いよいよ解答の発表です。その前に問題を振り返っておきましょう。
本が10回増刷されたとき（初版と合わせて合計11回発行されたとき）、発行部数の合計が10万部になるような、各発行タイミングにおける発行部数のパターンは何通りあるでしょうか。
※各発行タイミングにおける発行部数は1000部単位で、前回の発行部数と同じか、それより少ない部数を発行することにします。
答えは4,426,616通りです。
初刷の発行部数を決めると、残った部数を増刷時に発行することになります。このとき、発行回数は1回減り、残りの発行部数は全体から初刷の発行部数を引いたものとなります。
これは増刷時でも同様で、残りの発行回数と発行部数が分かると、再帰的に探索できます。ただし、前回の発行部数も必要です。
そこで、残りの発行回数と発行部数、前回の発行部数という3つの引数を用いた処理で表現してみます。なお、各発行タイミングでの発行部数は1000部単位ですが、これを1000で割って「1部単位で合計100部を作る」、と考えても問題ありません。
また、初刷に7000部発行して増刷時に2000部発行するのと、初刷に6000部発行して増刷時に3000部発行するのは、発行回数も残った部数も同じです。このような場合をメモ化することで、高速に処理できます。
これを実装すると、以下のようになります。
reprint, total = 11, 100000
@memo = {}
def publish(reprint, total, pre)
if @memo[[reprint, total, pre]]
return @memo[[reprint, total, pre]]
end
return 0 if total < 0
return (total == 0)?1:0 if reprint == 0
cnt = 0
1.upto(pre) do |i|
cnt += publish(reprint - 1, total - i, i)
end
@memo[[reprint, total, pre]] = cnt
end
puts publish(reprint, total / 1000, total / 1000)
皆さん、正解しましたか？ Ruby以外でも実装する方法はありますので、いろいろと考えてみてはいかがでしょうか。
見事正解した方も、残念ながら間違ってしまった方も、アルゴリズムの実装力をさらに養える『もっとプログラマ脳を鍛える数学パズル』をお楽しみください！
購入特典キャンペーンも実施中
本書を購入していただいた方のために、特典として特別解説「アルゴリズムで1000倍速くなる？」をプレゼントします。アルゴリズムを理解するための初歩的な知識となる「データ構造」と「ソート」についての解説です。
アルゴリズムの基礎を学べば、数学パズルをすらすら解けるようになるでしょう。実務にも役立つ内容ですが、まずはパズルに挑戦してみてください！
