※ 引述《mqazz1 (无法显示)》之铭言： : suppose that we cut a stick of length L (a positive integer) with the : probability P at each position such that its distance from the left end : is a positive integer. : design an efficient dynamic programming algorithm for calculating the : probability that a stick of length at least n remains. : 我手中的答案是 : 令F(k,n)为把长度k的木棒 切出有一条长度至少为n木棒的机率 : F(k,n) = 0, if 1<=k<=n-1 : F(k,n) = 2PF(k-1,n) + (1-P)^(k-1), if k>=n : 请问这个式子是怎麽导出来的? : 谢谢 我是在想说...假如 L = 5, P = 0.1, 我们希望至少剩下长度 3 __ __ __ __ __ | | | | | | |__|__|__|__|__| 1 2 3 4 1.剩下长度 5 : (1 - 0.1)^4 = 0.6561 2.剩下长度 4 : 在 1 切或在 4 切, 剩下三个不切: 0.1*(1 - 0.1)^3 * 2 = 0.1458 3.剩下长度 3 : 剩最左边长度 3, 或最右边长度 3 : 左: 12不切, 切 3, 4 无所谓. 右边类似 0.1*(1 - 0.1)^2 * 2 = 0.162 剩中间长度 3: 0.1^2 * (1 - 0.1)^2 = 0.0081 0.6561 + 0.1458 + 0.162 + 0.0081 = 0.972 不知道有没有错...这跟递回式算出来不同 //只是想表示递回式怪怪的 orz --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.217.34.226 ※ 编辑: suhorng 来自: 61.217.34.226 (02/22 20:45)