假币问题

来自计算思维百科
跳转至: 导航搜索
假币问题1.png

在n枚外观相同的硬币中找出唯一的一枚假币。这是一个经典的数学谜题,曾在Beasley(1990) 及赵文敏(1995)所著的趣味数学书中介绍过,其本质与Bundy(1996)所讨论的Odd Ball Problem属同类问题,但三人的解法不一样。在识别假币问题的多种版本中,我们考虑最能够体现出减常因子策略的那个版本——单假币问题。

假币问题描述:在n枚外观相同的硬币中有一枚是假币。如何找出那枚假币?已知假币比真币轻。提供一个天平。

解决方案

在一架天平上,我们可以比较任意两组硬币。通过观察天平的倾向我们可以挑出假币所在的那一组。把n枚硬币分成两堆,每堆有假币问题2.png枚硬币,如果n为奇数的话,留下额外的一枚硬币,然后称量两堆硬币。如果两堆硬币重量相同,那么放在旁边的硬币就是假币;否则就用相同的方法对较轻的一堆进行处理。一直到只剩两枚硬币时就很容易找出较轻的那一枚就为假币。

这里的假币问题是基于二分算法解决的,即是两两分堆的。

应用范围

假币问题主要解决的是如何高效地找出大量相似事物中的具有特殊性质的那一个。因此可以将它应用在很多方面,例如可用于工业生产中对次品的筛选,人才选拔考试等。

使用方法及步骤

1.确定适用范围:所要解决问题是否符合“从大量相似物中找出具有特殊性质的那一个”这一条性质,正如问题描述的“n枚外观相同的硬币中有一枚是假币”。注意,假币在这里只有质量与真币不同,其他性质都一样。同样,解决的问题中要控制目标性质的唯一性,类似于控制变量。

2.将n个实例(n枚硬币)分为2份,若有剩余的,利用检验设备(天平)通过检测分好两份的异同来确定剩余实例的弃留;

3.选择具有特殊性质的那一份再分为2份来检验(硬币中轻的那一堆);

4.重复3直到只剩一个实例,即为目标所求(假币)。

应用案例

应用1-找出“滥竽充数”中的那个人

案例:一个公司的某部门主要负责业务销售,每个员工都有目标业务量,业务主管发现他们的销售业绩有明显的下降,他怀疑有人开始混日子,他想找出混日子的那个人。

解决步骤:

1.确定下降的业绩是否只有一个人有关 ;

2.将部分分为两个组,观察两组的业绩。若有剩余一人,若两组业绩一样,则剩下的那人就是混日子的人。

3.若无剩余,挑出业绩低的哪一组再分两组,去查看其业绩。

4.重复3直到分到剩余一人时即为混日子的人。

可以体现的计算思维

从上面的案例我们容易看出,在实际的管理中,如果我们要找出大量相似体中的特殊体,可以通过一个个去找,但这样的话效率比较低。在这个案例中,通过不断两两分组每次都只需处理相对于原来的一半的规模的问题,这样就大大提高了效率,这也正是减治法的思想体现。而在这里的案例中,我们每次减去的都是一个相同的常数因子即为2,即为规模的一半,这体现了计算思维的约简特点。