sicpはじめから1.13の途中まで

長い。続きを読むという表示にする方法を後で調べる。

;;練習
;;(3*((2*4) + (3+5))) + ((10-7) + 6)
(+ (* 3
      (+ (* 2 4)
	 (+ 3 5)))
   (+ (- 10 7)
      6))
;57

;;m1.1
10 ; => 10
(+ 5 3 4) ;=> 12
(-9 1) ; => 8
(/ 6 2) ; => 3
(+ (* 2 4) (- 4 6)) ;=>6

(define a 3) ;=>a
(define b (+ a 1)) ; =>b
(+ a b (* a b)) ; => 19
(= a b) ;#f ;;たぶんfalse

(if (and (> b a) (< b (* a b)))
    b
    a)
;=> 4

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
;=> 16

(+ 2 (if (> b a) b a))
;=>6

(* (cond ((> a b) a)
	 ((< a b) b)
	 (else -1))
   (+ a 1))
;=>16

;;m1.2
(/ (+ 5
      4
      (- 2 (- 3 (+ 6 (/ 4 5))))
      )
   (* 3 (- 6 2) (- 2 7))) 
;=>-37/150
;;後であっているか確認にしたほうがいいかも

;;m1.3
(define (g x y) (+ (* x x) (* y y)))
(define (f x y z)
  (if (<= x y) 
	 (if (<= x z) (g y z) (g y x))
	 (if (<= y z) (g x z) (g x y))))

;;m1.4
(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))
;;こんな書き方できるんだ。なんかevalみたい
;;答えは、bの絶対値をaに足す関数。

;;m1.5
(define (p) (p))
(define (test x y)
  (if (= x 0))
  0
  y))
(test 0 (p))
;;作用的順序の場合
;;    p->p->pの無限ループ
;;正規的順序の場合
;;    if文の分岐よりx==0なので、0が出力される。

;1.1.7 平方根の計算
(define (sqrt x) 
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
	guess
	(sqrt-iter (improve guess x)
		   x)))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (average x y)
    (/ (+ x y) 2))
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001)))
;;これをさらに簡単にできるらしい。
;;||
;;\/
(define (square x) (* x x))
(define (abs x)
  (if (<= x 0) (- 0 x) x))
(define (average x y)
  (/ (+ x y) 2))
  ;上の式はわけておいた方が見やすいかも。

(define (sqrt x) 
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
	guess
	(sqrt-iter (improve guess))))
  (sqrt-iter 1.0))
　　;たぶん、sqrtに渡されている引数は、
;その中の関数に明示的に渡さなくても使えるってことだと思う。

;;m1.6
;ifが特殊形式である理由が分からない。＝特殊形式でないときに起こる問題が見付からない。
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
	(else else-clause)))
(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
	  guess
	  (sqrt-iter (improve guess x)
		     x)))
;1.1.3の図1.1は下から順に進んでいる。
;ということで、(f (g ..) ..)のような式の場合には、最も中のものから順に計算される。
;;たぶん、これが特殊形式以外の場合の計算される順序（一般形式？）。
;;ということで、new-ifが終了していいかどうか判断しようとしたときに、
;new-ifの引数のelse-clauseの部分のsqrt-iterが計算を繰り返す。暴走->終わらない。

;m1.7
;1.7.1（小さい数、大きい数の場合good-enough?が失敗する理由を考える）
;;1,7,2
;;繰り返しから、次のguessの変化に着目
;;後で考える。

;;m1.8
(define (cubic x) (* x x x))
(define (curt x)
  (define (good-enough? guess)
    (< (abs (- (cubic guess) x)) 0.001))
  (define (improve guess)
    (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
  (define (curt-iter guess)
    (if (good-enough? guess)
    guess
    (curt-iter (improve guess))))
    (curt-iter 1.0))

;;1.2.1(再帰プロセス)
(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))
;;線形再帰的プロセス(recursive process)

(define (factorial2 n)
  (define (fact-iter product counter max-count)
    (if (> counter max-count)
	product
	(fact-iter (* counter product)
		   (+ counter 1)
		   max-count)))
  (fact-iter 1 1 n))
;;反復的プロセス(iterative process)
;; 反復的プロセス分からない。たぶん、書けない。難しい。

;;これでいいような気がする…
(define (factorial3 n)
  (define (f a b)
    (if (= b 0)
	a
	(f (* a b) (- b 1))))
  (f 1 n))

;;m1.9
;;置き換えモデルめんどくさそうです＞＜。
;;たぶん、上が再帰的。下が反復的。
;;(inc（+ (dec a) b))の方は計算が助長な感じ。
;(inc (..この中が計算終わってから))incの計算が始まると思う。

