algorithm - 窓から猫を投げる

Question

あなたが猫のいる高層ビルにいると想像してみてください。猫は低層の窓からの落下に耐えることができますが、高層階から投げられると死にます。最小の試行回数で、猫が生き残ることができる最長の落下をどのように把握できますか？

明らかに、猫が1匹しかない場合は、直線的にしか検索できません。まず1階から猫を投げます。それが生き残った場合は、2番目から投げます。最終的に、f階から投げ出された後、猫は死にます。次に、フロアf-1が最大の安全フロアであることがわかります。

しかし、複数の猫がいる場合はどうなりますか？これで、ある種の対数探索を試すことができます。ビルドに100階があり、2匹の同じ猫がいるとします。最初の猫を50階から投げ出して死んだ場合、50階を直線的に検索するだけで済みます。あなたが最初の試みのために低い階を選ぶならば、あなたはさらに良くすることができます。一度に20階の問題に取り組むことを選択し、最初の致命的な階が＃50であるとしましょう。その場合、最初の猫は20階と40階からの飛行を生き延びてから、60階で死にます。41階から49階までを個別に確認する必要があります。これは合計12回の試行であり、バイナリ除去を使用しようとした場合に必要となる50回よりもはるかに優れています。

一般的に、2匹の猫がいるn階建ての建物にとって、最善の戦略と最悪の場合の複雑さは何ですか？n階とm猫はどうですか？

すべての猫が同等であると仮定します。それらはすべて、特定のウィンドウからの落下で生き残るか、死ぬでしょう。また、すべての試みは独立しています。猫が転倒を生き延びた場合、それは完全に無傷です。

これは宿題ではありませんが、学校の課題で一度解決したことがあるかもしれません。今日頭に浮かんだのは気まぐれな問題で、解決策を覚えていません。誰かがこの問題または解決策のアルゴリズムの名前を知っている場合、ボーナスポイント。

Answer 1

Radiolabの最近のエピソード（「Falling」について）によると、猫は9階までに終端速度に達します。その後、リラックスして怪我をする可能性が低くなります。30日以上から転倒した後、完全に無傷の猫がいます。最も危険なフロアは5階から9階です。

Answer 2

n階とm猫の一般的なケースでは、簡単に小さなDP（動的計画法）を書くことができます。

主な式はa[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n、自明である必要があります。

• 最初の猫がk階から投げ出されて死亡した場合、k - 1チェックするフロア（すべて下k）とm - 1猫（a[k - 1][m - 1]）があります。
• 猫が生き残った場合、n - k残りのフロア（上のすべてのフロアk）とまだm猫がいます。
• したがって、2つの最悪のケースを選択する必要がありmaxます。
• + 1（猫が生き残ったかどうかに関係なく）1回の試行を使用したという事実から来ています。
• 可能な限りすべてのフロアを試して、最良の結果を見つけますmin(f(k)) : for k in 1..n。

これは、 Gaurav Saxenaの（100、2）のリンクからのGoogleの結果と一致します。

int n = 100; // number of floors
int m = 20; // number of cats
int INFINITY = 1000000;

int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
    // no cats - no game
    a[i][0] = INFINITY;
}

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        // i floors, j cats
        a[i][j] = INFINITY;

        for (int k = 1; k <= i; ++k) {
            // try throw first cat from k-th floor
            int result = Math.max(a[k - 1][j - 1], a[i - k][j]) + 1;
            a[i][j] = Math.min(a[i][j], result);
        }
    }
}

System.out.println(a[n][m]);

k別の配列で 最もよく保存すれば、戦略（最初の猫を投げる方法）を簡単に見つけることができます。

O（n ^ 3）計算を含まない、より高速なソリューションもありますが、私はすでに少し眠いです。

編集
そうそう、私は以前にこの問題を見た場所を覚えています。

Answer 3

あなたが猫のいる高層ビルにいると想像してみてください。猫は低層の窓からの落下に耐えることができますが、高層階から投げられると死にます。最小の試行回数で、猫が生き残ることができる最長の落下をどのように把握できますか？

この問題を解決するための最良の戦略は、物理法則を使用して、最初にあなたの仮定が真実である確率を調査することです。

そうすれば、猫の生存の可能性は、地面までの距離が長くなるほど実際に増加することに気付くでしょう。もちろん、エベレストのようなこれまでにない高山ではなく、ペトロナスタワーなどのこれまでにない高層ビルから投げると仮定します。

編集：
実際には、未完成のラクダの配布が表示されます。
まず、猫が死ぬ確率は低く（非常に低い高度）、次に高くなり（低高度）、次に再び低くなり（高高度）、次に再び高くなります（非常に高い高度）。

