nobkzのブログ

連分数について、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$ 黄金数)を求める問題なんだよね。ところですべての自然数 $i$ で $N_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 }} }$

が求まるよねー。