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 反推出 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))
证明:
无论 a 和 b 是正是负,2a 3b 都是大于1的整数,所以它们的乘积是正整数。