是呆子?不是呆子

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

一年一度的程序设计竞赛日益临近,今年的竞赛非常火爆,报名人数超过了1万人。不过,参加评判的志愿者只有5人,所以不能让所有报名者全部参赛。因此,组织方决定,只让“真正的编程呆子”参加竞赛。

某人的呆子指数可以用如下两种数值的线性结合定义。

F=A×鞋子尺码+B×每分钟打字速度

其中,A和B都是系数,具体是什么值还不清楚。该指数越高,越接近呆子。根据F的值定义一个标准值T,如果报名者的呆子指数超过T,将允许参赛。

这种理论真的可行吗?是否存在合适的A,B和T,能利用F的公式区分呆子和不是呆子?为了确认,我们向我们已经了解是否是呆子的人收集了一些信息。最终资料由鞋子尺码、每分钟的打字速度,以及此人是否是呆子等信息组成。那么,适当定义A、B、T时,有没有方法判断此人是否是呆子呢?

人物

人物1

人物2

人物3

人物4

人物5

人物6

人物7

人物8

鞋子

尺码

2

2

3

3

4

4

4

5

打字

速度

3

5

3

4

1

4

5

5

是否是呆子

解决方案

方案一:变换成几何问题

把每人的鞋子尺码和每分钟的打字速度分别视为x、y坐标,就能把输入的数据表示成8个点,如下图所示:

 

是呆子?不是呆子2.png

 

从上图很容易可以看出,直线的一侧是呆子,另一侧不是呆子。因此,能够找出一条分割呆子和不是呆子的直线,即存在A、B、T使得公式能够判别参赛者是否是呆子。

运用的计算思维

我们通过建立图表的方式展现数据,同时也将问题转换成几何题,运用了“转化”的计算思维。

方案二: 凸包建模

从上述图表可知,问题已经变换成“在平面上给出两种类型的点时,判断有无直线能将这两类点相互分隔”的问题。如果对两种类型的点都存在一个凸包(包含所有点的面积最小的多边形),并且两个凸包没有连接或重叠在一起,那么必然存在一条直线能够分隔两个凸包,也即分割不同类型的点。

是呆子?不是呆子3.png

运用的计算思维

案二将问题转化成了凸包问题,运用了“转化”的计算思维。

参考文献

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