机灵的小老鼠

来自计算思维百科
跳转至: 导航搜索
机灵的小老鼠.jpg

大花猫是捕鼠能手,每天要抓到不少老鼠。但它在吃老鼠以前,先要叫老鼠列队报数。第一批吃掉报单数的;剩下的老鼠重新报数。第二批,花猫吃掉报单数的;第三批也是如此⋯⋯最后剩下的一只老鼠可以被保留,与第二天抓来的老鼠一起重新排队报数。后来,发生了一件极其有趣的事情。大花猫发现,一连好几天,最后被留下的总是一只机灵的小白鼠。大花猫就问小白鼠:“你想了什么办法,能每天都留下呢?”

小白鼠说:“尊敬的大花猫先生,每天排队前我都先数一数你抓到了多少只老鼠,然后,我站在一个相应的位置,就可以留下来了。”大花猫听了小白鼠的详细回答,很感叹地说:“没想到,害人的老鼠里居然也有你这样聪明的小白鼠呀!”小白鼠行了一个礼,恭敬地说:“尊敬的大花猫先生,不瞒您说,我并不是害人的老鼠,我是从科学家的实验室里溜出来玩的,您放我回去,好吗?”大花猫高兴地放它回去,临别的时候,大花猫还感谢小白鼠给它上了一节生动的数学课呢!

你知道吗,小白鼠每天应站在什么位置才能不被花猫吃掉。

(为了方便,我们假设第一天共有十只老鼠排队,第二天是二十只)

解决方案

方案一:蛮力法

大花猫第一批吃掉序数是单数的老鼠,留下序数是双数,也就是序数能被2 整除的老鼠(如2、8、14、等)。第一批吃完后,2、6、10⋯⋯这些序数变成1、3、5、⋯⋯,这样的老鼠在第二批就要被吃掉。而4、8、12⋯⋯变成2、4、6⋯⋯这样的序数还能被2 整除,第二批就不会被吃掉。我们可以列出每一次的具体情况,可以找出不被吃的位置。我们可以看到如果序数中有尽可能多的因数2,老鼠就安全了。聪明的小白鼠就专拣这样的位置站。比如10 只老鼠排队,站第8 个(2×2×2)20 只老鼠排队,站第16 个(2×2×2×2),可规律如下


鼠数

1

2→3

4→7

8→15

16→31

2n-1→2n -1

留下者的位置

1

2

4

8

16

 

2n-1

运用的计算思维

遇到一个问题,我们最容易想到的就是最直接的解法,正如计算思维中的机械式思维一样,先考虑最简单的情况怎么做,一步步地分析,一定能够得到答案,但在这个过程中,就不能够保证找到答案的时间和空间成本了。

方案二:

事实上,如果我们能把某一只老鼠的序数化成二进制数,就立刻可以知道它将在第几批被吃掉了。如第12 只老鼠。将12 化成二进数是1100,右面第一、二位是“0”所以它在第一批,第二批都留下。而右面第三位出了“1”,它肯定在第三批被吃掉。只有那些序数化成二进制数只有一个“1”和若干个“0”的老鼠,才有可能最后留下。如第4 只老鼠,序数化成二进制数是100;第8 只是1000;第16 只是10000,都符合这些条件,有可能留下。至于留下这几只中哪一只,要看排队的老鼠多少而定。

运用的计算思维

很多时候,许多问题可以通过分析抽象转化成一些更直观简单的问题处理,正如上面案例中利用二进制数简化了问题,这也是计算思维中抽象转化思维的体现。

参考文献

[1] 《数学趣味游戏》 网上资源