Projecteuler (280) Ant and seeds - 拼圖

1.我先講怎麼拆成單獨的小問題，這個部分我和 LPH66 與 jurian0101 想得一樣。

這整個過程必定歷經

初始狀態 → 駝第一顆豆 → 放第一顆豆 → 駝第二顆豆 → ... → 放第五顆豆

這樣 11 階段的狀態。扣掉最後已達終點的階段，每一階段的每一種可能組合，
都是一個我們要算的 process。 (1251 是這樣算出來的)

例如某一個狀態它長這樣 (紅格是螞蟻)

‧豆豆‧‧
‧‧‧‧‧
‧‧‧‧‧
‧‧‧‧‧
豆‧豆‧豆

它之後可能的進程必然是

‧豆豆‧‧ ‧豆豆‧‧ ‧豆豆‧‧
‧‧‧‧‧ ‧‧‧‧‧ ‧‧‧‧‧
‧‧‧‧‧ ‧‧‧‧‧ ‧‧‧‧‧
‧‧‧‧‧ ‧‧‧‧‧ ‧‧‧‧‧
豆‧豆‧豆 豆‧豆‧豆 豆‧豆‧豆

其中一種

這相當於一個醉漢跌入洞的問題 (求跌入各洞的機率 & 步數期望值)

‧‧醉‧‧
‧‧‧‧‧
‧‧‧‧‧
‧‧‧‧‧
洞‧洞‧洞



2.每一個 Markov process 的機率與步數期望值怎麼算

以上述的醉漢跌洞問題為例，我們要先算機率。先算最左邊的洞A。
假設每一格上都有一個機率 p(x,y) 表示跌入洞A的機率，
那麼 a) 洞A上的機率是 1
b) 另外兩洞上的機率是 0
c) 其他格上的機率是相鄰格機率的算術平均

p(1,5) p(2,5) p(3,5) p(4,5) p(5,5)
p(1,4) p(2,4) p(3,4) p(4,4) p(5,4)
p(1,3) p(2,3) p(3,3) p(4,3) p(5,3)
p(1,2) p(2,2) p(3,2) p(4,2) p(5,2)
1 p(2,1) 0 p(4,1) 0

解22元聯立方程式去算每一格的機率，再算完另外兩洞在每一格上的機率。

接下來算步數期望值。假設每一格上路入洞A的期望值是 s(x,y)，
那麼 a) 洞A上的期望值是 0
b) 另外兩洞上的期望值不重要 (也無意義)
c) 若其他某格的機率為 p, 期望值為 s, 相鄰格機率為 p1..pn, 期望值 s1..sn
則有 s = 1 + (p1s1 + ... + pnsn)/p*n (條件機率)

一樣解聯立，再算完其他兩個洞。
但是現在我們只要保留每一個洞的 p(3,5) 和 s(3,5) 就可以了。

有了這些數據的算法後之後就可以一步一步算那 1251 個狀態的達成機率與步數期望值
最後算那五個最終狀態的機率與期望值，加權平均即可。

好大的工程啊。 XD

--