Project Euler 329 Prime Frog
Pythonで分数型を用いたいときは
fractions.Fraction(分子,分母)で出来る.
2. 次にマスが素数であれば"P"と鳴く確率は2/3, "N"と鳴く確率は1/3
マスが素数でなければ"P"と鳴く確率は1/3, "N"と鳴く確率は2/3
これを辞書に記憶しておく.
d=dict()
d[(5,"P")]=Fraction(2,3) d[(5,"N")]=Fraction(1,3)
d[(6,"P")]=Fraction(1,3) d[(6,"N")]=Fraction(2,3)みたいに
3. あるマスi に関してそのマスから始めたときに"string"と鳴く確率を求める
メモ化再帰を用いる.
マスが1なら右しかいけないのでPr=d[(1,string[0])]*func(i+1,string[1:])
マスが500なら左しかいけないのでPr=d[(500,string[0])]*func(i-1,string[1:])
マスが2~499なら左右どちらもいけるので
Pr=d[(i,string[0])]*( func(i+1,string[1:])*0.5 + func(i-1,string[1:])*0.5) )である
これはiマスでstrnigの先頭一文字目("P","N")の確率*(二文字目以降の確率)である.
2~499では左右どちらかに行くのに0.5の確率を考慮する.
