第四章 numbers games
14 是原子吗
是的，数都是原子
(atom? n) 是真还是假，其中n是14
真，14 是原子
-3是数吗
是的，不过我们暂不考虑负数
3.14159是数吗
是的，不过我们仅仅考虑whole numbers
(add1 n)是多少，其中n是67
68
注：
Lisp中：1+
Scmeme：
(define add1
(lambda (n)
(+ n 1)))
(add1 67) 是多少
68。同上
(sub1 n) 是多少，其中n是5
4
注：
Lisp中：1-
Scmeme中：
(define sub1
(lambda (n)
(- n 1)))
(sub1 0) 是多少
没有答案
注：
我们仅仅考虑非负数。实际是-1。
(zero? 0) 是真还是假
真
注：
Lisp中：zerop
(zero? 1492) 是真是假
假
(+46 12) 是多少
58
试试写下函数+
提示：使用zero? add1 和sub1
(define +
(lambda a b)
(cond
((zero? b) a)
(else (add1 (+ a (sub1 b))))
很简单不是吗
注：
Lisp，Scheme中:这个有点像+。应写成O+(参看preface)
但是我们不是没有遵循第一戒吗
是的，但是我们可以把zero?看作是null?一样，因为zero?可以查询一个数是否是空 就如同null?查询一个list是否是空。
如果zero?像null?,那么add1像cons
对！cons构建list表，add1构建数
(- 14 3) 是多少
11
(- 17 9) 是多少
8
(-18 25) 是多少
没有答案。未考虑负数。
试试写下函数-
提示：使用sub1
下面这个如何
(define -
(lambda a b
(cond
((zero? b) a)
(else (sub1 (- a (sub1 b)))))))
注：
Lisp，Scheme中:这个有点像-。应写成O-(参看preface)
你能描述一下(- a b) 是如何工作的吗
输入两个参数，把第二个参数减一直到0，同时每次把第一个参数减一。
(2 11 3 79 47) 这是一个tup吗
是的，tuple是tuple的简写。
(8 55 5 555) 这是一个tup吗
是的，是一个数字组成的list
(1 3 8 apple 4 3) 这是一个tup吗
不是，这只是一个原子组成的list表。
(3 (7 4) 13 9) 这是一个tup吗
不是，(7 4)不是一个数
() 这是一个tup吗
是的，这是一个特殊的空tup
tup 是 (3 5 2 8) 那么(addtup tup) 是什么
18
tup 是 (15 6 7 12 3) (addtup tup) 是什么
43
addup做什么了
返回一个tuple参数的所有数成员的总和。
怎样从一个list构建数
用+替代cons：+构建数就像cons构建list表
当用cons构建list表，终止条件是()，那么+的终止条件呢
0
list 的自然终止条件
(null? l)
tup 的自然终止条件
(null? tup)
当从一个list表的数创建一个书，终止条件是啥样
((null? tup) 0) 如同 ((null? l) (quote ())) 是从list创建list的终止条件
addtup的终止条件
((null? tup) 0)
lat 是怎么定义的
空表，或者成员都是原子的list表。
tup 是怎么定义的
空表，或者成员都是数的list表。
list 的自然递归终止条件是什么
(cdr lat)
tup 的自然递归终止条件是什么
(cdr tup)
为什么
因为剩余的非空表是表，剩余的非空tup是一个tup
list 需要几个查询
两个
tup 需要几个查询
两个。空tup的情况，以及非空tup的情况。
数是怎么定义的
0，或者从一个数增加一递归得到。
数的 自然递归终止条件是什么
(zero? n)
数的自然递归是什么
(sub1 n)
数需要多少个查询
两个。
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
第一戒 (第一次修订)
当递归atom原子，lat时，两个查询：(null? lat) 和else
当递归数n时,两个查询：(zero? n) 和else
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
cons 是做什么的
构建list表
addup 是做什么的
从tup的所有数成员构建一个总和数。
addup 的终止条件
((null? tup) 0)
addup 的自然递归是什么
(addtup (cdr tup))
addup 用什么构建数
用+，因为+也构建数
填写下面的定义
(definei addup
(lambda (tup)
(cond
((null? tup) 0)
(else ...))))
下面这是我们填写的
(+ (car tup) (addup (cdr tup)))
注意这行与rember函数的这行非常相近：
(cons (car lat) (rember a (cdr lat)))
(x 5 3) 是多少
15
(x 13 4) 是多少
64
(x n m) 做什么
做乘法，求n和m的乘积
x 的终止条件是什么
((zero? m) 0)，因为nx0=0
既然(zero? m)是终止条件，m必须最终减到一，那么怎样做到
用sub1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
第四戒 (第一次修订)
递归时至少要有一个参数变化，并且向终止条件方向变化。变化的参数必须有终止测试条件：当时用cdr时，用null?当使用sub1，用zero?
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(x n (sub1 m)) 是啥
x的自然递归。
试试写下函数x
(define x
(lambda n m
(cond
((zero? m) 0)
(else (+ n (x n (sub1 m)))))))
注：
Lisp，Scheme中：有点像*
(x 12 3) 是多少
36。让我们一步步看函数是怎么得到值的。
(zero? m)
否。
(+ m (x m (sub1 n))) 是什么意思
把n(n=12)加到自然递归上。如果x正确的话，那么(x 12 (sub1 3))应该是24
(x n m) 的新参数是什么
n是12，m是2
(zero? m)
否。
(+ m (x m (sub1 n))) 是什么意思
把n(n=12)加到(x n (sub1 m))
(x n m) 的新参数是什么
n是12，m是1
(zero? m)
否。
(+ m (x m (sub1 n))) 是什么意思
把n(n=12)加到(x n (sub1 m))
下面这行是多少
((zero? m) 0)
0，因为(zero? 0)现在为true
完成了吗
没呢
为什么
还有3个+没计算呢
原始应用的值是多少
12加到12加到12加到0上，得到36。n加了m次。
用等式表示就是：
(x 12 3) = 12 + (x 12 2)
= 12 + 12 +( x 12 1)
= 12 + 12 + 12 (x 12 0)
= 12 + 12 + 12 + 0
= 36
为什么0是x的终止条件
因为0不影响+,n+0=n
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
第五戒
当用+构建一个值时，使用0作为终止值，因为0不改变加法的值。
当用x构建一个值时，使用1作为终止值，因为1不改变乘法的值。
当用cons构建list表，终止条件是()
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
tup1是(3 6 9 11 4)，tup2是(8 5 2 0 7)，问(tup+ tup1 tup2)是什么
(11 11 11 11 11)
tup1是(2 3)，tup2是(4 6)，问(tup+ tup1 tup2)是什么
(6 9)
(tup+ tup1 tup2)做什么
把所有tup1和tup2的元素一一对应加，tup的长度相同。
tup+ 有什么特殊之处
每次查找两个tup的元素，即每次递归都是处理两个元素。
递归tup需要多少个查询。
两个。(null? tup) 和else
当对两个tup递归时，需要查询多少个问题。
四个。第一个tup是空或者非空。第一个tup是空或者非空。
就是这几个吗
(and (null? tup1) (null? tup2))
(null? tup1)
(null? tup2)
else
没错
当第一个tup是()时，第二个tup不是()可以吗
否，因为两个tup必须一样长。
也就是仅仅需要
(and (null? tup1) (null? tup2))
else
对吗
是的，因为(null? tup1)真时，(null? tup2)也是真。
写出函数tup+
;;tup1 and tup2 must be the same length
(define tup+
(lambda (tup1 tup2)
(cond
((and (null? tup1) (null? tup2)) (quote ()))
(else (cons (+ (car tup1) (car tup2)) (tup+ (cdr tup1) (cdr tup2)))))))
'(1 2 3)
'(4 5 6)
(tup+ '(1 2 3)'(4 5 6))
DrRacket环境测试结果为
(1 2 3)
(4 5 6)
(5 7 9)
比较简单就不详细解释了。
(> 12 133)
#f真
(> 120 11)
#t假
需要多少个数来迭代。
n和m
怎么迭代
(sub1 n)和(sub1 m)
什么时候递归
当有一个数都不是零时。
n和m需要多少个查询
三个(zero? n), (zero? m),以及else
现在你能用zero?和sub1写出函数>吗
下面这个对吗
(define >
(lambda (n m)
(cond
((zero? m) #t)
((zero? n) #f)
(else (> (sub1 n) (sub1) m)))))
不对，没有考虑到m与n相等时的情形，m与n最后同时递归到0。结果取了第一种情况(zero? m) #t了。可以把两种情况交换下顺序。
(define >
(lambda (n m)
(cond
((zero? m) #t)
((zero? n) #f)
(else (> (sub1 n) (sub1) m)))))
下面是<函数的定义
(define <
(lambda (n m)
(cond
((zero? m) #t)
((zero? n) #f)
(else (< (sub1 n) (sub1) m)))))
下面是=的定义
(define =
(lambda (n m)
(cond
((and (zero? m) (zero? n)) #t)
((and (zero? m) (not (zero? n)) #f))
((and (not (zero? m) (zero? n)) #f))
(else (= (sub1 n) (sub1) m)))))
可以简写为
(define =
(lambda (n m)
(cond
((zero? m) (zero? n))
((zero? n) #f)
(else (= (sub1 n) (sub1) m)))))
第一个分支，当m已经递归到0时函数的值由(zero? n)决定，它为真则函数返回真，它为假函数则返回假；第二个分支，m未到0，而n已递归到0，那么显然为假。
用函数<和函数>重写函数=
(define =
(lambda (n m)
(cond
((> n m) #f)
((< n m) #f)
(else #t))))
就是说我们有两个函数来比较atom原子是否有相等对么
对。用=查询书，用eq? 查询其它的。
(^ 1 1)
1
(^ 2 3)
8
(^ 5 3)
125
现在，写出函数^
提示：记得第一戒和第五戒
(define ^
(lambda (n m)
(cond
((zero? m) 1)
(else (* n (^ n (sub1 m)))))))
(^ 5 3)
DrRacket环境测试结果为 (语言设置为初级)
125
这个函数的名字怎样才好
(define ???
(lambda (n m)
(cond
((< n m) 0)
(else (add1 (??? (- n m) m))))))
们从来没有见过这样的定义；自然递归看起来很奇怪
第一个查询是什么
看第一个参数是否小于第二个参数
第二行呢
我们递归函数，第一个参数变为原来两个参数的差。函数返回时加一。
那么函数做了什么
数出第一个参数能减掉多少个第二个参数。
这叫什么
除法
(define ÷
(lambda (n m)
(cond
((< n m) 0)
(else (add1 (÷ (- n m) m))))))
来一份(ham and cheese on rye)怎么样，别忘了芥末哦！
(length lat) 的值是什么，其中lat是(hotdogs with mustard sauerkraut and pickles)
6
(length lat) 的值是什么，其中lat是(ham and cheese on rye)
5
现在写一个函数length
(define length
(lambda (lat)
(cond
((null? lat) 0)
(else (add1 (length (cdr lat)))))))
(pick n lat) 是什么，其中n是4，lat是(lasagna spaghetti ravioli macaroni meatball)
(pick 0 lat) 是什么，其中lat是(a)
没有答案。
写出函数pick
(define pick
(lambda (n lat)
(cond
((zero? (sub1 n)) (car lat))
(else (pick (sub1 n) (cdr lat))))))
(pick 4 (quote (lasagna spaghetti ravioli macaroni meatball)) )
DrRacket环境测试结果为
语言: 大; memory limit: 64 MB.
macaroni
(rempick n lat) 是什么，其中n是3，lat是(hotdogs with hot mustard)
(hotdogs with mustard)
现在写一个函数rempick
(define rempick
(lambda (n lat)
(cond
((zero? (sub1 n)) (cdr lat))
(else (cons (car lat) (rempick (sub1 n) (cdr lat)))))))
'(hotdogs with hot mustard)
(rempick 3 '(hotdogs with hot mustard))
DrRacket环境测试结果为
语言: 大; memory limit: 64 MB.
(hotdogs with hot mustard)
(hotdogs with mustard)
(number? 76) 是真还是假
真
你能写出number?函数吗
不能。number? 如同add1, sub1, zero?, car, cdr, cons, null?, eq?, 以及atom?, 都是primitive函数
现在使用number?函数写一个no-nums，它删除一个lat中的所有出现的数。例如，lat是(5 pears 6 prunes 9 dates)，那么(no-nums lat)的值是(pears prunes dates)
(define no-nums
(lambda (lat)
(cond
((null? lat) (quote ()))
((number? (car lat)) (no-nums (cdr lat)))
(else (cons (car lat) (no-nums (cdr lat)))))))
'(5 pears 6 prunes 9 dates)
(no-nums '(5 pears 6 prunes 9 dates))
DrRacket环境测试结果为
欢迎使用 DrRacket, 版本 5.1.3 [3m].
语言: 大; memory limit: 64 MB.
(5 pears 6 prunes 9 dates)
(pears prunes dates)
现在写一个函数 all-nums，它从一个lat中抽取出所有的数构成一个tup。
(define all-nums
(lambda (lat)
(cond
((null? lat) (quote ()))
((number? (car lat)) (cons (car lat) (all-nums (cdr lat))))
(else (all-nums (cdr lat))))))
'(5 pears 6 prunes 9 dates)
(all-nums '(5 pears 6 prunes 9 dates))
DrRacket环境测试结果为
语言: 大; memory limit: 64 MB.
(5 pears 6 prunes 9 dates)
(5 6 9)
写一个函数eqan?，当两个参数a1和a2是一样的原子时为真。
(define eqan?
(lambda (a1 a2)
(cond
((and (number? a1) (number? a2)) (= a1 a2))
((or (number? a1) (number? a2)) #f)
(else (eq? a1 a2)))))
那么可以把所有用eq?的地方都可以替换为wqan?吗
可以当然了。
现在写一个函数occur描述一个lat中出现原子a的次数
(define occur
(lambda (a lat)
(cond
((null? lat) 0)
((eq? a (car lat)) (add1 (occur a (cdr lat))))
(else (occur a (cdr lat))))))
'(apple cake and chocolate cake)
(occur 'cake '(apple cake and chocolate cake))
DrRacket环境测试结果为
语言: 大; memory limit: 64 MB.
(apple cake and chocolate cake)
2
写一个函数one?仅当n为1时(one? n)为#t真，否则为#f假
(define one?
(lambda (n)
(cond
((zero? n) #f)
(else (zero? (sub1 n))))))
(one? 0)
(one? 1)
(one? 2)
DrRacket环境测试结果为
欢迎使用 DrRacket, 版本 5.1.3 [3m].
语言: 大; memory limit: 64 MB.
#f
#t
#f
或者
(define one?
(lambda (n)
(cond
(else (= 1 n)))))
(one? 0)
(one? 1)
(one? 2)
DrRacket环境测试结果为
欢迎使用 DrRacket, 版本 5.1.3 [3m].
语言: 大; memory limit: 64 MB.
#f
#t
#f
又或者直接
(define one?
(lambda (n)
(= 1 n)))
(one? 0)
(one? 1)
(one? 2)
现在重写rempick，它删去lat中的第n个atom原子。例如n为3，lat是(lemon meringue salty pie)那么(rempick n lat)的值是(lemon meringue pie)你可以使用你自己的one?函数。
(define one?
(lambda (n)
(= 1 n)))
(define rempick
(lambda (n lat)
(cond
((one? n) (cdr lat))
(else (cons (car lat) (rempick (sub1 n) (cdr lat)))))))
'(hotdogs with hot mustard)
(rempick 3 '(hotdogs with hot mustard))
DrRacket环境测试结果为
欢迎使用 DrRacket, 版本 5.1.3 [3m].
语言: 大; memory limit: 64 MB.
(hotdogs with hot mustard)
(hotdogs with mustard