エントリービルゲイツの面接試験ネタに便乗に便乗の金貨問題で出した問題の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回の計量で選別できるということです(プログラムが正しければ^^)。
う〜ん興味深いですね〜。
えぇーー？北京、ぺきんってあの北京！！
北京飯店とか、そういうオチじゃないよね！！！
「例のあれ」が何かは分かりませんが、
大気汚染とか毒菜とかにヤラれませんように。
楽しんできてください。
うはー、アナーキーなググり方（笑）
どうぞお気をつけてね。
いくってわかってたらアレコレご注意申し上げたのに（爆）
てんこさん中国の真実を語ってはいけません!
私が公安に消されてしまいます。
jujuさん注意今からでも遅くありません!
生きて帰ってこれるようによろしくお願いします。
それではおそまきながら…
ミネラルウォータは、蓋がきちんとしまっているのを選んで買うように。でないと空き瓶に水道水を詰めなおしてあります。
薬は全部日本から持っていくように。日本にいる中国の人ですら、日本から買ってもって行きます。なぜならありとあらゆる病院で偽薬が渡されるから。医師の処方箋はホンモノでも、調剤でだまされる。唯一ホンモノを手に入れる方法は、薬局に親戚がいること。その人ならホンモノをだしてくれるのさ。
あとはねぇ…タクシー乗っても空気悪いし、使い捨てマスクは必携なんだけど、もうおそいよね。
ちなみにキャスターつきバッグとか買うと、３０分で壊れた記録をもつ友人がいます。
どうもありがとうございます。
何とか日本に着くまでがんばります!
自分の名前が乗っててびっくりしましたwww
ほんとladiocastなかったらラジオできなかった。nicecast買おうかact2に電話までしてたその日にladiocastのことを知ったんです。
お世話になります。
わっもう見つかってた^^;。
LadioCast、使用説明ドキュメントがちゃんと無くてもうしわけない。
昨日のVSD放送、BGMやスカイプ音声はOKな感じでした。マイクについて、おそらく2重の経路でLadioCastに入っていたと思います。どちらかの経路を閉じればよりクリアになります(残した方のボリュームはUP)。
少し高度な設定になりますが、veadarさんのブログ「Macの手書き説明書」にあるLadioCast「Skype相手にも音楽やSEが聞こえるようにするセッティング」がVSD的^^?設定例です。また余裕があれば試してみて下さい。