2.5

练习 2.5 请证明,如果将 a 和 b 的序对表示为乘积 2a 3b 对应的整数,我们就可以只用非负整数和算术运算表示序对。请给出对应的过程 cons、car 和 cdr 的定义。

先来试一试:

 
(define (cons a b) (* (expt 2 a) (expt 3 b)))
(display (cons 2 3))
108

注意到以上结果是 108。要从 108 反推出 a 和 b,只需要将它除以 2 和 3,看分别能被整除几次即可。

由于 108 除以 2 是 54,54 再除以 2 是 27,27 不能再被 2 整除,于是 108 可以被 2 整除两次,即 a = 2。

又由于 108 除以 3 是 36,36 再除以 3 是 9,9 不能再被 3 整除,于是 108 可以被 3 整除两次,即 b = 3。

 
(define (cons a b) (* (expt 2 a) (expt 3 b)))
(display (cons 2 3))
(newline)
 
(define (number-of-division n divisor) (if (= n (ceil n)) (+ 1 (number-of-division (/ n divisor) divisor)) 0))
 
(define (car r) (- (number-of-division r 2) 1))
(define (cdr r) (- (number-of-division r 3) 1))
 
(define r (cons 2 3))
(newline)
(display "r is ") (display r)
(newline)
(display "car r is ") (display (car r))
(newline)
(display "cdr r is ") (display (cdr r))
108

r is 108
car r is 2
cdr r is 3

证明:

无论 a 和 b 是正是负,2a 3b 都是大于1的整数,所以它们的乘积是正整数。

results matching ""

    No results matching ""