[問題] 跳蚤馬戲團-模擬或解析?

看板Mathematica作者jurian0101 (Hysterisis)時間12年前 (2012/03/16 18:45)推噓1(1推 0噓 5→)

留言6則, 2人參與討論串1/2 (看更多)

正在用我layman的實力努力攻Project Euler http://projecteuler.net 其實Mathematica解這平台的一些題目是有長處的，那些大致上只需要形成一個明確的 data structure，算法也明確化之後，Mathematica的程式碼會(以layman觀點)很優雅 - - - 目前有疑問的是這一題 213:Flea Circus 大意是有一個30 X 30 的大棋盤，每格中各有一隻跳蚤。每次鐘一響，跳蚤有平均的機率跳到相鄰的格子(如角落兩格各1/2，邊緣三格各1/3，其餘1/4) 請問在50響鐘聲之後，沒有跳蚤的格子數量的期望值是多少？首先我想到的方針是計算單一隻跳蚤，例如起始點位在{1,1}的跳蚤，在五十步之後在各格的機率分佈表。因為每隻跳蚤的跳動是獨立的，故(特定某格是空的)此事件的機率就是 (全部900隻都沒停在此格) 的機率。等於上述表格取互補機率，全部相乘。然後再對900格加總就得到答案這樣......的樣子。 = = = = = 用來實行單跳蚤"隨機漫步"的函式我是這樣寫 (* iteration=步數，startpoint起始點，gridsize={x寬,y高}，accuracy=有效位數。*) GridRandomWalk [startpoint_List, gridsize_List, iteration_Integer,accuracy_Integer] := Module[ {grid, flag = 0, mx, my, loc}, grid[_][_, _] = 0; grid[flag][startpoint[[2]], startpoint[[1]]] = 1; mx = gridsize[[2]]; my = gridsize[[1]]; loc[px_, py_] := Which[(px == 1 || px == mx) && (py == 1 || py == my)(*corner*), 1/2, Xor[px == 1 || px == mx, py == 1 || py == my](*edge*), 1/3, True(*else=center*), 1/4] * grid[flag][px, py]; (*主迴圈*) For[i = 1, i <= iteration, i++, For[x = 1, x <= mx, x++, For[y = 1, y <= my, y++, grid[1 - flag][x, y] = loc[x - 1, y] + loc[x + 1, y] + loc[x, y - 1] + loc[x, y + 1]; ]; ]; flag = 1 - flag; ]; N[Table[grid[1 - flag][i, j], {i, mx}, {j, my}], accuracy] ] (*因為只想得到最後的結果，中間過程不重要，所以用flag在0,1間切換，輪流當作被寫入。DP*) 會得到最終跳蚤位在各格的機率，剩餘的就是相乘加總結論是答案不對 = =+ 然後我赫然發覺，啊~希罵打。期望值能加總的前提是事件彼此獨立。但是(A格子是空的) 與 (B格子是空的) 是會彼此相互影響的......似乎是不能單純相加......的樣子但是一番辜狗後又得到這樣做可以得到正解的結果 (如 http://stats.stackexchange.com/a/2434 Glen_b所言) 於是我完全混亂了 >>>> 請解過這題的LPH大指點迷津或者該寫 Needs["Help`LPH66"] :D 從上面網址得到的的想法還有，可否將(全體跳蚤在各格子裡的重數)當作一個統計分布 (感覺像統計物理那樣的東西) 作Monte Carlo，依layman的感覺是不行，至少在需要得到 10個有效位數這一點就有點難以實行。但網格、粒子、狀態、機率分布，感覺起來其中又有一些很有趣的架構在的樣子吧。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.213.88