SICP 全笔记

Exercise 1.10. The following procedure computes a mathematical function called Ackermann’s function.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

What are the values of the following expressions?

(A 1 10)

(A 2 4)

(A 3 3)

Consider the following procedures, where A is the procedure defined above:

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes $5n^2$.

分析 (A 1 10) (A 2 4)

(A 1 10)

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2 2)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2 2 2))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2 2 2 2)))))
(A 0 (A 0 (A 0 (A 0 (* 2 2 2 2 2 2))))
(A 0 (A 0 (A 0 (* 2 2 2 2 2 2 2)))
(A 0 (A 0 (* 2 2 2 2 2 2 2 2)))
(A 0 (* 2 2 2 2 2 2 2 2 2))
(* 2 2 2 2 2 2 2 2 2 2)
1024

(A 2 4)

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

即 $2^{2^{2^2}}$

总结

(A 0 n)

$$2 \times n $$

(A 1 n)

(A 1 n)
(A 0 (A 1 (- n 1)))
(A 0 (A 0 (A 1 (- n 2))))
...
(A 0 (A 0 (A 0 (.. (A 1 1)))))
(A 0 (A 0 (A 0 (.. 2))))
(A 0 (A 0 (* 2 2 .. 2)))

即为 $2^n$

(A 2 n)

(A 2 n) 可以转化为 n 个 (A 1 ..)。即为

$$2^{2^{2^{2^{⋰}}}} $$

测试

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))


(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (f1 n) (* 2 n))

(define (g1 n) (expt 2 n))

(define (h1 n)
  (cond ((= n 0) 1)
        (else
         (expt 2 (h1 (- n 1))))))
;;; tests begin
(load "../testframe.scm")

(for-each (lambda (n)
            (assert= (f n) (f1 n))
            (assert= (g n) (g1 n)))
          '(1 2 3 4 5 6 7 8 9 10))

(for-each (lambda (n)
            (assert= (h n) (h1 n)))
          '(1 2 3 4)) ; n should be < 5 for saving time on calculation