西北工業(yè)大學(xué)-軟件-算法實驗.doc

《西北工業(yè)大學(xué)-軟件-算法實驗.doc》由會員分享，可在線閱讀，更多相關(guān)《西北工業(yè)大學(xué)-軟件-算法實驗.doc（2頁珍藏版）》請在裝配圖網(wǎng)上搜索。

實驗二 動態(tài)規(guī)劃算法 姓名：王智慷 學(xué)號：2015303118 班級：14011502 一．問題描述 小明想要在王者榮耀游戲里晉升一個段位，假設(shè)他一共需打了n場比賽，且必須成功贏得至少70%的場次才能成功晉升。假設(shè)每場比賽小明獲勝的概率分別為p1，p2，…，pn，請幫他算出成功晉級段位的概率是多少？ 輸入： 參數(shù)1：整數(shù)num（0 num 1000），表示比賽的場數(shù)。 參數(shù)2：整數(shù)數(shù)組p[num] = {p1，p2，…，pnum}，其中pi表示小明有pi%的概率贏得第i場比賽。（0 pi 100） 輸出： 成功晉級段位的概率，保留小數(shù)點(diǎn)后5位，最后結(jié)果四舍五入。 二．實驗?zāi)康募耙? 1.理解動態(tài)規(guī)劃法的設(shè)計思想 2.掌握動態(tài)規(guī)劃法的求解步驟 3.掌握用動態(tài)規(guī)劃法解題的算法框架 三．實驗分析 1.分析問題的最優(yōu)子結(jié)構(gòu) 將問題分解為子問題求解：完成到第i局比賽時并贏下j局的概率。則晉級的概率為，完成所有num局比賽時，贏下0.7*num局到贏下num局的概率之和。 而完成到第i局比賽贏下j局比賽的概率可由完成到第i-1局比賽的概率得出，即，完成到第i-1局比賽時贏下j局并且第i局沒有贏、完成第i-1局比賽時贏下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] 五．算法時間復(fù)雜性分析 兩重循環(huán)，操作數(shù)為1+2+3+4+…+(num+1)，所以時間復(fù)雜度為O(n2)。 八．問題思考與總結(jié) 簡單的dp問題，重點(diǎn)在于分解子問題得到遞推方程。 九．實驗中出現(xiàn)的問題及總結(jié) 注意保留小數(shù)的問題。