西北工業(yè)大學(xué)-軟件-算法實(shí)驗(yàn).doc
《西北工業(yè)大學(xué)-軟件-算法實(shí)驗(yàn).doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《西北工業(yè)大學(xué)-軟件-算法實(shí)驗(yàn).doc(2頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
實(shí)驗(yàn)二 動(dòng)態(tài)規(guī)劃算法 姓名:王智慷 學(xué)號(hào):2015303118 班級(jí):14011502 一.問(wèn)題描述 小明想要在王者榮耀游戲里晉升一個(gè)段位,假設(shè)他一共需打了n場(chǎng)比賽,且必須成功贏得至少70%的場(chǎng)次才能成功晉升。假設(shè)每場(chǎng)比賽小明獲勝的概率分別為p1,p2,…,pn,請(qǐng)幫他算出成功晉級(jí)段位的概率是多少? 輸入: 參數(shù)1:整數(shù)num(0 num 1000),表示比賽的場(chǎng)數(shù)。 參數(shù)2:整數(shù)數(shù)組p[num] = {p1,p2,…,pnum},其中pi表示小明有pi%的概率贏得第i場(chǎng)比賽。(0 pi 100) 輸出: 成功晉級(jí)段位的概率,保留小數(shù)點(diǎn)后5位,最后結(jié)果四舍五入。 二.實(shí)驗(yàn)?zāi)康募耙? 1.理解動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想 2.掌握動(dòng)態(tài)規(guī)劃法的求解步驟 3.掌握用動(dòng)態(tài)規(guī)劃法解題的算法框架 三.實(shí)驗(yàn)分析 1.分析問(wèn)題的最優(yōu)子結(jié)構(gòu) 將問(wèn)題分解為子問(wèn)題求解:完成到第i局比賽時(shí)并贏下j局的概率。則晉級(jí)的概率為,完成所有num局比賽時(shí),贏下0.7*num局到贏下num局的概率之和。 而完成到第i局比賽贏下j局比賽的概率可由完成到第i-1局比賽的概率得出,即,完成到第i-1局比賽時(shí)贏下j局并且第i局沒(méi)有贏、完成第i-1局比賽時(shí)贏下j-1局比賽并且第i局贏了,這兩者概率之和。 2.建立遞歸關(guān)系 ans[i][j] = ans[i-1][0]*(1-pt[i]) (j=0) 或ans[i-1][j] * (1-pt[i]) + ans[i-1][j-1] * pt[i] (j>0) 四.算法偽代碼或流程圖 for i←1 to num-1 do ans[i][0] = ans[i-1][0] * (1-pt[i]) for j←1 to i+1 do ans[i][j] = ans[i-1][j] * (1-pt[i]) + ans[i-1][j-1] * pt[i] for i←0.7*num to num do pass = pass + ans[num-1][i] 五.算法時(shí)間復(fù)雜性分析 兩重循環(huán),操作數(shù)為1+2+3+4+…+(num+1),所以時(shí)間復(fù)雜度為O(n2)。 八.問(wèn)題思考與總結(jié) 簡(jiǎn)單的dp問(wèn)題,重點(diǎn)在于分解子問(wèn)題得到遞推方程。 九.實(shí)驗(yàn)中出現(xiàn)的問(wèn)題及總結(jié) 注意保留小數(shù)的問(wèn)題。- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 西北工業(yè)大學(xué) 軟件 算法 實(shí)驗(yàn)
鏈接地址:http://m.zhongcaozhi.com.cn/p-6709858.html