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