本课程适合10岁以上小朋友
回顾
在
比赛问题 (三)
中,我们讨论了
1. 递归的求值顺序
2. 递归的剪枝
3. 关系表
本章简介
1. 迭代
2. 抽象
3. 高阶函数
4. 匿名函数
过程式解法
小朋友还记得上一章比赛问题 (三)最后的这张图吗?
这张图的每一个节点代表从一个特定比分开始,甲最终取胜的概率。我们注意到,每一个节点上的值,可以由其左方节点的值和下方节点的值求出。比如,如果想求出节点10的值P(1:2),只需求出节点6的值P(2:2)和节点9P(1:3)的值。
图中黑色结点的值都是已知的,形如4:x的值为1, 形如x:4的值为。
如果我们想求出图中所有节点的值,首先要求出节点1的值, 最后求出节点16的值。至于求解的顺序则多种多样。
如:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 5 9 13 2 5 10 14 3 7 11 15 4 8 12 16
1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16
。。。。。。
我们先从一个特例展开讨论:
1. 单球胜率为1/2;
2. 采用4分制。
为了看得更清楚些,我们把上图顺时针旋转90度, 并简化为下图
我们选定一个计算顺序如下:
根据上述计算顺序,
很容易写出下面的C代码(为了便于理解,这里给出的是尽量简化的代码):
double a[5][5] = { };
int i,j;
for (i = 1; i
for (j = 1; j
a[i][j] = (a[i-1][j] + a[i][j-1] )/2.0;
}
}
for (i = 1; i
for (j = 1; j
printf("%8.6f\t", a[i][j]);
}
printf("\n");
}
0.500000 0.750000 0.875000 0.937500
0.250000 0.500000 0.687500 0.812500
0.125000 0.312500 0.500000 0.656250
0.062500 0.187500 0.343750 0.500000
喜欢Python的同学,可以写出更简洁的代码:
a = [ [1] * 5 ] + [[0] *5 for i in range(4)]
for i in range(1,5) :
for j in range(1,5) :
a[i][j] = (a[i-1][j] + a[i][j-1]) / 2
for i in range(1,5):
print(a[i][1:])
[0.5, 0.75, 0.875, 0.9375]
[0.25, 0.5, 0.6875, 0.8125]
[0.125, 0.3125, 0.5, 0.65625]
[0.0625, 0.1875, 0.34375, 0.5]
以上代码均可以正确地求解,但有三个我们需要注意到的问题
程序中使用了可变量,也就是说,随着时间的推进,不断改变自身值的量,如循环控制变量i, C语言中的数组a。在现代编程中,对可变量的使用一定要谨慎,本章中我们的程序依然只使用不可变量;
是的,C语言中,数组a是可变的,数组名a是一个常量。
这段代码的出发点是机器,而不是问题本身,我们的教学强调面向问题分析。今天讨论的这个问题,一眼就可以看出面向机器的解法,而面对更复杂的问题,如接下来我们马上要讲述的“24点问题”,如果不面向问题做充分的分析,很难推导出正确的程序;
我们知道,编程的核心是抽象,对公共模式的提取。我们分析问题的时候,能不能找出一些公共模式,推导出更有趣的写法呢?
处理一行
我们的教学是从函数式编程入手,此处我们再强调一下,函数式编程中的函数与C、Python这类语言中的“函数”不同(此处,我们仅就C、Python的典型风格而言),而是更接近于数学中的函数。也就是说,我们所说的函数,大多是纯函数,同样的输入一定产生同样的输出。由此,我们目前所说的程序是一系列函数变换,而不是指令序列。
回到本章的问题,我们把每一行的计算看成一个函数变换。
以第一行计算为例,它接收两个参数,(1 1 1 1 ),返回(1/2 3/4 7/8 15/16)
我们把这个函数记为scan-line,则有
(scan-line 0 '(1 1 1 1) ) ==> '(1/2 3/4 7/8 15/16)
简单分析一下,函数返回的结果的第一个元素1/2可以直接求得, 它是列表的第一个元素1与参数的平均值,结果列表的尾部(列表的尾部是指去掉其第一个元素后的剩余部分), 即( 3/4 7/8 15/16),正是(scan-line 1/2 '(1 1 1))的结果。
如果觉得这段话难以理解,可以观察下图。( 3/4 7/8 15/16)的计算,可以看作scan-line接收两个参数,(1 1 1)所进行的更小规模的计算。
我们引入符号来描述这个过程,函数形如
(scan-line v lst)
结果是一个列表
1. 其头部(列表的第一个元素)为lst的头部 和v的平均值,我们把这个平均值记为t
2. 其尾部为(scan-line t (cdr lst ))
由此,我们不难推导出程序如下:
(define (avg a b )
(/ (+ a b ) 2 ))
(define (scan-line v lst)
(if (null? lst)
'()
(let ([t (avg (car lst ) v)])
(cons t (scan-line t (cdr lst))))))
(scan-line 0 '(1 1 1 1))
'(1/2 3/4 7/8 15/16)
以上分析对于没有受过递归编程训练的小朋友来说,会有些困难。我们近期会写一篇关于递归编程的文章,如果您还没有关注我们的公众号,可以用微信扫本文结尾处的二维码。
整个过程
整体的计算solve,可以用下面的图来描述。
solve
我们把scan-line的图解重新列出来,方便大家对比。
scan-line
二者的不同之处在于
1.scan-line返回的列表的每一个元素都是数字
如(1/2 3/4 7/8 15/16)
solve返回的列表的每一个元素都是列表
( (1/2 3/4 7/8 15/16)
(1/4 1/2 11/16 13/16)
(1/8 5/16 1/2 21/32)
(1/16 3/16 11/32 1/2))
2.scan-line计算单个元素,使用平均数函数avg
solve计算一个元素(这个元素也是一个列表),使用的是上一节的scan-line函数
由以上分析可以推导出程序如下:
(define (solve v lst)
(if (null? lst)
'()
(let ([t (scan-line (car lst ) v)])
(cons t (solve t (cdr lst))))))
(solve '(1 1 1 1) '(0 0 0 0))
((1/2 3/4 7/8 15/16)
(1/4 1/2 11/16 13/16)
(1/8 5/16 1/2 21/32)
(1/16 3/16 11/32 1/2))
和上一节的程序是不是很像?
高阶函数
我们把前两节的程序放在一起对比一下
;scan-line
(define (scan-line v lst)
(if (null? lst)
'()
(let ([t (avg(car lst ) v)])
(cons t (scan-line t (cdr lst))))))
;solve
(define (solve v lst)
(if (null? lst)
'()
(let ([t (scan-line(car lst ) v)])
(cons t (solve t (cdr lst))))))
我们对比这两段代码,发现他们竟如此相似,仅有一处调用了不同的函数,一个是avg, 一个是scan-line。
我们通过引入高阶函数(函数作为参数),提取出两段代码的公共部分,写出函数如下:
(define (scan f v lst)
(if (null? lst)
'()
(let ([t (f (car lst ) v)])
(cons t (scan f t (cdr lst))))))
代入平均值函数avg, 下面的计算相当于之前的scan-line。
(scan avg 0 '(1 1 1 1 ))
'(1/2 3/4 7/8 15/16)
代入scan-line, 下面的计算相当于之前的solve。
(scan scan-line '(1 1 1 1) '(0 0 0 0 ))
'((1/2 3/4 7/8 15/16)
(1/4 1/2 11/16 13/16)
(1/8 5/16 1/2 21/32)
(1/16 3/16 11/32 1/2))
后一段代码还需要使用前面的scan-line函数,小朋友可能会想,我们能不能用(scan avg)来替代scan-line呢?
答案是否定的,系统会告诉你 arity mismatch,参数数目不匹配。
推荐两个解决方法:
一是使用匿名函数
(scan (lambda (v lst) (scan avg v lst )) '(1 1 1 1) '(0 0 0 0 ))
二是使用curry函数
(scan(curry scan avg)'(1 1 1 1) '(0 0 0 0 ))
进一步的简化
如果小朋友能熟练运用 lambda,那么程序更可以精简为:
(scan (lambda (v lst)
(scan (lambda (a b ) (/ (+ a b ) 2 )) v lst ))
'(1 1 1 1) '(0 0 0 0))
另一种方法
我们在讲高阶函数的时候提到过,高阶函数之所以称为高阶函数,一是函数作为参数,二是函数作为返回值。
这里提供另一种方法,不仅在参数中接受一个函数,而且返回的也是一个匿名递归函数。
(require mzlib/etc)
(define (avg a b ) (/ (+ a b ) 2 ))
(define (p f )
(rec (r-f v lst )
(if (null? lst)
'()
(let ([nv (f (car lst) v )])
(cons nv (r-f nv (cdr lst )))))))
在这个函数的基础上,计算可以表达为更精简的形式:
((p (p avg )) '(1 1 1 1) '(0 0 0 0))
思考
1. 构造一个函数add,可以求解三个数的和。
什么?太简单了?
我们要求的调用形式是
(((add 3) 4 ) 5 )
2. 本文只讨论了一个特例,小朋友可以扩展一下程序,处理更一般的比赛问题。
展望
下一章,我们将用计算机来模拟比赛,学习蒙特卡洛方法。
我们汇聚名校博士师资团队,坚持做严肃编程,区别于游戏式编程兴趣班,致力于帮助少年儿童获得更高级的数学思维和编程能力,坚持做有料的线上内容和有含金量的线下课程,成为一股独树一帜的编程和数学教育力量。
少年编程暑假训练营开始报名了!
欢迎全国各地小学三年级以上小朋友来西安学习
30天集训,每天四小时,120课时,小班教学(3到5人),
编程和数学理论与上机实践相结合
面向10岁以上少年儿童
课程基于麻省理工学院经典计算机教材SICP
自主研发Scheme课件
在提高数学思维能力的基础上
打下坚实的编程基础
教师:Dr. Yin (复旦大学与中科院两站博士后)
Colin Cai(复旦大学数学系硕士)
领取专属 10元无门槛券
私享最新 技术干货