題目原文：

Suppose that you have an n-story building (with floors 1 through n) and plenty of eggs. An egg breaks if it is dropped from floor T or higher and does not break otherwise. Your goal is to devise a strategy to determine the value of T given the following limitations on the number of eggs and tosses:

• Version 0: 1 egg, ≤T tosses.
• Version 1: ～1lgn eggs and ～1lgn tosses.
• Version 2: ～lgT eggs and ～2lgT tosses.
• Version 3: 2 eggs and ～2$ \sqrt{n} $?tosses.
• Version 4: 2 eggs and ≤c$ \sqrt{T} $?tosses for some fixed constant c

分析：

version0 ： 拿著一個(gè)雞蛋從1~n依次扔就可以，到floor T會(huì)碎，故復(fù)雜度為≤T

version 1: ?采用二分查找，首先從n/2層開(kāi)始扔:

　　　　　　if(雞蛋碎) 從(n/2)/2層開(kāi)始扔；

　　　　　　else 從n/2+(n/2)/2層開(kāi)始扔

　　　　　二分方法需要lgn個(gè)雞蛋嘗試lgn次

version 2: 依次從1, 2, 4, 8, 16, 32,...2^k開(kāi)始扔，如果雞蛋在2^k碎了，那么2^k-1≤T≤2^k，這時(shí)已經(jīng)使用了 lgT 次步，接下來(lái)在[2^k-1+1,2^k）區(qū)間進(jìn)行version1的二分查找方法，需要花費(fèi)lgT步。這兩種操作加起來(lái)總共花費(fèi)2lgT步

version 3: 將0~n層樓分成[1,?$ \sqrt{n} $-1], [$ \sqrt{n} $, 2?$ \sqrt{n} $-1], [2$ \sqrt{n} $,3?$ \sqrt{n} $-1]...[k$ \sqrt{n} $, (k+1)$ \sqrt{n} $-1]..個(gè)區(qū)間，用一個(gè)雞蛋分布從1開(kāi)始在各個(gè)區(qū)間的起始樓層扔，如果在k$ \sqrt{n} $層碎了，那就從(k-1)$ \sqrt{n} $+1開(kāi)始逐層扔。第一步區(qū)間選擇用了?$ \sqrt{n} $的復(fù)雜度，第二步區(qū)間內(nèi)部扔雞蛋用了?$ \sqrt{n} $的復(fù)雜度，總共用了?2$ \sqrt{n} $

version 4: 嘗試從1, 4, 9, 16, 25,...(k-1)², k²....樓層扔雞蛋，加入雞蛋在樓層k²碎了，意味著(k-1)²≤T≤k²，這一步嘗試了$ \sqrt{T} $次(k=$ \sqrt{T} $)。接著從樓層(k-1)²+1開(kāi)始逐層扔，最多嘗試至k²-1結(jié)束，這一步需要嘗試k²-1-(k-1)²-1=2$ \sqrt{T} $-1=2$ \sqrt{T} $-2次。總共用了3$ \sqrt{T} $-2次

?

轉(zhuǎn)載于:https://www.cnblogs.com/evasean/p/7208986.html

總結(jié)

以上是生活随笔為你收集整理的Coursera Algorithms week1 算法分析 练习测验: Egg drop 扔鸡蛋问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。