Re: [中譯] Projecteuler (280) Ant and seeds

[utomaya (烏托馬雅)]

我解掉了

馬可夫鏈太複雜了
我用DP去解

一樣分成11段去做
初始狀態 → 駝第一顆豆 → 放第一顆豆 → 駝第二顆豆 → ... → 放第五顆豆

第一段，初始狀態 → 駝第一顆豆
第二段，駝第一顆豆 → 放第一顆豆
第三段：放第一顆豆 → 駝第二顆豆
(依此類推)
.
.
.
對於每一段，假設1步要走一時間單位，對於5x5每一格，在經過了t時間單位後
螞蟻恰好走了t步而停在這一格上，都會有一對應的機率

舉例來說，假設在某一個時間點，螞蟻在(2,2)上走了N步的機率是P，那麼下一步中
碼蟻走了(N+1)步而到相鄰4格中的機率皆為P/4，
所以在相鄰四格其紀錄N+1步的機率的資料上分別加上P/4

對於DP來說，等於是每一個時間點t，掃過5x5的格子一遍，分別求出螞蟻恰好走了t步而
停在這一格上的機率(當然，機率有可能是零)

期望值就是每一步的機率乘上步數之總和

用陣列來紀錄這個機率，紀錄到2000步即可
因為兩千步以上的機率發生機率很小，機率乘以步數的乘積相當小，可以略去不計
所以要有[5x5x2000]筆資料

當螞蟻抵達最上一列或最下一列要放下或搬運種子時，他會有若干選擇，
以第一段來說，它可以有5種開始駝運種子的選擇，
它究竟是最先抵達最左邊的格子開始搬運？還是最先抵達最右邊的格子開始搬運？
也就是說，對於該段的每一個結束點都會有一個機率，
當然，這也可以用上述DP方法，分別記錄其機率，
每一個結束點的機率，其總和應為1。

對於11段中每一段來講，起始點會有若干種選擇(第一段除外)，結束點會有若干種選擇
每一個組合都要去跑
並紀錄其停在每個不同結束點的機率

最後，算出5!x5!的不同選擇路徑的期望值e跟機率p的總和
也就是Σe*p
還是滿複雜的@_@

答案是430.08xxxx
跟我當初模擬的狀況429.7~429.9差了那麼一點點

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.174.216
推 puzzlez:這一系列文章讓人好孤獨...因為都看不懂 Q_Q
推 penguin7272:推
推 jurian0101:推2000步
→ jurian0101:所以說這題其實不難，只是很麻煩而已。
→ jurian0101:小聲: 機率要收斂到10^-6 似乎不需要到 2000步
→ utomaya:蠻難的 因為很容易出錯 程式也不好寫
→ utomaya:我本來跑100步 但答案不對 才改成2000步
→ utomaya:1000步 寫錯
推 jurian0101:請受小弟一拜 XD
→ utomaya:不用了 有一個人更厲害 我晚了他3天才解出來XD
※ 編輯: utomaya         來自: 219.70.174.216       (03/04 21:49)
推 tw00088437:level 1的小弟朝聖