




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、期末總結(jié)基礎(chǔ)知識點(diǎn),1、概念(見教材) 2、漸進(jìn)分析 例題:寫出下列函數(shù)之間的大O、大或關(guān)系。,期末總結(jié)基礎(chǔ)知識點(diǎn),3、用展開法求解下列遞歸方程,將結(jié)果表示成大O形式。,1、最大子段和問題:最大子段和問題:給定由n個(gè)整數(shù)組成的序列(a1, a2, , an)(可能有負(fù)數(shù)),最大子段和問題要求該序列形如ai+aj的最大值(1ijn)。分別用蠻力法和分治法設(shè)計(jì)求解最大子段和問題,寫出算法的偽代碼描述,并分析每種方法的漸進(jìn)復(fù)雜性。 參考解答:(蠻力法) 時(shí)間復(fù)雜性:O(n2),期末總結(jié)算法設(shè)計(jì),2、設(shè)計(jì)分治算法求一個(gè)數(shù)組中最大元素的位置,建立該算法的遞推式并求解。(課后題P74,5) 參考解答:,期
2、末總結(jié)算法設(shè)計(jì),期末總結(jié)算法設(shè)計(jì),3、在一個(gè)序列中出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。請?jiān)O(shè)計(jì)分治算法尋找眾數(shù)并分析算法的時(shí)間復(fù)雜性。 (課后題P75,10) 參考解答(時(shí)間復(fù)雜性略):,期末總結(jié)算法設(shè)計(jì),4、設(shè)M是一個(gè)nn的整數(shù)矩陣,其中每一行(從左到右)和每一列(從上到下)的元素都按升序排列。設(shè)計(jì)分治算法確定一個(gè)給定的整數(shù)x是否在M中,并分析算法的時(shí)間復(fù)雜性。 (課后題P75,11,算法略),期末總結(jié)算法設(shè)計(jì),5、修改下面的折半查找算法,使其正確進(jìn)行查找。并設(shè)計(jì)寫出折半查找的遞歸形式算法,分析時(shí)間性能。(解答略) int BinSearch(int r, int n, int k) int low=
3、0, high=n-1; int mid; while(lowrmid) low=mid; else return mid; return 0; ,期末總結(jié)算法設(shè)計(jì),6、修改折半查找算法,使之能夠進(jìn)行范圍查找。所謂范圍查找是要找出在給定值a和b之間的所有元素(ab)。參考解答(復(fù)雜性分析略):,期末總結(jié)算法設(shè)計(jì),7、請寫出背包問題的貪心算法偽代碼描述,并進(jìn)行時(shí)間復(fù)雜性分析。并用貪心法求解下列背包問題:有7個(gè)物品,重量分別為(2,3,5,7,1,4,1),價(jià)值分別為(10,5,15,7,6,18,3),背包容量W=15,要求寫出求解過程(P146,1)。 (參考解答略。),期末總結(jié)算法設(shè)計(jì),8、
4、請寫出活動安排問題的貪心算法偽代碼描述,并進(jìn)行時(shí)間復(fù)雜性分析。并求解下列活動安排問題:有11個(gè)活動等待安排,這些活動的起止時(shí)間如下表所示,要求寫出求解過程。(參考解答略),期末總結(jié)算法設(shè)計(jì),9、設(shè)計(jì)用回溯法求解0/1背包問題的剪枝函數(shù),并給出相應(yīng)算法的偽代碼描述。 參考解答:,剪枝函數(shù) 設(shè)搜索至第i層,背包容量為c,當(dāng)前獲得的物品重量為cw,當(dāng)前獲得的價(jià)值為cv,當(dāng)前獲得的最大價(jià)值為bestv。 左子樹:用約束函數(shù)剪枝,當(dāng)cw+wic,則對左子樹進(jìn)行剪枝。 右子樹:設(shè)計(jì)上界函數(shù)剪枝,cp+vi+1+vnbestv,則對右子樹進(jìn)行剪枝。,主程序: 1、初始化bestv=0,cv=0,cw=0,bestx=0,0; 2、調(diào)用Backtrack(1); 3、輸出bestx1,n和bestv;,void Backtrack(int t) if(tn) if(bestvbestv) Backtrack(t+1); ,int Bound(int i) int b=cv; for(j=i;j=n;j+) b+=vj; return b; ,期末總結(jié)算法設(shè)計(jì),10、給定一個(gè)正整數(shù)集合X=x1,x2,xn和一個(gè)正整數(shù)y,設(shè)計(jì)回溯算法,求集合
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 鄉(xiāng)鎮(zhèn)煙花爆竹經(jīng)銷店安全檢查表
- 網(wǎng)點(diǎn)用戶體驗(yàn)提升策略-洞察闡釋
- 蛋白質(zhì)相互作用網(wǎng)絡(luò)與疾病關(guān)聯(lián)研究-洞察闡釋
- 安全員證和c證
- 幼兒注意力培養(yǎng)的教育心理學(xué)技巧
- 船舶安全生產(chǎn)月活動方案
- 環(huán)境保護(hù)鑒定-洞察及研究
- 從業(yè)人員安全生產(chǎn)管理制度
- 加強(qiáng)國際交流促進(jìn)中醫(yī)教育現(xiàn)代化發(fā)展
- 食堂安全管理應(yīng)急預(yù)案
- 手電筒產(chǎn)品課程設(shè)計(jì)報(bào)告書
- 《優(yōu)質(zhì)客戶服務(wù)技巧》
- TL4型彈性套柱銷聯(lián)軸器零件工藝規(guī)程及加工柱銷孔液動夾具設(shè)計(jì)
- 05-衣之鏢-輔行訣湯液經(jīng)法用藥圖釋義
- LS/T 3240-2012湯圓用水磨白糯米粉
- GB/T 15298-1994電子設(shè)備用電位器第一部分:總規(guī)范
- 2023高中學(xué)業(yè)水平合格性考試歷史重點(diǎn)知識點(diǎn)歸納總結(jié)(復(fù)習(xí)必背)
- 自然指數(shù)NatureIndex(NI)收錄的68種自然科學(xué)類期刊
- 手術(shù)報(bào)告審批單
- 《專業(yè)導(dǎo)論光電信息科學(xué)與工程》教學(xué)大綱
- 少兒美術(shù)國畫- 少兒希望 《紫藤課件》
評論
0/150
提交評論