sicp/section1.2.scm at master · pravnar/sicp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
;; Exercise 1.9

(define (+rec a b)
  (if (= a 0)
      b
      (inc (+rec (dec a) b))))

(define (+iter a b)
  (if (= a 0)
      b
      (+iter (dec a) (inc b))))

;; Evaluation using the substitution model

;; (+rec 4 5)
;; => (inc (+rec (dec 4) 5))
;; => (inc (+rec 3 5))
;; => (inc (inc (+rec (dec 3) 5)))
;; => (inc (inc (+rec 2 5)))
;; => (inc (inc (inc (+rec (dec 2) 5))))
;; => (inc (inc (inc (+rec 1 5))))
;; => (inc (inc (inc (inc (+rec (dec 1) 5)))))
;; => (inc (inc (inc (inc (+rec 0 5)))))
;; => (inc (inc (inc (inc 5))))
;; => (inc (inc (inc 6)))
;; => (inc (inc 7))
;; => (inc 8)
;; => 9

;; (+iter 4 5)
;; => (+iter (dec 4) (inc 5))
;; => (+iter 3 6)
;; => (+iter (dec 3) (inc 6))
;; => (+iter 2 7)
;; => (+iter (dec 2) (inc 7))
;; => (+iter 1 8)
;; => (+iter (dec 1) (inc 8))
;; => (+iter 0 9)
;; 9


;; Exercise 1.10

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))
;; > (A 1 10)
;; 1024
;; > (A 2 4)
;; 65536
;; > (A 3 3)
;; 65536

(define (f n) (A 0 n))
;; (f n) = 2n

(define (g n) (A 1 n))
;; (g n) = 2^n

(define (h n) (A 2 n))
;; (h n) = 2^(2^(...^2) (with n '2's in total)
;; Better definition: (h n) = 2^(2^n)

;; (A 2 4)
;; => (A 1 (A 2 3))
;; => (A 1 (A 1 (A 2 2)))
;; => (A 1 (A 1 (A 1 (A 2 1))))
;; => (A 1 (A 1 (A 1 2)))
;; => (A 1 (A 1 2^2))
;; => (A 1 2^(2^2))
;; => 2^(2^(2^2))

;; (A 2 3)
;; => (A 1 (A 2 2))
;; => (A 1 (A 1 (A 2 1)))
;; => (A 1 (A 1 2))
;; => (A 1 2^2)
;; => 2^(2^2)

;; (A 2 2)
;; => (A 1 (A 2 1))
;; => (A 1 2)
;; => 2^2


;; Exercise 1.11
;; f(n) = | n                                  if n<3
;;        | f(n - 1) + 2f(n - 2) + 3f(n - 3)   otherwise

;; Recursive
(define (frec n)
  (if (< n 3)
      n
      (+ (frec (- n 1))
         (* 2 (frec (- n 2)))
         (* 3 (frec (- n 3))))))

;; Iterative
(define (fiter n)
  (fiter-helper 2 1 0 n))

(define (fiter-helper a b c count)
  (cond ((< count 0) count)
        ((= count 0) c)
        ((= count 1) b)
        (else (fiter-helper (+ a (* 2 b) (* 3 c)) a b (- count 1)))))


;; Exercise 1.12
(define (pascal r c)
  (cond ((or (<= r 0) (<= c 0))
         (errorf 'pascal "Pascal's triangle's indices start at 1"))
        ((or (= c 1) (= c r)) 1)
        (else (+ (pascal (- r 1) (- c 1)) (pascal (- r 1) c)))))

(define (print-pascal n)
  (when (> n 0)
    (print-pascalrow n 1)
    (printf "~%")
    (print-pascal (- n 1))))

(define (print-pascalrow r c)
  (when (<= c r)
    (printf "~a " (pascal r c))
    (print-pascalrow r (+ c 1))))