応援しているぞ!ｗｗｗ (このエントリーは謎の公開励ましの言葉です^^)

エントリービルゲイツの面接試験ネタに便乗に便乗の金貨問題で出した問題の2問目は、エントリー金貨問題の解答編で可能であることだけ書いて力技での検証をしませんでした。問題を要約すると

正規品10グラムの金貨が24枚入った6袋中、何袋あるかわからない全て偽造品11グラムの金貨の袋を、1回だけの計量で選別する方法があるか

です。

ちょうど今ものにしようとしているプログラミング言語Rubyの題材として適当そうですので、プログラムを作って本当にそんなことが可能かどうか検証してみます。 (なお組み合わせを生成する部分は書籍Rubyプログラミング入門の「第8章 Rubyスクリプト実例集」のコードを参照しました。yieldの再帰が巧みですね。)

まず以下の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回の計量で選別できるということです(プログラムが正しければ^^)。

う〜ん興味深いですね〜。

本日の北京は終日曇天で、過ごしやすい気温でした。 立つ日の朝に荷造りしたので、いろいろなものを日本に忘れてきてしまいました。 本日、天安門や故宮のパノラマ写真ややばい写真を撮りまくったのですが、カードリーダーを持ってこなかったのでブログにアップできません。いや本当に忘れたんです! そのかわりというわけではありませんが、日本から風邪を持ち込みました。それでずっと喉がいがらっぽいです。いや本当に日本の風邪なんです! 不運もあれば運もあります。中国の地下鉄が(ごく最近?)ICカードでの改札(日本でいうSUICAやPASMO)を導入したようです。切符の自動販売機すらないのに大胆ですね^^。しかしそのおかげで中国語を使うことなく地下鉄に乗れます。これは旅行者には助かります。個人的に交通 ICカードのコレクションも増えるし。 いやしかしとにかく街に人が多い。人大杉。