作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] cutting sticks
时间Wed Feb 22 17:58:48 2012
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
请问这个式子是怎麽导出来的?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.24.240
1F：推 suhorng:2*p*f(k-1,n): 最左边切一刀或最右边切一刀, 用剩下的k-1 02/22 18:15
2F：→ suhorng:长木棍切出n长 02/22 18:15
3F：→ suhorng:(1-p)^{k-1}: 这k-1个间隔都不切,剩下长度自然也≧n 02/22 18:16
4F：→ suhorng:是说这递回式看起来好怪...真的是对的吗 ? 02/22 19:47
5F：→ mqazz1:不清楚耶 因为这是别人解的 请问s大会怎麽写呢? 02/22 19:57
6F：→ FRAXIS:或许是(1-P)^(k-1) ? 02/22 20:25