「SICP勉強会 #4」向けの学習
読書会の全体進捗に対し、明らかに遅れてるので、予習復習です。
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4
フィボナッチ数
- exercise1.19
連続自乗をもちいた対数ステップでフィボナッチ数を求めよう。
Tはa<-b+a,b<-a (TはTpqのp=0,q=1による特殊解ってゆうかTpqが一般解?) Tpqは(a,b)をa<-bq+aq+ap,b<-bp+aq
で、そもそものTpqの式がいまいち意味不明。<<例示は理解の試金石>>というわけで、確認、確認、確認。
0, 1, 1, 2, 3, 5, 8, 13, 21, <...>
a,b,p,qと分かりづらいので、a,bを以下に置きかえる。
f(n+1)=a
f(n)=b
Tpq,p=0,q=1,f(n+1)=1,f(n)=0 f(n+2)<-0*1+1*1+1*0 >1 f(n)<-0*0+1*1 >1 Tpq,p=0,q=1,f(n+1)=1,f(n)=1 f(n+2)<-1*1+1*1+1*0 >2 f(n)<-1*0+1*1 >1 Tpq,p=0,q=1,f(n+1)=2,f(n)=1 f(n+2)<-1*1+2*1+2*0 >3 f(n)<-1*0+2*1 >2 Tpq,p=0,q=1,f(n+1)=3,f(n)=2 f(n+2)<-2*1+3*1+3*0 >5 f(n)<-2*0+3*1 >3
で、得られた数列は
0, 1, 1, 2, 3, 5, <...>
で、ままフィボナッチ数列みたいです。
で、書いてて気づいたけど
Tpqは(a,b)をa<-bq+aq+ap,b<-bp+aq
って、
X=bq+aq Y=ap Tpqは(a,b)をa<-X+Y,b<-X
の形式ですね。だから何といわれても困りますが。
で、読んでて気づいたけど、上記のX,Yへの置換は間違ってますねw;
消しておきます。
wikipediaのフィボナッチ数列一般項の行列表現につながりそうかなって思った。
ん、ん、ん。
初期値をf(0)=p,f(1)=q p,q, f(2) = f(1)+f(0) = q+p p,q,p+q, f(3) p,q,p+q,p+2q, f(4) p,q,p+q,p+2q,2p+3q,
ん〜、ん。
Tpqの導出できない。
ちょっと休憩