は私が次に何をすべきか分からない（と私のアプローチが正しいとしても）、以下のような問題にアルゴリズムの擬似コード生成

Question

でスタック：

Part 1 Part 2

私はちょうど可能MNTことを考え出しました（部分aのために）瓶を得ることです、それが高さhから壊れているかどうかをテストします。そうであれば答えがあります。

パートbについては、次のとおりです。最大高さがnに等しいことが分かっているので、n（現在の高さ= n）から始まります。したがって、私たちは上から下へ、瓶が壊れるのを止めるまで、壊れた瓶の数を加えます（あなたが上から始めると壊れるはずです）。その場合、数値は現在の高さ+ 1になります（1つのインデックスに戻る必要があるため）。

cの部分については、アルゴリズムの順序がO（n^c）であると仮定しているので、私のアプローチは何か分かりません。ここでcは分数です。私はまた、O（n^c）がO（n）よりも速いことも知っています。

私はまた、オンラインでこれに似た問題があることに気づきましたが、ロボットアームの代わりにラングについて話しました。多分それは似ていますか？ここにはlink

あなたは何か推奨事項がありますか？どんな助けもありがとう。

ご利用いただきありがとうございます。

乾杯！

Answer 1

（a）の部分では、高さを超えてバイナリ検索を使用できます。

lo = 0 
hi = n 
while(lo<hi) { 
    mid = lo +(hi-lo)/2; 
    if(galss_breaks(mid)) { 
     hi = mid-1; 
    } else { 
     lo = mid; 
    } 
} 

「lo」は可能な限り最小限の試行で可能な最大高さを含みます。ワーストケースではlog（n）ステップが必要ですが、ワーストケースではNステップかかる場合があります。一部については

（b）は、

あなたは、あなたのアプローチaを使用して最小の高さから開始し、ガラス破断するまで1によって高さを増やすことができます。これは、必要な高さを決定するために、たいてい1枚のガラスを割ることになります。

Answer 2

これはパート（c）の回答です。 アイデアはいくつかの数kを見つけ、次のスキームを適用することです： 落下高さkからjarファイル：

• それが壊れた場合、我々はその高さを見つけるまで、1までのk-1から他の1をドロップそれはk回の試行で壊れてしまいます。
• 破損していない場合は、高さk +（k-1）から再度落としてください。もう一度、（k +（k-1）-1）からk + 1に降下した場合は、（k +（k-1）+（k-2））に進む。
• あなたは高さ

見つけるまで（もちろんのをあなたはnより大きい高さにジャンプする必要がある時点で、あなただけのnにジャンプしている場合）、これを続けます。

この方式では、最大でk回試行します。だから問題は最小のk（nの関数として）を見つける方法です。すべてのステップで、高さが1増加するので、次の式が成立する必要があります。
k +（k-1）+ ... + 1> = n
nに達する前にステップの「出る」。不等式が成立する最小のkを求めたい。 合計に式があります：

1 + 2 + ... + K = K（K + 1）/ 2

我々は方程式を得ることを使用：

kは（ K + 1）/ 2 = N ===>K^2 + K - 2N = 0

これを解くと（そして、それは不可欠ではない場合、私たちは、kを与えるだろう）、それの天井を取ります。二次方程式の2つのソリューションを持っていますが、あなたが得る負の1を無視可能性があります

K =（-1 + SQRT（1 + 8N））複雑探し/ 2

を、私たちは、しかし、すべてを無視することができますnの指数は1/2です（私たちは平方根を取っているからです）。実際には、nの2/3乗の要求された複雑さよりも優れています。