ここから本文です

数学クイズ

suf********さん

2008/6/2212:53:59

数学クイズ

友人から出されたクイズ(論理クイズ)が分かりません。

【問題】
ある特殊なボールがあって、一定の高さから落とすと割れる構造になっています。
例えばビルの23階から落としても割れないが、24階から落とすと割れるといった感じです。

その特殊なボールが割れる高さが分かっておらず、100階立てのビルを使ってその割れる
高さを調べることになりました。そのボールを2つ使って、効率よくその高さを割り出す方法と、
その場合何回落とすだけで済むのか?一度割れたボールは再利用できません。また、
各階を移動する手間というのは考えないものとする。

というのが問題です。ボールが1個の場合は1階から順に2階、3階、・・・99階、100階と
やって、2階で割れれば2回で済みますが、最悪のケースでは100階まで調べなくては
なりません。2個ある場合は、例えば50階から落として、割れれば1階から順に49階
まで残ったボールで調べることで最悪でも50回で済みますし、50階で割れなければ
51階から上の階を調べるだけで済みます。どうやらうまく分割して調べていくようなのですが、
どうすれば解答に辿り着けるでしょうか?

また一般化して、N階立てのビルで調べる際に必要最低限のn回はどうすれば求まるでしょうか?

閲覧数:
2,731
回答数:
6
お礼:
25枚

違反報告

ベストアンサーに選ばれた回答

bot********さん

編集あり2008/6/2213:50:16

逆にn回の試行しか許されていないときの調べられるビルの高さを計算したほうがよいようです。
n回しか許されていないので、n階ではじめトライします。失敗したら残りで1~n-1階をしらみつぶしです。
1stトライで成功したら、残り回数はn-1回なので、n-1階高い n+(n-1)階でトライ。。。。
すると、Σk=n(n+1)/2階まで上れるのではないでしょうか。

ということは、100階なら、14回ですむようです。

質問した人からのコメント

2008/6/23 00:16:18

成功 なるほど、逆転の発想で「逆にn回の試行しか許されていないときの調べられるビルの高さ」
を調べるんですね。友人に確認したら、その通りの解答でした。

問題にあやふやな点があったかもしれませんが、題意を汲み取っていただけて
ありがとうございます。

一般化すると2N<n(n+1)が成立する最小のnということになるかと思います。

バイナリ・サーチ、今回の問題では使えませんが勉強になりました。

ベストアンサー以外の回答

1〜5件/5件中

並び替え:回答日時の
新しい順
|古い順

m47********さん

編集あり2008/6/2218:23:14

//参考までに・・・・
.
原理自体は分数の足し算より簡単!!

バイナリ・サーチ(二分探索)
.
まず真ん中の値をチェックして、それより大きいか小さいかを判断する。
大きければ、小さかったほうの探索はもうしない。次に大きいほうの配列
の真ん中の値をチェック・・・と半分>半分>半分と絞り込んでいく方法

・データが並んでいるとき使える。(小さい順、または、大きい順)
・最大のメリットはデータ件数(ビルの階数が)が2倍になっても
....探す回数(ボールの個数)は1回(端数により基本的に)しか増えなくて済むこと。

.
http://www.h3.dion.ne.jp/~unisoft/tiny002.html
.
http://www5c.biglobe.ne.jp/~ecb/algorithm/6_3.html
.

s_h********さん

2008/6/2214:25:35

ボールの数がいくつでもいいならN階を調べるのに
2^n>Nとなるn回でいいはずです。最小のボールの個数も同じ。
1回落とすとその階より上か下かがわかります(2つに分割できる)
ということはボール一つで2分割、二つで4分割・・・三つで8分割となります。
結局2^n分割>ビルの階数です。(もしかしたら最終確認で+1が必要かもしれない)

常に残った部分の真ん中でボールを落とすようにします。
50階でやって割れなければ75階、割れれば25階というように

もしボールの数に制限がある場合はわかりません。
100階なら2^7=128なのでたぶん7個です。

ふゆきたさん

2008/6/2213:04:23

ボールが二個しかないのでしたら、ひとつで高さの特定・もうひとつで範囲の特定。

>例えば50階から落として、割れれば1階から順に49階
>まで残ったボールで調べることで最悪でも50回で済みますし、50階で割れなければ
>51階から上の階を調べるだけで済みます

この答えしかないと思います。

また、

>必要最低限のn回

これは、文章の意味通りなら2回です。
一回目と二回目の高さを一階差にして運良く当たりを引いた場合は 「 最低回数 」 となります。

このような場合で意味のある数字は、「 最大試行回数 」 もしくは 「 期待値 」 だと思います。

e30********さん

2008/6/2213:01:51

わからん、逆に教えてくれ。

紅玉恭さん

2008/6/2212:59:18

まずn/2の高さで落としてみる。
割れればその半分より上か下かのどこか。
もし、割れなかった場合は3n/4で割れたらn/4…と繰り返せばそのうちヒットする。
回数的には最大n/2回

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる