螺钉螺母问题

来自计算思维百科
跳转至: 导航搜索
螺钉螺母问题1.jpg

螺钉螺母问题指的是,在一堆螺钉和一堆螺母中如何快速找出所有匹配的螺钉和螺母。

基本概念

假设我们有8个直径各不相同的螺钉,以及8个相应的螺母。我们一次只能比较一对螺钉和螺母,来判断螺母是大于螺钉、小于螺钉还是正好合适螺钉。然而,我们不能拿两个螺母作比较,也不能拿两个螺钉作比较。问如何找到每一对匹配的螺钉和螺母?

螺钉螺母问题2.png

解决方案

方案一:蛮力法

从螺钉堆中随意挑一个螺钉,将该螺钉与螺母堆中的螺母一一比较,直到找到匹配的螺母。然后继续下一个螺钉的匹配。直到所有螺钉和螺母都匹配成功。

运用的计算思维

蛮力法是思维最简单的方法,但同时也是最耗时的,体现一种机械化的思维方式。

方案二:分治法

第一步,我们从螺钉堆中任意挑选一个螺钉,将螺母堆中的每个螺母与该螺钉进行比较,大于该螺钉的放一堆,小于该螺钉的放另一堆,同时我们也能找到与该螺钉匹配的螺母。此时,我们已经将螺母分成了两堆。

螺钉螺母问题3.png

第二步,我们将螺钉堆中的每个螺钉与第一步中匹配好的螺母进行比较,大于该螺母的放一堆,小于螺母的方另一堆。此时,螺钉也被我们分成了两堆。

螺钉螺母问题4.png

第三步,通过第一步和第二步,螺钉和螺母都被我们分成了总体大小不同的两堆,且螺钉和螺母堆大小是对应的。接下来,我们对小一些的螺钉和螺母堆重复第一步和第二步,对大一些的螺钉和螺母堆重复第一步和第二步,直到将所有的螺钉螺母配对。

螺钉螺母问题5.png

螺钉螺母问题6.png

运用的计算思维

上述经验推理的过程能够帮我们排除大部分情况甚至可以直接找出答案,运用了计算思维的启发式特点。