読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

Project Euler 329 Prime Frog

projecteuler.net

Pythonで分数型を用いたいときは

fractions.Fraction(分子,分母)で出来る.

 

1. 500以下の全てのマスを素数素数でないか区別する.

 

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の確率を考慮する.

 

gist.github.com