SICP#3まとめ　vol.1 - snow-bellの日記

SICP#3終ってかなり経つのにまとめも全くしてなかったので（ー△ー；）
いい加減まとめたいと思います(^—^)
SICP#3では定員18名のところ16名の方々に参加して頂きました
参加して頂いた方々やSICPに関わって頂いた方々全てに感謝感謝ですm(_ _)m
今回は1.2.5最大公約数から1.3高階手続きによる抽象の前までを演習＆読書しました
2:30~6:00までの時間帯でしたが休憩なしでしたw
ちょっと頑張りすぎた感もありますが・・・
その場の雰囲気で喋って集中力を切らしたら負けみたいな感じも少しありました
やってみたらあっという間なんですけど個人的には全然時間が足りなかったりしています
今回進んだページは約5pなんですが内容は・・・重いです
分からない事だらけなので自分の無知さ加減を実感出来ます

(define ( gcd a b)
 (if (= b 0)
  a
   ( gcd b (remainder a b))))

これはユークリッドの互除法を実装したものですね
ココは前勉強してたのでばっちりでしたw
だけど・・・Lameの定理なるものが今もちゃんと理解出来ていません

Lameの定理
ユークリッドのアルゴリズムである対のGCDの計算にkステップが必要なら
対の小さい方はk番目のフィボナッチ数に等しいかそれより大きい

この定理を使うとユークリッドのアルゴリズムの増加の程度が見積もれる
nを手続きへの２つの入力のうち小さい方とする
プロセスがkステップかかるとすればn ≧ Fib(k) = φ^k / √5
でなければならない
従ってステップ数kはnの(φを底とする)対数的に増加する
従って増加の程度はΘ(log n)である
(計算機プログラムの構造と解釈第２版本文そのまま)

中身がよく分かってなくてlingrで質問してみたら
ユークリッドの互除法は早いという事だと教えてもらいましたが
やっぱりよく分かりません
なのでもし詳しい方がいたら是非教えて下さい(o＞д人)
ちなみに私はやっぱり数学が出来ないので教えて下さる場合は
めっちゃレベル下げてから教えて下さい（＞人＜*）
(具体的には高校生レベルでお願いします(o；TωT)o)
長いのでvol.2へ続く・・・