この質問は「プログラミングのインタビューの要素」からのもので、数日間私を困惑させました。与えられたCのケースとDの許容されるフロアの最大床数
質問には、「CケースとD許容ドロップを考慮すると、最悪ケースでテストできるフロアの最大数はいくらですか?
仮定は以下の通りである:
1)全てのケースが同じ特性を有し、レベルからの1つ破損した場合、そうであろう他のすべて
2)落下を存続する場合は、再び使用されるが、破壊されてもよいです1つは破棄されます
3)落下時にケースが破損した場合、上の床から落下した場合にケースが破損します。それが生き残れば、それはより短い秋に生き残るだろう。
私には、この質問は、滴の数を最小限に抑えようとしている「一般化された2つの卵の問題」の変形のようです。 この問題は、決められた数のドロップがある場合、フロアの数を最大限にしようとします。
溶液で与えられる再帰関係は、以下である: - + 1 + F
F(C + 1、D)= F(1 C、D)(C + 1、D - 1)
ここで、F(c、d)= max#floorは、w/cケースとd dropsをテストできます。 この繰り返しの関係は、フロアF(c、d - 1)+ 1でテストしたときにケースが壊れない場合、右の項がフロアであるという本の説明にもかかわらず、私を混乱させています。ケースが壊れたときの原因は何ですか?これは反復関係には現れません。
質問には、O(c)スペースで同じ問題を解決する追加質問があります。上記の漸化関係を実装することは、当然、2Dメモマトリックスを用いた動的プログラミングにつながる。あなたは1Dアレイでこれをどうやって行いますか?
(式中
F(c, d - 1)
対応)、それはF. – stark