二分法提问

来源:吉言网 编辑:问筠 2018-12-20 16:57:59

假如有本书,旁人随意指定书中的任意一个字(符号也算是一个字),你能用多少次猜中那个指定的字呢?对方针对你的回答,只能答复是或不是。

当然,如果按照书页,将字逐个猜“是这个字吗?”,也不是不可以,只是多了分乏味,少了分趣味。万一那本书是厚厚的一本,指定的字刚好又是在尾段,那岂不是一项巨大的工程?如果没有足够的耐心和十足的信心,面对如此机械的工作恐怕早就半途而废了。

如果这本书有200页,每页上的字不超过1000个,最坏的打算真的要猜199999次吗?相信换了谁都不愿意。

我们先来看看简单的情况。如果只有两个字设为1和2,问“是1吗?”,回答“是”,那么就是1。回答“不是”,那么就只能是2。如果有四个字1、 2、 3、 4,如果我逐个询问“是吗?”,而这个要猜的数恰好是4,就需要问3次。但同样的情况若是问“是1或2吗?”,否的回答让我们直接将目标锁定在了3和4上,还只需一问就可以完全确定了。也就是说一问的话可以确定两个字的情况,两问可以确定四个字的情况,三问验算下来也可以确定8个字中的一个,这样一来,如果用这种方法问n次,那就可以猜中2n个字中哪一个是(可以用数学归纳法证明)。每次将情况一分为二来进行考虑,我们通常称为二分法。而该种方法在计算机的运作中也起着相当大的作用。

因为217=131072<200000<262144=218,所以这本不足二十万字的书,其实只需要18次的提问就可以将字确定下来。想起来有点不可思议,但是真的不可忽略这个小小的2能有如此大的功效。

你也可以尝试一下,如果要将这本《趣味数学》中的某个字猜出来,需要多少次提问呢?

精彩阅读