のてすきあ − 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

Problem 65

ネイピア数eの連分数展開による有理数近似。

 多分プログラミング的にアレコレやることも可能なのだろう。しかし考えるのが面倒(問題としてあまり魅力を感じない)ので、数学の知識を使ってストレートに漸化式を解くことにする。

 無理数有理数近似については、以下が知られている。ハッキリ言ってこの問題は、これを知っているかどうかだけで勝負が決まるので、プログラミングクイズとしては悪問であると思う。


無理数 \omega = [a_0,a_1,...,a_n,... ] に対して数列  \{{p_n}\}_{n=-1}^{\infty}

および数列  \{{q_n}\}_{n=-1}^{\infty}


\begin{eqnarray}
  \left\{
    \begin{array}{l}
      p_{-1} = 1 \\
      q_{-1} = 0
    \end{array}
  \right.
\end{eqnarray}

\begin{eqnarray}
  \left\{
    \begin{array}{l}
      p_{0} = a_0 \\
      q_{0} = 1
    \end{array}
  \right.
\end{eqnarray}

\begin{eqnarray}
  \left\{
    \begin{array}{l}
      p_{n} = a_n p_{n-1} + p_{n-2} \\
      q_{n} = a_n q_{n-1} + q_{n-2}
    \end{array}
  \right.
\end{eqnarray}


と定めると

 [a_0,a_1,...,a_n ] =  \frac{p_n}{q_n}

が成り立つ。



むしろはてなブログTexを使う練習?…★