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

版本8和14间的区别 (跳过第6版)

Procedures and the Processes They Generate

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 13:44:19修订的的版本8 → 
  大小: 2431
  编辑: czk
  备注:
+   ← 于2008-02-23 15:36:44修订的的版本14 → ⇥
  大小: 5208
  编辑: localhost
  备注: converted to 1.6 markup
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 1:
-[[TableOfContents]]
+<<TableOfContents>>
 行号 71:
+. {{{
(count-change 100)
292
}}}{{{#!python
count_change(100)
}}}
-行号 73:
+行号 79:
+. {{{
(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
}}}
-行号 74:
+行号 116:
+. {{{
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))
}}}{{{#!python
gcd = lambda a, b: a if b==0 else gcd(b, a%b)
}}}
-行号 75:
+行号 125:
+. {{{
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
}}}{{{#!python
smallest_divisor = lambda n: find_divisor(n, 2)
find_divisor = lambda n, test_divisor: n if square(test_divisor) > n else test_divisor if divides(test_divisor, n) else find_divisor(n, test_divisor+1)
divides = lambda a, b: b%a==0
}}}
 1. {{{
(define (prime? n)
  (= n (smallest-divisor n)))
}}}{{{#!python
prime = lambda n: n==smallest_divisor(n)
}}}
 1. {{{
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))   
}}}{{{#!python
expmod = lambda base, exp, m: 1 if exp==0 else square(expmod(base, exp/2, m))%m if even(exp) else (base*expmod(base, exp-1, m))%m
}}}
 1. {{{
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))
}}}{{{#!python
from random import randint
def fermat_test(n):
    try_it = lambda a: expmod(a, n, n) == a
    return try_it(1+randint(0, n-2))
}}}
 1. {{{
(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))
}}}{{{#!python
fast_prime = lambda n, times: True if times==0 else fast_prime(n, times-1) if fermat_test(n) else False
}}}