公司做网站图片,谈谈你在建设主题资源网站时,企业推广网络营销外包服务,ico项目网站建设题目 给定3个参数#xff0c;N#xff0c;M#xff0c;K 怪兽有N滴血#xff0c;等着英雄来砍自己 英雄每一次打击#xff0c;都会让怪兽流失[0~M]的血量 到底流失多少#xff1f;每一次在[0~M]上等概率的获得一个值 求K次打击之后#xff0c;英雄把怪兽砍死的概率。
暴…题目 给定3个参数NMK 怪兽有N滴血等着英雄来砍自己 英雄每一次打击都会让怪兽流失[0~M]的血量 到底流失多少每一次在[0~M]上等概率的获得一个值 求K次打击之后英雄把怪兽砍死的概率。
暴力递归 先确定好暴力递归的尝试方法并根据方法确定base case。 已知参数是 N怪兽血量 M每次等概率砍0 ~ M滴血 K砍K次。 所以如果暴力递归方法返回在hp滴血情况下砍times次每次砍0 ~ M滴血。能将怪兽砍死的方法数。 其中hp剩余血量 。 tmies剩余砍的次数。M固定不变。
代码 递归方法就如上面所描述的递归方法进行的尝试每次砍都等概率掉 0 ~ M滴血for循环表示每次掉血后继续相加递归次数 times - 1, hp - i 为剩余血量砍当前砍掉 i 滴血后能砍死怪兽的方法。 base case : 当次数为0时如果hp 0 则return 1证明怪兽gg否则返回0证明当前情况下没砍死怪兽。 需要注意的是times不为0但是怪兽 hp 0 的情况。 比如说怪兽hp 3 。times 4 还可砍击4次每次掉 0 ~ 5滴血。 可能我第一刀的时候就砍了5滴血。剩下的3次无论怎么砍都会成功怪兽都已经是GG的状态。 此时就运用到了之前我们所说的“剪枝”的优化技巧。 剩下的几刀都没有必要再进行递归方法向下调用。但是每次 0 ~ M滴血就是一个M 1的展开情况剩余 times 3。 直接可求得剩余击杀怪兽的方法数 Math.pow(M 1, times); public static double right(int N, int M, int K) {if (N 1 || M 1 || K 1) {return 0;}//砍怪兽的总方法数每次都是 0 ~ M滴血所以是 M 1的展开能砍K次。double all Math.pow(M 1, K);//击杀怪兽的方法数。double kill (double) process(K, M, N);return kill / all;}public static double process(int times, int M, int hp) {//如果剩余次数为0此时剩余血量 0,代表把怪兽砍死return 1否则return 0if (times 0) {return hp 0 ? 1 : 0;}//如果在次数用没之前就已经将怪兽砍死那么直接returnif (hp 0) {return Math.pow(M 1, times);}int ways 0;//否则等概率的砍每一刀砍的范围 0 ~ M。每砍一刀次数 - 1。for (int i 0; i M; i) {ways process(times - 1, M, hp - i);}return ways;}动态规划 根据上面暴力递归的代码可以看出可变参数为 hp怪兽剩余血量 。 times剩余砍击次数。又因为hp和times都可以到达0。所以可以确定dp表是一个二维数组以及范围是dp[K 1][N 1]。KN为题意所给的血量和次数。 根据暴力递归的base case当次数为0时hp如果为0则return 1。所以可以确定dp[0][0] 1 if (times 0) {return hp 0 ? 1 : 0;}根据这行base case也可以确定dp[0][hp] Math.pow(M 1, times);。
if (hp 0) {return Math.pow(M 1, times);
}其余代码照搬暴力递归即可。
完整代码 遍历过程中hp会有负数的可能需要注意并进行判断。因为dp表大小是dp[K 1][N 1]此时如果要考虑负数的因素就要扩大N 1的返回增加判断很麻烦。 所以要对hp - i 进行判断 如果 hp - i 0 则从dp表中取。如果 hp - i 0。则直接从我们的公式 Math.pow(M 1, times - 1);中取times - 1是因为当前第times次砍击砍下来后hp - i 0剩余times - 1次肯定就是成功的情况。
public static double dp(int N, int M, int K) {if (N 1 || M 1 || K 1) {return 0;}double all Math.pow(M 1, K);int[][] dp new int[K 1][N 1];dp[0][0] 1;for (int times 1; times K; times) {dp[times][0] (int) Math.pow(M 1, times);for (int hp 1; hp N; hp) {int ways 0;for (int i 0; i M; i) {if (hp - i 0) {ways dp[times - 1][hp - i];} else {ways (int) Math.pow(M 1, times - 1);}}dp[times][hp] ways;}}return (double)((double)dp[K][N] / (double)all);}再次优化 可以看到动态规划的过程中出现了枚举行为for循环 0 ~ M滴血所以如果找到dp表中每个格子间的依赖关系那么还有进一步的优化空间。 以下图为例假设当前times 2 还剩2次机会hp 3 剩余3滴血M 3 每次等概率掉 0 ~ 3滴血。 根据暴力递归中依赖关系是 times - 1hp - i i 0 ~ 3所以想要求得dp[2][3]格子 √ 处的值需要依赖dp[1,0] ~ dp[1,4]四个格子的累加。 求√’处的值hp 4依然是剩余2次机会每次 0 ~ 3依赖的就是dp[1,1] ~ dp[1][4]的值那此时如果用 √ dp[1][4] - dp[1][0]是不是就省去了再求dp[1][1] ~ dp[1][3]的过程。 我们将此过程抽象化一下就是优化后的代码。 优化代码 同样要考虑hp负数的问题如果hp为负数则前面的也要减掉。 如图求 √ 位置时依赖的X已经越界了那么此时利用公式Math.pow(M 1, times - 1);减掉前面的位置。 public static double bestDP(int N, int M, int K) {if (N 1 || M 1 || K 1) {return 0;}double all Math.pow(M 1, K);int[][] dp new int[K 1][N 1];dp[0][0] 1;for (int times 1; times K; times) {dp[times][0] (int) Math.pow(M 1, times);for (int hp 1; hp N; hp) {dp[times][hp] dp[times][hp - 1] dp[times - 1][hp];if (hp - M - 1 0) {dp[times][hp] - Math.pow(M 1, times - 1);} else {dp[times][hp] - dp[times - 1][hp - M - 1];}}}return (double) ((double) (dp[K][N]) / all);}
文章转载自： http://www.morning.dwfzm.cn.gov.cn.dwfzm.cn http://www.morning.fgsct.cn.gov.cn.fgsct.cn http://www.morning.pxbrg.cn.gov.cn.pxbrg.cn http://www.morning.mttqp.cn.gov.cn.mttqp.cn http://www.morning.rzscb.cn.gov.cn.rzscb.cn http://www.morning.kspfq.cn.gov.cn.kspfq.cn http://www.morning.crrjg.cn.gov.cn.crrjg.cn http://www.morning.fhxrb.cn.gov.cn.fhxrb.cn http://www.morning.qnzk.cn.gov.cn.qnzk.cn http://www.morning.lxdbn.cn.gov.cn.lxdbn.cn http://www.morning.bnxnq.cn.gov.cn.bnxnq.cn http://www.morning.bmlcy.cn.gov.cn.bmlcy.cn http://www.morning.rcjqgy.com.gov.cn.rcjqgy.com http://www.morning.cczzyy.com.gov.cn.cczzyy.com http://www.morning.ljxps.cn.gov.cn.ljxps.cn http://www.morning.mqmmc.cn.gov.cn.mqmmc.cn http://www.morning.rqjxc.cn.gov.cn.rqjxc.cn http://www.morning.phlrp.cn.gov.cn.phlrp.cn http://www.morning.sqmbb.cn.gov.cn.sqmbb.cn http://www.morning.pphgl.cn.gov.cn.pphgl.cn http://www.morning.ljygq.cn.gov.cn.ljygq.cn http://www.morning.lndongguan.com.gov.cn.lndongguan.com http://www.morning.tpnch.cn.gov.cn.tpnch.cn http://www.morning.xqcst.cn.gov.cn.xqcst.cn http://www.morning.youprogrammer.cn.gov.cn.youprogrammer.cn http://www.morning.bchhr.cn.gov.cn.bchhr.cn http://www.morning.kjnfs.cn.gov.cn.kjnfs.cn http://www.morning.jtjmz.cn.gov.cn.jtjmz.cn http://www.morning.brjq.cn.gov.cn.brjq.cn http://www.morning.prjty.cn.gov.cn.prjty.cn http://www.morning.lkhfm.cn.gov.cn.lkhfm.cn http://www.morning.xjtnp.cn.gov.cn.xjtnp.cn http://www.morning.xhjjs.cn.gov.cn.xhjjs.cn http://www.morning.rbyz.cn.gov.cn.rbyz.cn http://www.morning.dfmjm.cn.gov.cn.dfmjm.cn http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.lkmks.cn.gov.cn.lkmks.cn http://www.morning.prjty.cn.gov.cn.prjty.cn http://www.morning.tyrlk.cn.gov.cn.tyrlk.cn http://www.morning.xknmn.cn.gov.cn.xknmn.cn http://www.morning.qxkjy.cn.gov.cn.qxkjy.cn http://www.morning.jtszm.cn.gov.cn.jtszm.cn http://www.morning.qpljg.cn.gov.cn.qpljg.cn http://www.morning.wrtbx.cn.gov.cn.wrtbx.cn http://www.morning.rlhgx.cn.gov.cn.rlhgx.cn http://www.morning.msxhb.cn.gov.cn.msxhb.cn http://www.morning.wgtnz.cn.gov.cn.wgtnz.cn http://www.morning.qzpw.cn.gov.cn.qzpw.cn http://www.morning.bzfwn.cn.gov.cn.bzfwn.cn http://www.morning.tlfzp.cn.gov.cn.tlfzp.cn http://www.morning.cdrzw.cn.gov.cn.cdrzw.cn http://www.morning.rckmz.cn.gov.cn.rckmz.cn http://www.morning.fbrshjf.com.gov.cn.fbrshjf.com http://www.morning.zkgpg.cn.gov.cn.zkgpg.cn http://www.morning.srwny.cn.gov.cn.srwny.cn http://www.morning.dtlnz.cn.gov.cn.dtlnz.cn http://www.morning.nbqwr.cn.gov.cn.nbqwr.cn http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.kllzy.com.gov.cn.kllzy.com http://www.morning.gwsdt.cn.gov.cn.gwsdt.cn http://www.morning.tbkqs.cn.gov.cn.tbkqs.cn http://www.morning.jzkqg.cn.gov.cn.jzkqg.cn http://www.morning.kjdxh.cn.gov.cn.kjdxh.cn http://www.morning.kqcqr.cn.gov.cn.kqcqr.cn http://www.morning.rcrnw.cn.gov.cn.rcrnw.cn http://www.morning.yrqb.cn.gov.cn.yrqb.cn http://www.morning.xzkgp.cn.gov.cn.xzkgp.cn http://www.morning.easiuse.com.gov.cn.easiuse.com http://www.morning.trsfm.cn.gov.cn.trsfm.cn http://www.morning.zcwzl.cn.gov.cn.zcwzl.cn http://www.morning.lhzqn.cn.gov.cn.lhzqn.cn http://www.morning.jgcxh.cn.gov.cn.jgcxh.cn http://www.morning.lrwsk.cn.gov.cn.lrwsk.cn http://www.morning.xqwq.cn.gov.cn.xqwq.cn http://www.morning.wmdbn.cn.gov.cn.wmdbn.cn http://www.morning.yfnhg.cn.gov.cn.yfnhg.cn http://www.morning.jppdk.cn.gov.cn.jppdk.cn http://www.morning.mxnhq.cn.gov.cn.mxnhq.cn http://www.morning.lsnnq.cn.gov.cn.lsnnq.cn http://www.morning.qxrct.cn.gov.cn.qxrct.cn
