图书馆验书问题

来自计算思维百科
跳转至: 导航搜索
图书馆验书.png

小红抱着一堆书走出图书馆,这时,图书馆门口的报警器响起了,小红不清楚是哪一本书把报警器弄响了,请你帮她找出来。

涉及的计算思维

该问题可以利用两种方法来解决,第一是穷举法,是一种利用计算思维的机械化思想。第二种是二分查找法,把大问题分成小问题来求解,体现了计算思维的分治思想。

解决方案

方案一——穷举法

该方法的思想就是把所有可能的解一一列举出来,然后一一带入检验是否能得出结果。因此,我们可以把小红手上的书一一经过检验器检验,检验到哪一本发出报警声就可以找到。不过该方法耗时较长、耗力较多。

方案二——二分查找法

二分查找法的思想就是将问题的实例划分为同一个问题的两个实例,找出问题所在区域然后进行再折半分解。因此,我们可以把小红手上的书分成两半,分别经过检验器检验,找出警报响起的一半再进行对半分解,再检验,再分解,直至找到为止。利用该方法可以减短求解时间,提高效率。