地上高度の関数としての猫の死亡確率のグラフは次のようになります:(
未完成のラクダの分布のため、3で終了します）

更新：
猫の終端速度は100 km / h（60mph）[= 27.7m / s=25.4ヤード/s]です。
人間の終端速度は210km/ h（130mph）です。[= 75m / s=68.58ヤード/秒]

終端速度のソース： http：
//en.wikipedia.org/wiki/Cat_righting_reflex

クレジット：
Goooooogle

後で確認する必要があります：http：
//en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov /WWW/K-12/airplane/termv.html

Answer 4

私は最初にこの問題をStevenSkienaのアルゴリズム設計マニュアル（演習8.15）で読みました。動的計画法の章に続きましたが、戦略の正確な限界を証明するために動的計画法を知る必要はありません。最初に問題の説明、次に以下の解決策。

十分な高さから落とすと卵が割れる。n階建ての建物を考えると、f階から落ちた卵が壊れても、f-1階から落ちた卵は生き残るようにf階がなければなりません。（卵がいずれかの床から壊れた場合、f = 1と言います。卵がどの床からも生き残った場合、f = n + 1と言います）。

あなたは重要なフロアを見つけようとしますf。実行できる唯一の操作は、卵を床から落とし、何が起こるかを確認することです。あなたはk個の卵から始めて、できるだけ少ない回数だけ卵を落とそうとします。壊れた卵は再利用できません（無傷の卵は再利用できます）。E（k、n）を常に十分な卵の糞の最小数とします。

1. E（1、n）=nであることを示します。
2. それを示してE(k,n) = Θ(n**(1/k))ください。
3. E（k、n）の漸化式を見つけます。E（k、n）を見つけるための動的プログラムの実行時間はどれくらいですか？

---

たまご1個

最初から各フロアから卵をドロップすると、（最悪の場合）n回の操作で重要なフロアが見つかります。

より高速なアルゴリズムはありません。どのアルゴリズムでも、いつでも、卵が壊れないように見える最上階をgとします。アルゴリズムは、より高いフロアh> g+1の前にフロアg+1をテストする必要があります。そうしないと、卵がフロアhから壊れた場合、f = g+1とf=hを区別できませんでした。

卵2個

まず、n = r ** 2が完全な正方形である場合、k=2の卵の場合を考えてみましょう。これがO（sqrt（n））時間を要する戦略です。最初の卵をr階単位でドロップすることから始めます。最初の卵が壊れたとき、たとえばフロアarで、クリティカルフロアfはでなければならないことがわかります(a-1)r < f <= ar。次に、から始まる各フロアから2番目の卵をドロップし(a-1)rます。2番目の卵が割れるとき、私たちは重要な床を見つけました。最大でr回各卵を落としたので、このアルゴリズムは最悪の2r操作を取ります。これはΘ（sqrt（n））です。

nが完全な平方でない場合は、r=を取りceil(sqrt(n)) ∈ Θ(sqrt(n))ます。アルゴリズムはΘ（sqrt（n））のままです。

アルゴリズムが少なくともsqrt（n）時間かかることの証明。より高速なアルゴリズムがあるとします。最初の卵を落とす床の順序を考えてみましょう（壊れない限り）。ドロップはsqrt（n）よりも少ないため、少なくともn / sqrt（n）の間隔が必要です。これはsqrt（n）です。fがこの間隔にある場合、アルゴリズムは2番目の卵でそれを調査する必要があり、1卵の場合を思い出して、フロアごとに実行する必要があります。矛盾。

k個の卵

2個の卵に対して提示されたアルゴリズムは、k個の卵に簡単に拡張できます。一定の間隔で各卵を落とします。これは、nのk乗根の累乗と見なす必要があります。たとえば、n=1000およびk=3の場合、最初の卵で100階、2番目の卵で10階、最後の卵で1階の間隔を検索します。

Θ(n**(1/k))同様に、k = 2の証明から誘導することにより、より高速なアルゴリズムがないことを証明できます。

正確なソリューション

最初の卵を落とす場所（床g）を最適化することで再発を推測し、より小さなパラメーターの最適な解を知っていると仮定します。卵が壊れた場合は、下にg-1階があり、k-1個の卵で探索できます。卵が生き残った場合、k個の卵で探索するために上のng階があります。悪魔は私たちにとって最悪のものを選びます。したがって、k>1の場合は再発

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n

Answer 5

「同じ猫」を使っていると思いませんか？

数学的にアプローチすることもできますが、それは数学の良いところです...正しい仮定では、0は1に等しくなります（0の値が大きい場合）。

実用的な観点からは、「似たような猫」は入手できますが、「同じ猫」は入手できません。

経験的に答えを決定することもできますが、統計的には十分な違いがあるので、統計的に意味がないと思います。

「同じ猫」を使おうと試みることもできますが、最初のドロップの後、同じ猫ではなくなったため、それは機能しません。（同様に、同じ川に2回足を踏み入れることはできません）

または、猫の健康状態を集計し、非常に近い間隔でサンプリングして、猫が「ほとんど生きている」（「プリンセスブライド」の「ほとんど死んでいる」とは対照的）高さを見つけることができます。猫は平均して（最後の間隔まで）生き残ります。

私は当初の意図から逸脱したと思いますが、経験的なルートを進む場合は、可能な限り高い位置から始めて、統計的に生き残るまで高さが低くなるにつれて猫を落とし続けることに投票します。そして、生き残った猫を再テストして確認します。

Answer 6

少し異なる方法で解決策を作成しました。

私は、次の方法を使用して、 x匹の猫とy個の推測を使用してカバーできる最大フロアを計算することから始めました。

1階から始めて、チェックされたフロアと各フロアに残っている猫の数を追跡しながら、推測の数を増やし続けます。これをy回
まで繰り返します。

与えられた答えを計算するためのこの非常に非効率的なコードですが、それでも少数の猫/床には役立ちます。

Pythonコード：

def next_step(x, guess):
  next_x = []
  for y in x:
    if y[0] == guess:
      if y[1] != 1:
        next_x.append((guess+1, y[1] - 1))
    next_x.append(y)
    if y[0] == guess:
      next_x.append((guess+1, y[1]))
  return next_x

x = [(1, TOTAL_NUM_CATS)]
current_floor = 1
while len(x) <= TOTAL_NUM_FLOORS:
  x = next_step(x, current_floor)
  current_floor += 1
  print len(x)

2匹の猫の場合、x個の推測で識別できる最大フロアは次のとおりです：1、3、6、10、15、21、28
.. ..

3匹の猫の場合：
1、3、7、14、25、41、63 ..

4匹の猫の場合：
1、3、7、15、30、56、98 ..

広範囲にわたる調査（主にOEISへの数字シーケンスの入力を含む）の後、 xの最大フロアが区分的パターンの組み合わせに従っていることに気付きました。

2匹の猫の場合：
n <2：2 ^ n-1
n> = 2：C（n、1）+ C（n、2）

3匹の猫の場合：
n <3：2 ^ n-1
n> = 3：C（n、1）+ C（n、2）+ C（n、3）

4匹の猫の場合：
n <4：2 ^ n-1
n> = 4：C（n、1）+ C（n、2）+ C（n、3）+ C（n、4）

ここから、必要なフロア数を超えるまで、nを単純にインクリメントするという簡単なアプローチを取りました。

Pythonコード：

def find_smallest(floors, eggs):
  maximum_floors = 0
  n = 0
  while maximum_floors < floors:
    maximum_floors = 0
    n += 1
    if n < eggs:
      maximum_floors = 2**n - 1
    else:
      count = 0
      for x in xrange(1, eggs+1):
        maximum_floors += combination(n, x)
  print n

これにより、（100、2）= 14の正しい解が得られます。
ささいなことをチェックしたい人には、（1 000 000、5）=43が得られます。

これはO（n）で実行されます。ここで、nは問題の答えです（猫が多いほど良い）。
ただし、数学のレベルが高い人は、区分的式を単純化してO（1）で計算できると確信しています。

Answer 7

O(m*(n^(1/m))) algorithm.

Let 'x' be the maximum number of attempts needed.  

m = 1 => linear => x=n

m = 2:  
Let the floors be split into 'k' partitions. The first cat is thrown at the end of each partition (max 'k' times). 
When it dies, the second cat is used to go up from the beginning of this partition.   
x = k + n/k.   
Minimize x by diff wrt k and setting = 0, to get k = n^(1/2) and x = 2 * n^(1/2).

m = 3:  
x = k + 2*(y^(1/2)), where y = n/k  
diff wrt x and set = 0, to get k = n^(1/3) and x = 3 * n^(1/3)

for general m:  
x = m * n^(1/m). 

Answer 8

猫についてのこのすべてのクレイジーな話..そしてそれは最小の推測（猫の数）での数の問題を推測するだけです。解の一部として無限大を人為的に（そして誤って）定義する必要もありません。変数には、upper-boundまたはmax-tryなどの名前を付ける必要があります。問題の定義（猫のこと）にはいくつかの深刻な問題がありますが、人々は動物虐待の可能性に対応し、空気抵抗、重力は加速、その他の現実のパラメータなど、現実の生活で提起されるそのような問題の多くの側面もあります問題の。ですから、おそらくそれはまったく異なる方法で尋ねられるべきでした。