プログラミングを仕事にし始めると、楽しむことよりも効率的に作業をこなすことを優先し、好奇心からではなく業務に必要だからという理由で知識と技術を身につけている方もいるかもしれません。最初は自分で書いたコードが動作するだけで楽しかったのに、いったいどうしてこうなってしまったのか……？
ですが、日々の仕事に嫌気が差している方でも、発見と喜びの味は格別だとご存知のはず。もう一度、心からプログラミングを楽しいと思いたい――そんな方のために、翔泳社では10月13日（火）に『プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問』を刊行しました。
本書にはエンジニアに人気のスキル評価サービス「CodeIQ」の連載「今週のアルゴリズム」から問題を収録、さらにオリジナル問題を追加。解いていくだけで高速化・単純化・一般化のためのアルゴリズムを習得することができます。言語は問いません、得意な言語や勉強中の言語で取り組んでみてください。
今回は本記事だけのオリジナル問題を最後に出題し、それを解くことができた方に本書をプレゼントいたします……が、その前に小手調べ（募集は締め切りました）。
入門編：いまだに現金払い？（目標時間15分）
最近は電車もバスも電子マネーが当たり前。でも、いまだに現金で払う人も意外と多いもの。今回はバスに設置されている両替機を考えます。
この機械では、10円玉、50円玉、100円玉、500円玉の組み合わせに両替することができ、いずれの硬貨も充分な枚数がセットされています（現金での運賃は10円単位になっているため、1、5円玉は取り扱っていません）。
両替する際に、使われない硬貨があっても構いませんが、バスの中でたくさん小銭が出ると困るため、最大15枚になるように両替します。例えば1000円を両替するときに、「10円玉を100枚」という両替はできません。
上記の条件において、1000円札を入れたときに出てくる硬貨の組み合わせは何通りあるかを求めてください。なお、硬貨の順番は区別しないものとします。
いかがでしょうか。難しいという方も、簡単だという方も、自分なりに回答してみてください。本書が用意した解答は文末にあります。
それではいよいよ、正解すれば本書をゲットできるオリジナル問題を発表します。
プレゼントキャンペーン：カラーボックスで作る本棚
手軽で便利な家具として人気のカラーボックスは、さまざまな種類が販売されています。今回は3段のカラーボックス（縦90cm、横60cm）を複数組み合わせて本棚を作ることを考えます（カラーボックスは横に倒すことで、雑誌など大きな本も入れられるようになります）。
上下左右に並べて配置して、見た目がスッキリするように「全体として長方形」になるようにします。例えば、5個のカラーボックスを使うと、下記左図のような8パターンが考えられます（下記右図のような配置は「全体として長方形」になっていないのでNGです）。
上記の条件において、20個のカラーボックスを使った場合、その配置が何パターンあるかを求めてください。回答される場合はソースコードをお忘れなく。
※個々のカラーボックスは区別せず、配置のパターン数のみを考えてください。また、置く場所には充分な広さと高さがあるものとします。
この問題の回答を下記からご応募いただくと、正解者の中から3名に本書をプレゼントします。
ほんの束の間、コードを覚えたばかりの頃のようにプログラミングを楽しんでみませんか？
『プログラマ脳を鍛える数学パズル』プレゼントキャンペーン
応募方法
募集は締め切りました。
※ソースコードの未記入は正解の場合でもプレゼント対象外となります。
回答期限
2015年10月28日（水）午前6時まで。
プレゼント内容と対象者
問題に正解した方の中から抽選で3名
→『プログラマ脳を鍛える数学パズル』をプレゼント
正解して抽選に外れた方
→翔泳社のオンラインショップ「SEshop」で使える20％オフクーポンをプレゼント
連絡方法
正解および当選の方にのみ、個別にご連絡します。
CodeZine上でお名前やメールアドレス、回答を公表することはありません。
解答の発表
解答は10月28日（水）午前6時以降にCodeZine上で発表します。
→「20個のカラーボックスで作る本棚は何通り？『プログラマ脳を鍛える数学パズル』キャンペーンクイズの解答」
「いまだに現金払い？」の解答と解説
答えは20通りです。この問題は、条件を満たすような硬貨の枚数を順番に調べていけば解くことができます。例えば、Rubyでは以下のように書くことができます。
cnt = 0
(0..2).each{|coin500| # 500円玉は最大2枚
(0..10).each{|coin100| # 100円玉は最大10枚
(0..15).each{|coin50| # 50円玉は最大15枚
(0..15).each{|coin10| # 10円玉は最大15枚
if coin500 + coin100 + coin50 + coin10 <= 15 then
if coin500 * 500 + coin100 * 100 +
coin50 * 50 + coin10 * 10 == 1000 then
cnt += 1
end
end
}
}
}
}
puts cnt
ですが、これだと拡張性に乏しく、紙幣も含めた1万円の両替や最大枚数が変わると、ループ回数の考慮が必要になります。そこで、変更に強いアルゴリズムを考えてみましょう。
coins = [10, 50, 100, 500]
cnt = 0
(2..15).each do |i|
coins.repeated_combination(i).each{|coin_set|
cnt += 1 if coin_set.inject(:+) == 1000
}
end
puts cnt
Rubyでは、5行目の「inject(:+)」によって配列の要素の合計を求めることができます。こうしておくと、扱う硬貨（紙幣）や目標額が変更されたときも修正箇所がすぐに分かります。
さらに、再帰を使って以下のように書くこともできます。
@cnt = 0
def change(target, coins, usable)
coin = coins.shift
if coins.size == 0 then
@cnt += 1 if target / coin <= usable
else
(0..target/coin).each{|i|
change(target - coin * i, coins.clone, usable - i)
}
end
end
change(1000, [500, 100, 50, 10], 15)
puts @cnt
こうすると12行目を書き換えるだけでいろいろな入力に対応できます。仕様変更に強いプログラムを書くことも重要ですね。
