乐正

Actions speak louder than words.

Sicp-ex-1-10

问题

下面过程计算一个称为Ackermann函数的数学函数:

1
2
3
4
5
6
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

下面各表达式的值是什么?

1
2
3
4
5
(A 1 10)

(A 2 4)

(A 3 3)

请考虑下面的过程,其中的A就是上面定义的过程:

1
2
3
4
5
6
7
(define (f n) (A 0 n))

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

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

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

请给出过程f、g和h对给定整数值n所计算的函数的数学定义。例如,(k n)计算的是$5n^2$.

解答

1
2
3
4
5
6
7
8
(A 1 10)
;Value: 1024

(A 2 4)
;Value: 65536

(A 3 3)
;Value: 65536

将过程f展开得,

1
(define (f n) (* 2 n))

所以, $$ (f\quad n) = 2n $$

将过程g展开,

1
2
3
4
5
6
7
(define (g n) (A 1 n))

(define (g n) (A 0
                 (A 1 (- n 1))))

;;; ... 直到 n = 1
;;; (define (g n ) (* 2 2 2 ... 2))

所以, $$ (g\quad n) = 2^n $$

同样,展开过程h

1
2
3
4
5
6
7
8
9
(define (h n) (A 2 n))

(define (h n) (A 1 (A 2 (- n 1))))

(define (h n) (A 1 (A 1 (A 2 (- n 2)))))

;;; ...

(define (h n) (A 1 (A 1 (A 1 ... (A 2 1)))))

其中,$(A\ 2\ 1) = 2$, $(A\ 1\ 2) = 2^2$。所以, $$ (h\quad n) = {2^{2^{2^\cdots}}} \text{连续求$n$次二次幂} $$

draft

« sicp-ex1-9 sicp-ex1-11 »

Comments