Problem 227
コンテンツ
227 The Chase
サイコロゲームの終了までの期待ターン数を求める.
サイコロがあちこちに動くので,一見複雑だが…
ひとつのサイコロの位置を基準にして考えれば,簡単なマルコフ連鎖であることが分かる.
あとは各状態について,期待値の等式をたて,その連立一次方程式を解けばよい.
しかし,その連立一次方程式を解くのに苦労した.
自分で実装してもよいのだが,車輪の再発明はあまりよろしくないと思っている.
ライブラリがあるなら,それを使うべき.
ということで,Haskellで行列計算するライブラリhmatrixを入れた.
import Numeric.LinearAlgebra (Matrix, fromLists, linearSolve, (@@>)) coef :: Int -> Matrix Double coef n = fromLists.(top :).take (n-1).map (take n).iterate (drop (n - 1)).tail $ base where base = cycle $ [-1, -8, 18, -8, -1] ++ replicate (n - 5) top = 1:replicate (n - 1) rightSide :: Int -> Matrix Double rightSide n = fromLists $ [] : replicate (n - 1) [36] p227 :: Int -> Double p227 n = linearSolve (coef n) (rightSide n) @@> (div n 2, ) main :: IO () main = print $ p227 100
それにしても行列要素へのアクセスが”@@>”って変な記号なのが気になる.
作成者 Toru Mano
最終更新時刻 2023-01-01 (c70d5a1)