西北工業(yè)大學(xué)-軟件-算法實(shí)驗(yàn).doc
-
資源ID:6709858
資源大?。?span id="njh0bjv" class="font-tahoma">20.57KB
全文頁數(shù):2頁
- 資源格式: DOC
下載積分:9.9積分
快捷下載
會(huì)員登錄下載
微信登錄下載
微信掃一掃登錄
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請知曉。
|
西北工業(yè)大學(xué)-軟件-算法實(shí)驗(yàn).doc
實(shí)驗(yàn)二 動(dòng)態(tài)規(guī)劃算法姓名:王智慷 學(xué)號(hào):2015303118 班級(jí):14011502 一問題描述小明想要在王者榮耀游戲里晉升一個(gè)段位,假設(shè)他一共需打了n場比賽,且必須成功贏得至少70%的場次才能成功晉升。假設(shè)每場比賽小明獲勝的概率分別為p1,p2,pn,請幫他算出成功晉級(jí)段位的概率是多少?輸入:參數(shù)1:整數(shù)num(0 num 1000),表示比賽的場數(shù)。參數(shù)2:整數(shù)數(shù)組pnum = p1,p2,pnum,其中pi表示小明有pi%的概率贏得第i場比賽。(0 pi 100)輸出:成功晉級(jí)段位的概率,保留小數(shù)點(diǎn)后5位,最后結(jié)果四舍五入。二實(shí)驗(yàn)?zāi)康募耙?.理解動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想2.掌握動(dòng)態(tài)規(guī)劃法的求解步驟3.掌握用動(dòng)態(tài)規(guī)劃法解題的算法框架三實(shí)驗(yàn)分析1.分析問題的最優(yōu)子結(jié)構(gòu)將問題分解為子問題求解:完成到第i局比賽時(shí)并贏下j局的概率。則晉級(jí)的概率為,完成所有num局比賽時(shí),贏下0.7*num局到贏下num局的概率之和。而完成到第i局比賽贏下j局比賽的概率可由完成到第i-1局比賽的概率得出,即,完成到第i-1局比賽時(shí)贏下j局并且第i局沒有贏、完成第i-1局比賽時(shí)贏下j-1局比賽并且第i局贏了,這兩者概率之和。2.建立遞歸關(guān)系ansij = ansi-10*(1-pti) (j=0)或ansi-1j * (1-pti) + ansi-1j-1 * pti (j>0)四算法偽代碼或流程圖for i1 to num-1 doansi0 = ansi-10 * (1-pti) for j1 to i+1 do ansij = ansi-1j * (1-pti) + ansi-1j-1 * ptifor i0.7*num to num dopass = pass + ansnum-1i五算法時(shí)間復(fù)雜性分析兩重循環(huán),操作數(shù)為1+2+3+4+(num+1),所以時(shí)間復(fù)雜度為O(n2)。八問題思考與總結(jié)簡單的dp問題,重點(diǎn)在于分解子問題得到遞推方程。九實(shí)驗(yàn)中出現(xiàn)的問題及總結(jié)注意保留小數(shù)的問題。