: ※ 引述《Sany (小美眉)》之铭言： : : 以前玩过一个游戏, : : 规则是这样的... : : 猜拳赢一次得一分，平手不影响分数，输一次倒扣一分至０分为止 : : 你得五分则本局胜利与结束，你猜输三次则本局失败与结束 : : 我觉得那真是很难赢的游戏, : : 後来想算算赢的机率, : : 但都没人会算, : : 我只好自己用程式试, : : 玩10万次的胜率是13.02% : : 不知道有没有人能列式算出胜率呢? : 也就是这样: : : → AmosYang:0.130859375 这个应该没错了 03/07 20:45 : → AmosYang:解出来了，但有一种"输了"的感觉，因为我是一项一项列出 03/07 20:49 : → AmosYang:慢慢加;一开始原本以为DP建表直接算就好，结果答案出 03/07 20:50 : → AmosYang:来差十万八千里… <囧> 03/07 20:50 : → AmosYang:<囧><囧><囧><囧><囧> 03/07 21:34 : → AmosYang:事实上之前DP解法的方向是对的，但有一个小typo... 03/07 21:35 : → AmosYang:总之…DP解、暴力解、模拟解三管齐下…那答案应该是正确 03/07 21:36 : 推 Sany:dp解系啥米? 03/07 21:51 : → AmosYang:dynamic programming 03/07 21:59 总之，这题可以用 DP 这样解: 先开 2D table row index 为猜输的次数 column index 为目前分数 table 开出来後就不难看出这个 table 可以纪录这个游戏的状态 且，游戏目前停在某个 cell 的机率就是「所有通往此 cell 的路径的机率的总和」 而每个 cell 要记得的就是「从 (R=0,C=0) 走到我这格走了 X 步有 Y 种走法」 然後让 (R=0,C=0) 这格初始化为 「从 (R=0,C=0) 走到我这格走了 0 步有 1 种走法」 然後要记得处理一些 special case, 假设目前在计算 (R,C) 这格 当 R=0 或 C=4 时，只需要看 (R,C-1) 这格 当 C=0 时，要看的是 (R-1,C) 与 (R-1,C+1) 这两格 其他的时候，要看的是 (R,C-1) 与 (R-1,C+1) 这两格 最後，启动 DP 去算 (0,4) (1,4) (2,4) 把所有的 "走了 X 步有 Y 种走法" 换成 (Y * 2^-X) 就是该路径的机率总和 那三个 cell 里的机率通通加起来即可得解… 我觉得这题还算善良的，猜赢与猜输的机率相同， 有空有闲的人可以想想若猜赢与猜输机率不同要怎麽解… (我已经不行了…) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 65.87.177.87 hmm... 若猜赢与猜输机率不同...事实上没有想像中复杂…算法几乎一样… (自言自语…) ※ 编辑: AmosYang 来自: 65.87.177.87 (03/07 22:45)