西北工业大学-软件-算法实验2

实验二动态规划算法姓名：王智慷学号：2015303118班级：14011502一．问题描述小明想要在王者荣耀游戏里晋升一个段位，假设他一共需打了n场比赛，且必须成功赢得至少70%的场次才能成功晋升。假设每场比赛小明获胜的概率分别为p1，p2，…，pn，请帮他算出成功晋级段位的概率是多少？输入：参数1：整数num（0num1000），表示比赛的场数。参数2：整数数组p[num]={p1，p2，…，pnum}，其中pi表示小明有pi%的概率赢得第i场比赛。（0pi100）输出：成功晋级段位的概率，保留小数点后5位，最后结果四舍五入。二．实验目的及要求1.理解动态规划法的设计思想2.掌握动态规划法的求解步骤3.掌握用动态规划法解题的算法框架三．实验分析1.分析问题的最优子结构将问题分解为子问题求解：完成到第i局比赛时并赢下j局的概率。则晋级的概率为，完成所有num局比赛时，赢下0.7*num局到赢下num局的概率之和。而完成到第i局比赛赢下j局比赛的概率可由完成到第i-1局比赛的概率得出，即，完成到第i-1局比赛时赢下j局并且第i局没有赢、完成第i-1局比赛时赢下j-1局比赛并且第i局赢了，这两者概率之和。2.建立递归关系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](j0)四．算法伪代码或流程图fori←1tonum-1doans[i][0]=ans[i-1][0]*(1-pt[i])forj←1toi+1doans[i][j]=ans[i-1][j]*(1-pt[i])+ans[i-1][j-1]*pt[i]fori←0.7*numtonumdopass=pass+ans[num-1][i]五．算法时间复杂性分析两重循环，操作数为1+2+3+4+…+(num+1)，所以时间复杂度为O(n2)。八．问题思考与总结简单的dp问题，重点在于分解子问题得到递推方程。九．实验中出现的问题及总结注意保留小数的问题。