Euler : Problem 65

Posted by TAKAIY On 2011年11月26日土曜日 0 コメント
eについて、ある段階まで連分数展開したものを分数表記したときの分子の数字の問題。

これは、問題57で使った公式ですぐに解ける。
問題57ではは√2だったけど、こんどはe。





この方式は、連分数展開したときの 数列aを求める必要がある。
64の答えを使ってもいいのだけれど、eの連分数は、 {2:1,2,1,1,4,1,1,6,1,1,8,1,....}  になることが分っているので、これをつかう。

a0 = 2 、このあと

a1 = 1, a2 = 2, a3 = 1,
a4 = 1, a5 = 4, a6 = 1,
a7 = 1 a8 = 6, a9 = 1,

のように規則的に並んでいる。これを、a[n] についての場合で分けるとこうなる。

  • n=0 のときは2
  • nを3で割った余りが2のときは ((n+1)/3)*2
  • それ以外は1

これで実装した。





- cf-seq-of-e
  eの数列の生成関数。 説明の通り。

- cf-numerator
  n番目まで展開したときの分子を求める。
  問題57を解いたときは数列を外部参照していたけど、持っていくように変更。
  ずうっと持って回っているのがちょっと気持ち悪い。
  defn-memoは前につくったメモ化マクロ。

- cf-denominator
  使ってないけど、分母を出すやつ。

- pu-65
  n番目の分子を計算して、中の数字を全部足す。
  この方法だと、数字が大きくなるとスタックが溢れるかもしれない。
  そのときは小さい数字から攻めていこうと思ったけど、計算できたのでよしとする。




0 コメント:

コメントを投稿