エントリービルゲイツの面接試験ネタに便乗に便乗の金貨問題で出した問題の2問目は、エントリー金貨問題の解答編で可能であることだけ書いて力技での検証をしませんでした。問題を要約すると
正規品10グラムの金貨が24枚入った6袋中、何袋あるかわからない全て偽造品11グラムの金貨の袋を、1回だけの計量で選別する方法があるかです。
ちょうど今ものにしようとしているプログラミング言語Rubyの題材として適当そうですので、プログラムを作って本当にそんなことが可能かどうか検証してみます。
(なお組み合わせを生成する部分は書籍Rubyプログラミング入門
まず以下の2つの関数を作ります。
[code language="ruby"]
# 各n枚の金貨が入ったm袋からの金貨の取り出しかた全てについて、与えられたブロックを実行する
def combi(n, m)
if m == 0
yield([])
else
combi(n, m - 1) do |x|
s = (x.length == 0 ? 1 : x[0] + 1)
(s..n).each do |i|
yield([i] + x)
end
end
end
end
# 与えられた金貨の取り出しかたについて、正規品および偽造品の組み合わせ全てで
# 重量が区別できるかどうか調べる
def weight(coins)
if coins.length == 0
return [0]
end
weight_list = weight(coins[1..-1])
if !weight_list
return nil
end
new_list = []
weight_list.each do |x|
# 正規金貨の場合
w = coins[0] * 10 + x
if new_list.index(w)
# 重量が重複するので不可
return nil
end
new_list.push(w)
# 偽造金貨の場合
w = coins[0] * 11 + x
if new_list.index(w)
# 重量が重複するので不可
return nil
end
new_list.push(w)
end
return new_list
end
[/code]
この2つの関数を以下のように使って、24枚入り6袋の場合で実行して結果を表示させてみましょう。
[code language="ruby"]
combi(24, 6) do |x|
if weight(x)
p x
end
end
[/code]
[24, 23, 22, 20, 17, 11]
結果はこの組み合わせ1つ。24枚入り6袋でも24, 23, 22, 20, 17, 11枚と取り出せば偽造金貨の袋を1回の計量で選別できるということです(プログラムが正しければ^^)。
う〜ん興味深いですね〜。