比赛问题(四)

本课程适合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(复旦大学数学系硕士)

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180712G1M29O00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券