比赛问题（四）

本课程适合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. 采用４分制。

为了看得更清楚些，我们把上图顺时针旋转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

二者的不同之处在于

１.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))

思考

１. 构造一个函数add，可以求解三个数的和。

什么？太简单了？

我们要求的调用形式是

(((add 3) 4 ) 5 )

2. 本文只讨论了一个特例，小朋友可以扩展一下程序，处理更一般的比赛问题。

展望

下一章，我们将用计算机来模拟比赛，学习蒙特卡洛方法。

我们汇聚名校博士师资团队，坚持做严肃编程，区别于游戏式编程兴趣班，致力于帮助少年儿童获得更高级的数学思维和编程能力，坚持做有料的线上内容和有含金量的线下课程，成为一股独树一帜的编程和数学教育力量。

少年编程暑假训练营开始报名了！

欢迎全国各地小学三年级以上小朋友来西安学习

30天集训，每天四小时，120课时，小班教学（3到5人），

编程和数学理论与上机实践相结合

面向10岁以上少年儿童

课程基于麻省理工学院经典计算机教材SICP

自主研发Scheme课件

在提高数学思维能力的基础上

打下坚实的编程基础

教师：Dr. Yin (复旦大学与中科院两站博士后)

Colin Cai(复旦大学数学系硕士)