Re: [問題] cutting sticks
看板Prob_Solve (計算數學 Problem Solving)作者suhorng ( )時間12年前 (2012/02/22 20:39)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/2 (看更多)
※ 引述《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)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
