エントリービルゲイツの面接試験ネタに便乗に便乗の金貨問題で出した問題の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回の計量で選別できるということです(プログラムが正しければ^^)。
う〜ん興味深いですね〜。
Scatmanです。お世話になっております。
早速の対処ありがとうございます。クラッシュする事なく送信する事が
できる様になりました。感謝します。
mp3モードでの送出テストは私のiBook G4では問題はありませんでしたが、
Ogg Vorbisモードでのねとらじへの送出テストが全くできない状態です。
送出設定をして「送出する」ボタンを押下しても
「接続に失敗しました(Login Failed)」旨のダイアログが出てきて、ねとらじサーバーに接続できません。
申し訳ありまあせんが、確認をお願い致します。
レポートありがとうございます!
Ogg Vorbis形式はねとらじにはつなげられないと思います。確かなことはわかりませんが、Ogg Vorbisでつなぎますと宣言してつないでくるクライアントに対して、ねとらじサーバーは意識的にはじいているように思います。(ローカル環境での検証からの推察)
Scatmanです。お世話になっております。
ねとらじのOgg Vorbisの件なんですが、ちょっと気になって調べてみました所、ねとらじではOgg Vorbisに対応していない事が分かりました。
以下のブログを見て下さい。
「livedoorネットラジオ / ねとらじ開発日誌」
http://blog.livedoor.jp/ladio_staff/archives/2005-06.html
ここに、2005年3月に試験的に導入していたOgg Vorbisの接続ができなくなる旨の書き込みがありました。と言う事はこれ以降はOgg Vorbisでの接続は非対応と言う事になります。
よく調べもせずに書き込んでしまいまして申し訳ありませんでした。
ScatmanさんOgg Vorbisの情報ありがとうございます!