- プログラミングのお題スレ Part5
292 ：276[sage]：2014/10/14(火) 16:43:51.64 ID:n56qJH47 - >>291
私の解答より素晴らしいです
以下が用意してた解答です
次のようにして早く、精度の良い答えが得られます
マスに0ベースのインデックスを振るとし、
e[i] = iマスからgoalまでのターン数の期待値
という配列eを想定します
すると、 e[0] について次のような式が建てられます
e[0] = 1 + (e[1+3] + e[2] + e[3+5] + e[4] + e[5] + (1 + e[6])) / 6
(スゴロクのマスと見比べてみると意味がわかると思います)
同様にすべてのマスについてこのような式ができます
ゴールマスについてはすでにgoalに着いているという意味で
e[17] = 0
となります
以上を踏まえるとこの問題は
「e[0],..,e[17]についての連立方程式を解き、e[0] の具体的な値を求める」
という問題に帰着します
私は連立方程式の解法とか詳しくないので
e[0],..,e[16]の式を何度も評価し、徐々に精度を上げるというアルゴリズムを書きました
http://ideone.com/QGi1OZ
40回ほどの反復で目的の精度になりました
|