动态规划法（七）鸡蛋掉落问题（二）

偏执的太偏执、 2022-05-23 09:40 196阅读 0赞

上次我们讲到，我们的主人公丁丁由于用动态规划法解决了鸡蛋掉落问题（egg dropping problem）而获得了当地科学家的赏识。这不，正当丁丁还沉浸在解决问题的喜悦中，科学家又给丁丁出了一个难题：

> 假设有n个鸡蛋和d次尝试机会，那么，最多能探索多少层楼？

这无疑是鸡蛋问题的翻版，因为这两个问题实在太像了。丁丁没有犹豫，立马按照之前的想法开始思考：

用f(d,n)  f ( d , n ) 表示该问题的解。假设从k层楼扔下鸡蛋（k足够大），若鸡蛋碎了，则剩下n-1个鸡蛋，d-1次尝试机会，最多能向下探索f(d−1,n−1)  f ( d − 1 , n − 1 ) 层楼；若鸡蛋没碎，则剩下n个鸡蛋，d-1次尝试机会，最多能向上探索f(d−1,n)  f ( d − 1 , n ) 层楼，于是：

f(d,n)=1\+f(d−1,n−1)\+f(d−1,n).  f ( d , n ) = 1 + f ( d − 1 , n − 1 ) + f ( d − 1 , n ) .

令  g(d,n)=f(d,n\+1)−f(d,n)  g ( d , n ) = f ( d , n + 1 ) − f ( d , n )  ,则：

g(d,n)=f(d,n\+1)−f(d,n)=\[1\+f(d−1,n)\+f(d−1,n\+1)\]−\[1\+f(d−1,n−1)\+f(d−1,n)\]=\[f(d−1,n\+1)−f(d−1,n)\]\+\[f(d−1,n)−f(d−1,n−1)\]=g(d−1,n)\+g(d−1,n−1)  g ( d , n ) = f ( d , n + 1 ) − f ( d , n ) = \[ 1 + f ( d − 1 , n ) + f ( d − 1 , n + 1 ) \] − \[ 1 + f ( d − 1 , n − 1 ) + f ( d − 1 , n ) \] = \[ f ( d − 1 , n + 1 ) − f ( d − 1 , n ) \] + \[ f ( d − 1 , n ) − f ( d − 1 , n − 1 ) \] = g ( d − 1 , n ) + g ( d − 1 , n − 1 )

因为  f(0,n)=f(d,0)=0  f ( 0 , n ) = f ( d , 0 ) = 0  ,对于任意的  n,d  n , d  ，且  f(d,1)=d  f ( d , 1 ) = d  ,故  g(0,n)=0,g(d,0)=d.  g ( 0 , n ) = 0 , g ( d , 0 ) = d .  因为在组合数学中，有：

Ckn=Ckn−1\+Ck−1n−1,  C n k = C n − 1 k + C n − 1 k − 1 ,

因此，由数学归纳法可知：  g(d,n)=Cn\+1d.  g ( d , n ) = C d n + 1 .  当  n\+1≥d  n + 1 ≥ d  时，  Cn\+1d=0.  C d n + 1 = 0.  对于  f(d,n)  f ( d , n )  ,有：

f(d,n)=\+\+\+\+\[f(d,n)−f(d,n−1)\]\[f(d,n−1)−f(d,n−2)\]⋯\[f(d,1)−f(d,0)\]f(d,0).  f ( d , n ) = \[ f ( d , n ) − f ( d , n − 1 ) \] + \[ f ( d , n − 1 ) − f ( d , n − 2 ) \] + ⋯ + \[ f ( d , 1 ) − f ( d , 0 ) \] + f ( d , 0 ) .

因为  f(d,0)=0  f ( d , 0 ) = 0  ,因此  f(d,n)=∑i=1nCid,d≥1.  f ( d , n ) = ∑ i = 1 n C d i , d ≥ 1.  于是，科学家的问题就解决了。  
  突然，丁丁又想到了：能不能用这个结果来解决鸡蛋掉落问题呢？答案是肯定的，对于给定的  k=f(d,n)  k = f ( d , n )  ,只需要对d从1开始算起，得到d,恰好使得  f(d,n)≥k,  f ( d , n ) ≥ k ,  则d即可鸡蛋掉落问题的解。  
  科学家看了丁丁的解答，十分满意，他终于下定决心招丁丁为自己的助手。不过，丁丁说，他还要去外面的世界再看看，因此，科学家也没有挽留，但他祝愿丁丁好运。  
  本文不再给出相关的程序，读者可以自己实现哦~~  
  本文的参考文献为： [https://brilliant.org/wiki/egg-dropping/][https_brilliant.org_wiki_egg-dropping] 。

***注意：***本人现已开通两个微信公众号： 用Python做数学（微信号为：python\_math）以及轻松学会Python爬虫（微信号为：easy\_web\_scrape）， 欢迎大家关注哦~~

[https_brilliant.org_wiki_egg-dropping]: https://brilliant.org/wiki/egg-dropping/