Super Egg Drop
2956 ワード
一つの陳題
原因はルームメイトの携帯電話の画面を覗いて、彼のグループの中で経典の問題を聞く人がいるのを見た.
2つのそっくりのガラス球で、2つのガラス球が一定の高さから地面に落ちると割れてしまいますが、この高さ以下で投げるとどうしても割れません.今では、このちょうど割れた高さの範囲が1階から100階の間にあることが知られていますが、どのように最小限の試験回数で、この2つのガラス球でガラス球がちょうど割れたビルの高さをテストしますか?1
ボールが1つしか残っていない場合は、1層ずつ上へテストするしかない.1番目のボールの役目は2番目のボールに必要なテストの回数を減らすことである.直感的に言えば、1番目のボールのテストポイントの間隔はますます小さくなり、このように2番目のボールに必要なテスト回数が少なく、総回数が一定であることを保証することができる.
最小テスト回数を(m)、すなわち最適ポリシーの最悪テスト回数を(m)と記す.1番目のボールが(j)回目のテスト(前に砕けなかった)で(n_j)層に落下した場合が割れていない場合、(j+1)回の試験の場合、問題は(100-n_j)階の最低試験回数を求めることに帰結する. が割れると、2番目のボールは(m-j)次内在(n_j-n_{j-1}-1)階でテストを完了する.2番目のボール(m-j)回目は、最大で(m-j)階に臨界層数しか位置決めできない.
したがって、2つのボール(m)回のテストは、最大で(m+(m-1)+dots+1=m(m+1)/2)層において臨界層数を位置決めことができる.最小テスト回数は(min{minmathbb Nmidm(m+1)/2ge 100}=14)である.ポリシーは一意ではない、例えば、(n_j=m+(m-1)+dots+(m-j+1))であり、ここで(jle 11)である.
1つの自然な問題は、(k)個のガラス球がある場合、(N)層の中で臨界層数を位置決めするのに必要な最小試験回数を求める.2上記の問題と同様に、(k)個の球(m)回の試験を考慮すると、(f(k,m))層の中で臨界層数を位置決めすることができる.1番目のボールが1回目のテストで(n_1)層に落下した場合が砕けていなければ、(k)個のボールが残り、(m-1)回の機会があり、せいぜい上の(f(k,m-1))層の中で臨界層数を位置決めすることができる. が割れると、(k-1)個のボールが残り、(m-1)回の機会が多く、下の(f(k-1,m-1))階で臨界層数を位置決めすることができる.
したがって
\[ f(k, m) = f(k, m-1) + 1 + f(k-1, m-1),\]
境界条件(f(0,m)=f(k,0)=0)、あるいは(f(1,m)=m)、(f(k,1)=1)である.
この形は自然に組み合わせ数の繰返しを思い出させる
\[\frac{m(m-1)\cdots (m-n+1)}{n!}=\begin{pmatrix}m\\end{pmatrix} =\begin{pmatrix}m-1\\end{pmatrix} +\begin{pmatrix}m-1\-1\end{pmatrix}.\]
だから何とかしてプッシュ式の1を取り除く.First attemptは、表記(g(k,m)=f(k,m)+1)であるが、このような境界条件は異なる.試行(g(k,m)=f(k,m)-f(k,m-1))の境界条件も間違っている.表記(g(k,m)=f(k,m)-f(k-1,m))の場合
\[ g(k,m) = g(k, m-1) + g(k-1, m-1),\]
今回の境界条件は、(g(1,m)=m),(g(1,1)=1),(g(k,1)=0)for(k>1)である.わかりやすい
\[ f(k,m) =\sum_{x=1}^k g(x,m) + f(0,m) =\sum_{x=1}^k\begin{pmatrix}m\\x\end{pmatrix}.\]
そこで(k)個のボール(N)階で、最低テスト回数は(min{mmid f(k,m)ge N})である.
アルゴリズム時間複雑度(O(klog N))、空間複雑度(O(1)).
ガラス球が割れなければ、臨界層数(最低割れ階)は変わらないという意味だ.1つのポリシー(Scolonmathbb Ntomathbb N)が与えられ、(S(n))は臨界層数が(n)である場合、そのポリシーがテストする必要がある回数を表し、最小テスト回数は(displaystylemin_Smax_n S(n))である.↩
調べてみると、LeetCode 887にこの問題があります.↩
転載先:https://www.cnblogs.com/shiina922/p/11516507.html
100階建ての2つのガラス玉
原因はルームメイトの携帯電話の画面を覗いて、彼のグループの中で経典の問題を聞く人がいるのを見た.
2つのそっくりのガラス球で、2つのガラス球が一定の高さから地面に落ちると割れてしまいますが、この高さ以下で投げるとどうしても割れません.今では、このちょうど割れた高さの範囲が1階から100階の間にあることが知られていますが、どのように最小限の試験回数で、この2つのガラス球でガラス球がちょうど割れたビルの高さをテストしますか?1
ボールが1つしか残っていない場合は、1層ずつ上へテストするしかない.1番目のボールの役目は2番目のボールに必要なテストの回数を減らすことである.直感的に言えば、1番目のボールのテストポイントの間隔はますます小さくなり、このように2番目のボールに必要なテスト回数が少なく、総回数が一定であることを保証することができる.
最小テスト回数を(m)、すなわち最適ポリシーの最悪テスト回数を(m)と記す.1番目のボールが(j)回目のテスト(前に砕けなかった)で(n_j)層に落下した場合
したがって、2つのボール(m)回のテストは、最大で(m+(m-1)+dots+1=m(m+1)/2)層において臨界層数を位置決めことができる.最小テスト回数は(min{minmathbb Nmidm(m+1)/2ge 100}=14)である.ポリシーは一意ではない、例えば、(n_j=m+(m-1)+dots+(m-j+1))であり、ここで(jle 11)である.
(N)フロア(k)個のガラス玉
1つの自然な問題は、(k)個のガラス球がある場合、(N)層の中で臨界層数を位置決めするのに必要な最小試験回数を求める.2上記の問題と同様に、(k)個の球(m)回の試験を考慮すると、(f(k,m))層の中で臨界層数を位置決めすることができる.1番目のボールが1回目のテストで(n_1)層に落下した場合
したがって
\[ f(k, m) = f(k, m-1) + 1 + f(k-1, m-1),\]
境界条件(f(0,m)=f(k,0)=0)、あるいは(f(1,m)=m)、(f(k,1)=1)である.
この形は自然に組み合わせ数の繰返しを思い出させる
\[\frac{m(m-1)\cdots (m-n+1)}{n!}=\begin{pmatrix}m\\end{pmatrix} =\begin{pmatrix}m-1\\end{pmatrix} +\begin{pmatrix}m-1\-1\end{pmatrix}.\]
だから何とかしてプッシュ式の1を取り除く.First attemptは、表記(g(k,m)=f(k,m)+1)であるが、このような境界条件は異なる.試行(g(k,m)=f(k,m)-f(k,m-1))の境界条件も間違っている.表記(g(k,m)=f(k,m)-f(k-1,m))の場合
\[ g(k,m) = g(k, m-1) + g(k-1, m-1),\]
今回の境界条件は、(g(1,m)=m),(g(1,1)=1),(g(k,1)=0)for(k>1)である.わかりやすい
\[ f(k,m) =\sum_{x=1}^k g(x,m) + f(0,m) =\sum_{x=1}^k\begin{pmatrix}m\\x\end{pmatrix}.\]
そこで(k)個のボール(N)階で、最低テスト回数は(min{mmid f(k,m)ge N})である.
class Solution:
def superEggDrop(self, k: int, N: int) -> int:
def f_k(m):
# if f(k, m) >= N, return True; else False
result = 0
c = 1
for x in range(1, k+1):
c = c * (m-x+1) / x # combinatorial number C_m^x
result += c # f(x, m)
if result >= N:
return True
return False
# binary search
left, right = 1, N
while left < right:
mid = (left + right) // 2
if f_k(mid):
right = mid
else:
left = mid + 1
return leftアルゴリズム時間複雑度(O(klog N))、空間複雑度(O(1)).
ガラス球が割れなければ、臨界層数(最低割れ階)は変わらないという意味だ.1つのポリシー(Scolonmathbb Ntomathbb N)が与えられ、(S(n))は臨界層数が(n)である場合、そのポリシーがテストする必要がある回数を表し、最小テスト回数は(displaystylemin_Smax_n S(n))である.↩
調べてみると、LeetCode 887にこの問題があります.↩
転載先:https://www.cnblogs.com/shiina922/p/11516507.html