連分数について、SICPより

連分数に書いてみる。

連分数

 </p><p>f = \frac {N_1} {D_1 + \frac{N_2} {D_2 + \frac{N_3} {D_3 + \ddots}   } }</p><p>


SICPの問題1.37は有限の連分数を用いて 1 / \phi(\phi黄金数)を求める問題なんだよね。ところですべての自然数iN_i = 1, D_i = 1の時に 1/\phiになるのか気にならない?

では説明してみよー。難しい説明になるではと思いの方もいるかもね。でも、とても簡単なのですよ。中学生でも分かるぜー。

さてではまず黄金比の定義から考えよー。

黄金比の定義:
下図をみてくれ。図の線分の長さについての比 1 : x = x : (x + 1) を満たす時、1:xが黄金比なのよね。

つまり、長い線分と短い線分の比と、全部の線分と長い線分の比が等しい時の比なんだよねー。

f:id:Nobkz:20130504093839g:plain

 1 : x = x : (x + 1) の1:xが黄金比って分かったのね。じゃあ、次はこれを分数の形にしてみよー。

え?なんで分数の形にするかって?
連分数を求めるのだから、とりあえず分数の形にしておけば分かりそーじゃない?

ってので、分数にしよ。とするとー

\frac{1}{x} = \frac{x}{x+1}


になるちょー。あ、言い忘れてたけど、1:x黄金比なんだから、当然ながら1:x = 1:\phiですよね。つまり x = \phi当然だけどね。

左式をみたら、1/x!やった、1/\phiだ!

じゃあ、右辺を変形していったらいいよね!
つまり、

 \frac{1}{x} = \frac{x}{x + 1}

の右式\frac{x}{x+1}

 \frac{1}{1 + \frac{1}{1 + \frac{1}{ 1+ \ddots }} }

の形にしていけばいいんだ。とすると連分数の方は凄く1が多いよね。じゃあ、1が多くなるよーに変形しいこー。とすると、x/(x + 1)に1を増やすにはって考えると、分子分母に1/xを掛けてあげればいいって思いつくのね。

すると、

 \frac{x}{x + 1} = \frac{x * 1/x}{ (x + 1) * 1/x} = \frac{1}{ 1 + \frac{1}{x}}

そんで、これを

 \frac{1}{x} = \frac{1}{ 1 + \frac{1}{x} }

となるよね。んでこの数式をじーっと見てみて。何か気づかない?

左辺は
 (\frac{1}{x}) = ....

の形をしている。右辺は....
 \frac{1}{ 1 +( \frac{1}{x} )  }

ん?括弧の部分が同じだよね...。

なにが、言いたいかって言うと、左辺の1/x =..となってるから、右辺の(1/x)に代入できるってこと。つまり、

 (\frac{1}{x}) = \frac{1}{ 1 + (\frac{1}{x})  } = \frac{1}{ 1 + (\frac{1}{ 1 + \frac{1}{x}}) }

と変形できちゃうわけ!同じ式の中に、同じ式を代入できるんだ!さらに!一番右の式の中に1/xが出てる!また代入できるね!きゃっきゃ!

 (\frac{1}{x}) = \frac{1}{ 1 + (\frac{1}{x})  } = \frac{1}{ 1 + \frac{1}{ 1 + (\frac{1}{x}) } } = \frac{1}{ 1 + \frac{1}{ 1 + \frac{1}{ 1 + (\frac{1}{x}) }} }

さらに、また1/xが出てきた、また代(ry。

同じ式の中に、同じ式を代入といった。そうこれは再帰!だ。だから、ずーっとループする事ができる。このループを繰り返す事によって、


 \frac{1}{1 + \frac{1}{1 + \frac{1}{ 1+ \ddots }} }

が求まるよねー。