"SICP的Python实现/SICP的Python实现1.2"版本比较

版本1和9间的区别 (跳过第8版)

Procedures and the Processes They Generate

1. Linear Recursion and Iteration

```
(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))
```
```
   1 factorial = lambda n: 1 if n==1 else n*factorial(n-1)
```

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

   1 fatorial = lambda n: fact_iter(1, 1, n)
   2 fact_iter = lambda product, counter, max_count: product if counter > max_count else fact_iter(counter*product, counter +1, max_count)

2. Tree Recursion

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

   1 fib = lambda n: 0 if n==0 else ( 1 if n==1 else fib(n-1)+fib(n-2) )

(define (fib n)
  (fib-iter 1 0 n))

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

   1 fib = lambda n: fib_iter(1, 0, n)
   2 fib_iter = lambda a, b, count: b if count ==0 else fib_iter(a+b, a, count-1)

(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)))

   1 count_change = lambda amount: cc(amount, 5)
   2 cc = lambda amount, kinds_of_coins: 1 if amount==0 else 0 if amount < 0 or kinds_of_coins == 0 else cc(amount, kinds_of_coins-1)+cc(amount-first_denomination(kinds_of_coins), kinds_of_coins)
   3 first_denomination = lambda kinds_of_coins: 1 if kinds_of_coins==1 else 5 if kinds_of_coins==2 else 10 if kinds_of_coins==3 else 25 if kinds_of_coins==4 else 50 if kinds_of_coins==5 else 0

```
(count-change 100)
292
```
```
   1 count_change(100)
```

3. Orders of Growth

4. Exponentiation

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

SICP的Python实现/SICP的Python实现1.2 (2008-02-23 15:36:44由localhost编辑)

-  ⇤ ← 于2007-04-16 10:47:34修订的的版本1 → 
  大小: 311
  编辑: czk
  备注:
+   ← 于2007-04-16 13:56:20修订的的版本9 → ⇥
  大小: 3420
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 1:
-.2  Procedures and the Processes They Generate
            1.2.1  Linear Recursion and Iteration
            1.2.2  Tree Recursion
            1.2.3  Orders of Growth
            1.2.4  Exponentiation
            1.2.5  Greatest Common Divisors
            1.2.6  Example: Testing for Primality
+[[TableOfContents]]

== Procedures and the Processes They Generate ==
=== Linear Recursion and Iteration ===
 1. {{{
(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))
}}}{{{#!python
factorial = lambda n: 1 if n==1 else n*factorial(n-1)
}}}
 1. {{{
(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))
}}}{{{#!python
fatorial = lambda n: fact_iter(1, 1, n)
fact_iter = lambda product, counter, max_count: product if counter > max_count else fact_iter(counter*product, counter +1, max_count)
}}}
=== Tree Recursion ===
 1. {{{
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
}}}{{{#!python
fib = lambda n: 0 if n==0 else ( 1 if n==1 else fib(n-1)+fib(n-2) )
}}}
 1. {{{
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
}}}{{{#!python
fib = lambda n: fib_iter(1, 0, n)
fib_iter = lambda a, b, count: b if count ==0 else fib_iter(a+b, a, count-1)
}}}
 1. {{{
(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)))
}}}{{{#!python
count_change = lambda amount: cc(amount, 5)
cc = lambda amount, kinds_of_coins: 1 if amount==0 else 0 if amount < 0 or kinds_of_coins == 0 else cc(amount, kinds_of_coins-1)+cc(amount-first_denomination(kinds_of_coins), kinds_of_coins)
first_denomination = lambda kinds_of_coins: 1 if kinds_of_coins==1 else 5 if kinds_of_coins==2 else 10 if kinds_of_coins==3 else 25 if kinds_of_coins==4 else 50 if kinds_of_coins==5 else 0
}}}
 1. {{{
(count-change 100)
292
}}}{{{#!python
count_change(100)
}}}
=== Orders of Growth ===
=== Exponentiation ===
 1. {{{
(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))
}}}{{{{#!python
expt = lambda b, n: 1 if n==0 else b*expt(b, n-1)
}}}
 1. {{{
(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product)))) 
}}}{{{#!python
expt = lambda b, n: expt_iter(b, n, 1)
expt_iter = lambda b, counter, product: product if counter==0 else expt_iter(b, counter-1, b*product)
}}}
 1. {{{
(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))
}}}{{{#!python
fast_expt = lambda b, n: 1 if n==0 else square(fast_expt(b, n/2)) if even(n) else b*fast_expt(b, n-1)
}}}
 1. {{{
(define (even? n)
  (= (remainder n 2) 0))
}}}{{{#!python
even = lambda n: n%2 == 0
}}}
=== Greatest Common Divisors ===
=== Example: Testing for Primality ===