『もっとプログラマ脳を鍛える数学パズル』が当たるオリジナルクイズの解答発表!|翔泳社の本

『もっとプログラマ脳を鍛える数学パズル』が当たるオリジナルクイズの解答発表!

2018/02/20 07:00

 2月2日にCodeZine上で出題した『もっとプログラマ脳を鍛える数学パズル』が当たるオリジナルクイズ「本の発行部数のパターンは何通り?」、その解答を発表します。正解者の中から抽選で3名に、本書をプレゼントします。

もっとプログラマ脳を鍛える数学パズル』の発売記念に出題したオリジナルクイズ「本の発行部数のパターンは何通り?」。解答して応募してくださった皆さん、ありがとうございました。

 正解者の中から抽選で3名に本書をプレゼントしますので、連絡をお待ちください。不正解の方、また抽選に外れてしまった方には連絡いたしませんのでご了承ください。

解答とソースコードの例

 さて、お待たせしました、いよいよ解答の発表です。その前に問題を振り返っておきましょう。

 本が10回増刷されたとき(初版と合わせて合計11回発行されたとき)、発行部数の合計が10万部になるような、各発行タイミングにおける発行部数のパターンは何通りあるでしょうか。

※各発行タイミングにおける発行部数は1000部単位で、前回の発行部数と同じか、それより少ない部数を発行することにします。

 答えは4,426,616通りです。

 初刷の発行部数を決めると、残った部数を増刷時に発行することになります。このとき、発行回数は1回減り、残りの発行部数は全体から初刷の発行部数を引いたものとなります。

 これは増刷時でも同様で、残りの発行回数と発行部数が分かると、再帰的に探索できます。ただし、前回の発行部数も必要です。

 そこで、残りの発行回数と発行部数、前回の発行部数という3つの引数を用いた処理で表現してみます。なお、各発行タイミングでの発行部数は1000部単位ですが、これを1000で割って「1部単位で合計100部を作る」、と考えても問題ありません。

 また、初刷に7000部発行して増刷時に2000部発行するのと、初刷に6000部発行して増刷時に3000部発行するのは、発行回数も残った部数も同じです。このような場合をメモ化することで、高速に処理できます。

 これを実装すると、以下のようになります。

Rubyによる例
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倍速くなる?」をプレゼントします。アルゴリズムを理解するための初歩的な知識となる「データ構造」と「ソート」についての解説です。

 アルゴリズムの基礎を学べば、数学パズルをすらすら解けるようになるでしょう。実務にも役立つ内容ですが、まずはパズルに挑戦してみてください!

特典をチェックする

もっとプログラマ脳を鍛える数学パズル

Amazon SEshop その他

もっとプログラマ脳を鍛える数学パズル
アルゴリズムが脳にしみ込む70問

著者:増井敏克
発売日:2018年2月19日(月)
価格:2,786円(税込)

本書の特徴

・パズル問題をソースコードで解く
・楽しみながらプログラミングが上達
・4人のキャラクターによるやさしい解説
・アルゴリズムを深く理解できる