;;m1.10
;;めんどくさそう。後で考える。
;;というか、どういう風に書いたいいのか分かりません＞＜

;1.2.2
(define (fib n)
  (cond ((= n 0) 0)
	((= n 1) 1)
	(else (+ (fib (- n 1)) (fib (- n 2))))))

(define (fib2 n)
  (define (fib-iter a b count)
    (if (= count 0)
	b
	(fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
	((or (< amount 0) (= kinds-of-coins 0)) 0)
	(else (+ (cc amount
		     (- kinds-of-coins 1))
		 (cc (- amount
			(first-denomination kinds-of-coins))
		     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
	((= kinds-of-coins 2) 5)
	((= kinds-of-coins 3) 10)
	((= kinds-of-coins 4) 25)
	((= kinds-of-coins 5) 50)))

;;m1.11
(define (f1 n)
  (if (< n 3)
      n
      (+ (f1 (- n 1))
	 (* 2 (f1 (- n 2))) 
	 (* 3 (f1 (- n 3))))))
;再帰的

(define (f2 n)
  (define (f-iter a b c count)
    (if (= count n)
	a
	(f-iter (+ a (* 2 b) (* 3 c)) a b (+ count 1))))
  (if (< n 3)
      n
      (f-iter 4 2 1 3)))
;できた。反復的な方法。一応。(f1と返す値は一緒。はじめから値を入れておくってずるいような気もしないでもない。）

;;m1.12
(define (pascal n k)
  (define (calc n k)
    (cond ((= k 1) 1) 
	  ((= n k) 1)
	  (else (+ (calc (- n 1) (- k 1)) (calc (- n 1) k)))))
    (if (or (<= n 0) (<= k 0) (< n k))
	     -1
	     (calc n k)))
;;再帰的な方法

;;m1.13
;;今からやる。
;;  最も近い整数であることの証明。
;;  問いよりFib(n)=(θ-Ψ)/√5と書いてあるので、
;;  |((θ^n-(θ^n-Ψ^n))/√5| < 0.5を示せばいい。
;;  あとは、Fib(n)=(θ-Ψ)/√5が証明できればいいんだけど…分かりません＞＜     

m1.7,m1.9（実際に紙に書く),m1.10はあとでやる。

追記

Fib(n) = (θ^n - ψ^n)/√5
証明できた。ただ計算すればいいだけだった。
その前に「ψ^2=ψ+1」を証明する必要があった。

ψ^2=1/4*(1-√5)^2
   =1/2*(3-√5)
ψ+1=1/2*(1-√5)+1
   =1/2*(3-√5)=ψ^2

これから、本題

when n=0
L:Fib(0)=0
R:θ^0+ψ^0/√5
  =0/√5
  =0
L=R

when n=1
L:Fib(1)=1
R:((1+√5)-(1-√5))/2√5
  =2√5/2√5
L=R
when n=k+1 (ただし、n=k,k-1の時に成り立つことを仮定する)
Fib(k+1)=Fiψ(k) + Fiψ(k-1)
        =(1/√5)*((θ^k-ψ^k)+(θ^(k-1)-ψ^(k-1)))/2
        =(1/2√5)*(2(1+θ)*θ^(k-1)-2((1+ψ)*ψ^(k-1)))

ここで、θ^2=θ+1, ψ^2=ψ+1より、
        =(1/2√5)*(2(θ^2)*θ^(k-1)-2(ψ^2)*ψ^(k-1))
        =(1/2√5)*(2θ^(k+1) - 2ψ^(k+1))
        =(θ^(k+1) - ψ^(k+1))/√5
        =R

証明完了。疲れた。