]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ch1_2.clj
rewrite `quote->cons' using `match'.
[sicp.git] / src / sicp / ch1_2.clj
1 (ns sicp.ch1-2
2   (:use [sicp.utils :only (square)]
3         [clojure.contrib.math :only (sqrt expt)]
4         [clojure.contrib.trace :only (dotrace)]))
5
6
7 (defn factorial [n]
8   (if (= n 1)
9     1
10     (* n (factorial (- n 1)))))
11
12 ;; stack friendly version
13 (defn factorial2 [n]
14   (loop [x n acc 1] 
15     (if (= x 1)
16       acc
17       (recur (- x 1) (* acc x)))))
18
19 ;; even better
20 (defn factorial3 [n]
21   (reduce * (range 1 (inc n))))
22
23 ;; (comment
24 ;;  user> (dotrace [factorial] (factorial 3))
25 ;;  TRACE t2701: (factorial 3)
26 ;;  TRACE t2702: |    (factorial 2)
27 ;;  TRACE t2703: |    |    (factorial 1)
28 ;;  TRACE t2703: |    |    => 1
29 ;;  TRACE t2702: |    => 2
30 ;;  TRACE t2701: => 6
31 ;;  6
32 ;; )
33
34 ;; (comment
35 ;;   sicp.chapter1.ch1_2> (dotrace [factorial] (factorial 6))
36 ;;   TRACE t2778: (factorial 6)
37 ;;   TRACE t2779: |    (factorial 5)
38 ;;   TRACE t2780: |    |    (factorial 4)
39 ;;   TRACE t2781: |    |    |    (factorial 3)
40 ;;   TRACE t2782: |    |    |    |    (factorial 2)
41 ;;   TRACE t2783: |    |    |    |    |    (factorial 1)
42 ;;   TRACE t2783: |    |    |    |    |    => 1
43 ;;   TRACE t2782: |    |    |    |    => 2
44 ;;   TRACE t2781: |    |    |    => 6
45 ;;   TRACE t2780: |    |    => 24
46 ;;   TRACE t2779: |    => 120
47 ;;   TRACE t2778: => 720
48 ;;   720
49 ;;   )
50
51 ;; (comment
52 ;;   sicp.chapter1.ch1_2> (dotrace [factorial2] (factorial2 6))
53 ;;   TRACE t2806: (factorial2 6)
54 ;;   TRACE t2806: => 720
55 ;;   720
56 ;;   )
57
58 (defn fact-iter [product counter max-count]
59   (if (> counter max-count)
60     product
61     (fact-iter (* product counter)
62                (inc counter)
63                max-count)))
64
65 (defn factorial [n]
66   (fact-iter 1 1 n))
67
68 ;; (comment
69 ;; user> (dotrace [factorial fact-iter] (factorial 6))
70 ;; TRACE t2378: (factorial 6)
71 ;; TRACE t2379: |    (fact-iter 1 1 6)
72 ;; TRACE t2380: |    |    (fact-iter 1 2 6)
73 ;; TRACE t2381: |    |    |    (fact-iter 2 3 6)
74 ;; TRACE t2382: |    |    |    |    (fact-iter 6 4 6)
75 ;; TRACE t2383: |    |    |    |    |    (fact-iter 24 5 6)
76 ;; TRACE t2384: |    |    |    |    |    |    (fact-iter 120 6 6)
77 ;; TRACE t2385: |    |    |    |    |    |    |    (fact-iter 720 7 6)
78 ;; TRACE t2385: |    |    |    |    |    |    |    => 720
79 ;; TRACE t2384: |    |    |    |    |    |    => 720
80 ;; TRACE t2383: |    |    |    |    |    => 720
81 ;; TRACE t2382: |    |    |    |    => 720
82 ;; TRACE t2381: |    |    |    => 720
83 ;; TRACE t2380: |    |    => 720
84 ;; TRACE t2379: |    => 720
85 ;; TRACE t2378: => 720
86 ;; 720
87 ;; )
88
89 ;; observation: clojure loop-recur construct is essentially the same as
90 ;; the iterative version.
91
92 ;; section 1.2.2: Tree Recursion
93 (defn fib [n]
94   (cond (= n 0) 0
95         (= n 1) 1
96         :else (+ (fib (- n 1))
97                  (fib (- n 2)))))
98
99 ;; iterative version
100 (defn fib-iter [a b count]
101   (if (= count 0)
102     b
103     (fib-iter (+ a b) a (dec count))))
104
105 (defn fib [n]
106   (fib-iter 1 0 n))
107
108 ;; example: counting changes
109 (defn first-denomination [kinds-of-coins]
110   (cond (= kinds-of-coins 1) 1
111         (= kinds-of-coins 2) 5
112         (= kinds-of-coins 3) 10
113         (= kinds-of-coins 4) 25
114         (= kinds-of-coins 5) 50))
115
116
117 (defn first-denomination [kinds-of-coins]
118   ({1 1 2 5 3 10 4 25 5 50} kinds-of-coins))
119
120 (defn cc [amount kinds-of-coins]
121   (cond (= amount 0) 1
122         (or (< amount 0) (= kinds-of-coins 0)) 0
123         :else (+ (cc amount (- kinds-of-coins 1))
124                  (cc (- amount
125                         (first-denomination kinds-of-coins))
126                      kinds-of-coins))))
127
128 (defn count-change [amount]
129   (cc amount 5))
130
131
132
133
134
135 ;; 1.2.4: exponentiation
136 ;; computing b^n
137
138 ;; iterative
139 (defn expt-iter [base counter product]
140   (if (= counter 0)
141     product
142     (expt-iter base
143                (dec counter)
144                (* product base))))
145
146 (defn myexpt [b n]
147   (expt-iter b n 1))
148
149 (defn myexpt [b n]
150   (if (= n 0)
151     1
152     (* b (myexpt b (dec n)))))
153
154 ;; fast version
155 (defn fast-expt [b n]
156   (cond (= n 0) 1
157         (even? n) (square (fast-expt b (/ n 2)))
158         :else (* b (fast-expt b (dec n)))))
159
160
161
162 ;;;  Section 1.2.5: GCD
163 (defn mygcd [a b]
164   (if (= b 0)
165     a
166     (mygcd b (rem a b))))
167
168 ;;; section 1.2.6 Primality testing.
169 (defn divides? [a b]
170   (= (rem b a) 0))
171
172 (defn find-divisor [n test-divisor]
173   (cond (> (square test-divisor)  n) n
174         (divides? test-divisor n) test-divisor
175         :else (find-divisor n (inc test-divisor))))
176
177 (defn smallest-divisor [n]
178   (find-divisor n 2))
179
180 (defn prime? [n]
181   (= (smallest-divisor n) n))
182
183
184 ;; fermat's little theorem
185 (defn expmod [base exp m]
186   (cond (= exp 0) 1
187         (even? exp) (rem (square (expmod base (/ exp 2) m))
188                          m)
189         :else (rem (* base (expmod base (dec exp) m))
190                    m)))
191
192 (defn try-it [a n]
193   (= a (expmod a n n)))
194
195 (defn fermat-test [n]
196   (try-it (+ 1 (rand-int (- n 1))) n))
197
198 (defn fast-prime? [n times]
199   (cond (= times 0) true
200         (fermat-test n) (fast-prime? n (dec times))
201         :else false))
202
203