信科算法課課后思考題

https://wenku.baidu.com/view/7c9de809581b6bd97f19ea72.html

鷹蛋問(wèn)題
兩顆蛋:考慮sqrt(n)的方式逐個(gè)扔蛋
M顆蛋,N層樓:
(1)動(dòng)態(tài)規(guī)劃,O(MNN)=O(N3)
f(i,j) = min{max(f(i-1, w-1), f(i, j-w))|1<=w<=j} + 1
(2)優(yōu)化,當(dāng)M>log2(N),使用二分法最壞情況下的最小次數(shù)必然是log2(N+1);故只需考慮M<=log2(N)的情況,復(fù)雜度降低為O(N2logN)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡(jiǎn)書(shū)系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • "use strict";function _classCallCheck(e,t){if(!(e instanc...
    久些閱讀 2,142評(píng)論 0 2
  • 一年級(jí)語(yǔ)文上冊(cè)生字表 生字表一(共400字) 啊(ā)愛(ài)(ài)安(ān)岸(àn)爸(bà)八(bā)巴(bā)...
    meychang閱讀 3,153評(píng)論 0 6
  • 在C語(yǔ)言中,五種基本數(shù)據(jù)類(lèi)型存儲(chǔ)空間長(zhǎng)度的排列順序是: A)char B)char=int<=float C)ch...
    夏天再來(lái)閱讀 4,038評(píng)論 0 2
  • 常見(jiàn)數(shù)據(jù)類(lèi)型的公共方法 python包含以下常見(jiàn)內(nèi)置函數(shù) 索引和切片 運(yùn)算符 各數(shù)據(jù)類(lèi)型獨(dú)有的函數(shù) 1.字符串的常...
    南城不寒冷閱讀 256評(píng)論 0 0
  • “鹿鳴先生回來(lái)了!”童子向老者稟報(bào)。老者捋著胡子微微一笑,瞥了一眼公子縶,言下之意我沒(méi)騙你吧? 公子縶慌忙起身迎接...
    原瘋不動(dòng)閱讀 853評(píng)論 1 6

友情鏈接更多精彩內(nèi)容