是呆子?不是呆子?2

来自计算思维百科
跳转至: 导航搜索
是呆子?不是呆子21.jpg

去年编程年度模拟考试后,参加程序设计竞赛的热潮愈演愈烈,今年估计会有超过10万人报名参赛。竞赛组依旧只让真正的编程呆子参加比赛。不过今年组委会提出了新理论,参赛者是否是呆子将取决于如下两种数值:

(1)在程序设计在线评分系统中解过的习题数P

(2)目前为止熬夜时吃过的方便面数q

参赛者按顺序报名,如果已经报名的参赛者中习题数和吃过的方便面数都比当前正在报名的参赛者少,那么会淘汰相对少的参赛者。因此,能够参赛的人员名单会根据新报名者的出现而发生变化。以下四人按顺序申请参赛,请计算报名过程中参赛人员数量的变化。

参赛者

宗万

宰勋

孝成

光圭

习题数

72

57

74

64

方便面数

50

67

55

60

解决方案

方案一:直接比较法

宗万第一个报名,习题数72,方便面数50;参赛人员数量:1

宰勋第二个报名,习题数57<72,方便面数67>50,因此宰勋参赛;参赛人员数量:2

孝成第三个报名,习题数和方便面数都大于宗万,因此宗万淘汰,孝成参赛;参赛人员数量:2

光圭第四个报名,习题数和方便面数没有比其他人都多,也没有比其他人都少,所以光圭参赛;参赛人员数量:3

运用的计算思维

我们根据参赛顺序,通过直接比较法能够得出人员变化过程,是正常的解决思路,体现了机械化的思维方式。

方案二: 几何法

我们按顺序把每个报名者的习题数和方便面碗数分别视为横坐标和纵坐标,并在二维平面上用点的形式表示出来。

首先是宗万报名

是呆子?不是呆子22.png

上图中灰色的区域的习题数和方便面碗数都不会超过宗万,所以该区域是宗万阻碍其他人参赛的区域,也就是如果之后有报名者在灰色区域中,那么该报名者一定会被宗万打败。

接下来是宰勋报名

是呆子?不是呆子23.png

从图中可以看出,宰勋不在宗万的控制区内,所以宰勋参赛,参赛人员为2。

接下来是孝成报名:

是呆子?不是呆子24.png

我们发现宗万落在了孝成控制的区域,那么宗万将被淘汰,孝成参赛,人员数量为2。

接下来是光圭参赛:

是呆子?不是呆子25.png

从上图可知,光圭没有落在之前参赛人员的控制区域中,并且也没有其他人员落在光圭的控制区域中,因此光圭参赛,人员数量为3.

运用的计算思维

方案二将问题转化成了“每次加入新点时,计算共有多少个不被其他点控制的点”,可以用互相覆盖的区域明确表明谁会被淘汰,使问题求解变得很清晰,运用了“转化”的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015