古典的なプログラミングのインタビューの質問の 1 つ...
あなたは 2 つのビー玉を与えられ、特定の高さから落とすと壊れると言われます (おそらく、その高さより下から落としてもダメージを受けないでしょう)。次に、100 階建ての建物 (おそらく特定の高さよりも高い) に連れて行かれ、ビー玉をできるだけ効率的に壊さずに落とすことができる最上階を見つけるように求められます。
追加情報
The interesting thing here is how you can do it in the least amount of drops possible. Going to the 50th floor and dropping the first would be disastrous if the breaking floor is the 49th, resulting in us having to do 50 drops. We should drop the first marble at floor n, where n is the max amount of drops required. If the marble breaks at floor n, we may have to make n-1 drops after that. If the marble doesn't break we go up to floor 2n-1 and if it breaks here we have to drop the second marble n-2 times in the worst case. We continue like this up to the 100th floor and try to break it at 3n-2, 4n-3....
and n+(n-1)+(n-2)+...1 <=100
n=14 Is the maximum drops required
同じ高さから落とすとそれぞれ壊れますか、それとも違いますか?
同じなら50階に行き、最初のビー玉を落とす。壊れなければ75階に行って同じことをし、壊れない限り残りの50%ずつ上げていきます。壊れたら、以前よりも 1 つ上の階に戻り (75 階で壊れた場合は 51 階に戻ります)、2 つ目のビー玉を落として、壊れるまで 1 階ずつ上に移動します。その時点で、大理石の破損なしにドロップできる最高階がわかります。
ベストアンサーではないかもしれませんが、他の方の回答が気になります。
I think the real question is how accurate do you want the answer. Because your efficiency is going to really depend on that.
I'm going to agree with Justin if you want 100% accuracy on the marbles then once the first marble breaks your going to have to go up 1 floor at a time from the last known "good" floor until you find out which floor is the "winner." Maybe even throw in some statistics and start at the 25th floor instead of the 50th floor so that you're worst case scenario would be 24 instead of 49.
If you're answer can be plus or minus a floor or two then there could be some optimizations.
Secondly, does walking up/down the stairs count against your efficiency? In that case always drop both marbles and pick up both marbles on every up/down trip.
最初のビー玉を 10、20、30 などの階に落として壊れるまで落としてから、最後に確認された良好な階に戻り、そこから一度に 1 階ずつビー玉を落とし始めます。最悪の場合、99 が Magic Floor であり、常に 19 ドロップ以下で見つけることができます。
個人的には、このような謎解きの質問はあまり好きではありません。面接で実際にプログラミングの演習を行う方が好きです。
とはいえ、まず、落としている床から壊れているかどうかを判断できるかどうかにかかっています。できると思います。
2階に上がり、最初のビー玉を落とします。壊れたら1階にしようと思います。それが壊れたら、それは床ではないことがわかります。
最初が壊れていなければ、4階に行ってそこから降ります。それが壊れたら、私は戻って別のビー玉を手に入れ、3階に落ちて、壊れるかどうかで、どこが限界かがわかります。
どちらも壊れていない場合は、両方を入手して、今度は6階から同じプロセスを実行します.
このようにして、ビー玉が壊れるまで、1 つおきのフロアをスキップできます。
これは、ビー玉が早く壊れた場合に最適化されます...各スキップで最大限にスキップできる最適な数のフロアがおそらくあると思います...しかし、1つ壊れた場合は、各フロアを個別にチェックする必要があります最後の既知の階の上の 1 階から... もちろん、あまりにも多くの階をスキップした場合は苦痛になります (申し訳ありませんが、今は最適な解決策を見つけ出すつもりはありません)。
理想的には、ビー玉が 1 袋丸ごと必要な場合は、二分探索アルゴリズムを使用して、落下ごとに階数を半分に分割できます... しかし、それは問題ではありませんでしたね?
Nフロア（あなたの場合はN = 100）の結果を与える一般的なソリューションが必要な場合は、二次方程式$x^2+x-2\cdot(N-1)=0$と結果は正の根の天井です。
それは次のとおりです。
$$f(N)=天井\bigg(\frac{-1+\sqrt{1+4\cdot2\cdot(N-1))}}{2}\bigg)$$
3階から最初の大理石を落とします。壊れた場合は、1階または2階であることがわかっているので、もう1つの大理石を2階から落とします。壊れていない場合は、2階が最も高いことがわかります。壊れた場合は、1階が最も高いことがわかります。2滴。
3階から落としても大理石が壊れない場合は、6階から落とします。壊れた場合は、4階または5階が最も高いことがわかります。5階から2番目の大理石を落とします。壊れない場合は、5が最も高いことがわかります。もしそうなら、4階が最高です。4滴。
継続する。
3フロア-最大2滴
6階-最大4滴
9階-最大6滴
12階-最大8滴
等
3xフロア-最大2xドロップ
したがって、99階建ての建物の場合、最大66滴になります。そしてそれが最大です。あなたはおそらくそれよりも滴が少ないでしょう。ああ、そして66は100階建ての建物の最大値でもあります。休憩フロアが98階または97階の場合、必要なのは66滴だけです。休憩階が100の場合、34滴を使用します。
それは問題ではないと言ったとしても、これはおそらく最小限の歩行で済み、建物の高さを知る必要はありません。
問題の一部は、効率をどのように定義するかです。常にx滴未満で解を得る方が「効率的」ですか、それともy <xで、x滴を超える可能性があるという警告とともにy滴で解を得る可能性が高い方が効率的ですか。 ？
私が最初に行うことは、フロア 1 から開始してビー玉を一度に 1 フロアずつ落として、100 に達するかビー玉が壊れるという非常に単純なアルゴリズムを使用することです。
次に、誰かがそれが問題になることを示すことができるまで、なぜ時間をかけて最適化する必要があるのか を尋ねます。はるかに単純なアルゴリズムで問題を解決できるのに、完璧で複雑なアルゴリズムを見つけることに夢中になっている人があまりにも多くいます。つまり、必要になるまで最適化しないでください。
これは、もぐらの丘から山を作ることができる人かどうかを確認するためのひっかけ問題かもしれません。