推 haman: 請問第10題的算法... 謝謝 11/20 13:35
第十題是醉漢走路
可參考這篇中文文章 https://reurl.cc/Q6oo75
知醉漢左走L步進水溝，右走R步進水溝
左右走機率1/2的情形下
期望值L*R步會踏入水溝中
轉成飛鏢問題
前兩鏢必定命中兩個新區域
此時下一個新區域為1步，反方向的新區域為(3-1)步
故期望值需2鏢
再下一個新區域又為1步，反方向的新區域為(4-1)步
故期望值需3鏢
依此類推
.
.
.
區域數 飛鏢數期望值 總合
1 1 1
2 1 2
3 2 4
4 3 7
5 4 11
6 5 16
7 6 22
8 7 29
9 8 37
10 9 46
11 10 56
12 11 67
13 12 79
14 13 92
15 14 106
16 15 121
17 16 137
18 17 154
19 18 172
20 19 191
191即為答案
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.91.252 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1637396870.A.854.html
留言