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

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者utomaya (烏托馬雅)時間16年前 (2010/03/04 19:10)推噓5(5推 0噓 6→)

留言11則, 5人參與討論串5/5 (看更多)

我解掉了馬可夫鏈太複雜了我用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