溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1.有1棟100層高的樓和兩顆玻璃球。在一定的高度摔下玻璃球將會摔碎。請給定一個方法來確定玻璃球摔碎的臨界樓層。并說明該方法的最好情況，最差情況以及方法的復雜度（樓層為N層時）。
分析：由于只有兩個球，那么二分法、三分法就不行了，比如在50層丟一個，被摔壞。然后在25層丟另外一個，同樣被摔壞，此時根本無從找到問題答案。
其次想到的是分段，用第一個球尋找損壞區間，然后用第二球去遍歷那個區間去尋找損壞層。
假定最優區間長度是x，則第一步最多要摔100/x次，第二步最多摔x-1次，問題轉換為求100/x+(x-1)的最小值。
具體描述：以10層樓為一個區間，先摔第一個，以確定摔壞的區間，然后再用另一個在這個區間內從最低的樓層摔，從而找到所要求層數，這種方法最多要摔19次。
然而這種等長區間也是有問題，第一次我們需要判斷的范圍是100，然而摔下第一個球的時候，判斷區間就改變了，如果碎了，那么就進入第二個步驟了。如果沒有碎，那么需要判斷的區間就變成了x+1到100。由于他的區間變小，應該可以有更優的選擇，而不適宜沿用之前的定長區間。
假設最終需要測試的次數的為x，我們在x樓層摔下第一個玻璃球，球摔壞了，那么最多需要的樓層為1到x-1，即總測試次數為1+（x-1）=x
如果球未損壞，那么我們的測試范圍變成了x+1層到100層，即測試范圍減少了x層。
當我們再次摔下第一個球的時候，為了保證最終的測試次數為x，那么需要增長x-1,即為x+x-1層。
如果還沒有摔壞，那么為了保證最終的結果仍為x，那么我們需要增長x-2，即為x+（x-1）+（x-2）層。
以此類推，直到增長區間為1時，由于我們設定這個x為最差情況，因此最終可搜索的樓層是可能超過100層的，即x+（x-1）+（x-2）+（x-3）....+1>=100。
到此我們終于明白了，這不是等差數列嗎，等差數列公式是（首項＋末項）×項數÷2，那么可以得到
（x+1）*x/2 >=100，由此我們求的x最小值為14。
具體描述：
先從14層扔（碎了試1-13）
再從27層扔（碎了試15-26）
再從39層扔（碎了試28-38）
再從50層扔（碎了試40-49）
再從60層扔（碎了試51-59）
再從69層扔（碎了試61-68）
再從77層扔（碎了試70-76）
再從84層扔（碎了試78-83）
再從90層扔（碎了試85-89)
再從95層扔（碎了試91-94）
再從99層扔（碎了試96-98）
最后從100層扔
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
