进位制与数学游戏

现有1000个苹果,10个盒子,问各个盒子内应该分别放入多少个苹果,才能使得用户要买任意1至1000之间的一个苹果数,都可以给他(卖的时候是整个盒子卖,不能拆盒子的包装)。

曾经在我的那些数学玩具们——二进制篇中提到过这个问题,看过那篇文章后,答案应该是不言而喻的,1, 2, 4, 8, 16, 32……

如果把题目换成:现有一架天平,若干个砝码,每个砝码应该分别多重才能称出1至1000克整数克的物品?

答案如果是不假思索的1, 2, 4, 8, 16, 32……自然是可以的,那我也不用废话写这篇文章了。实际上1000个苹果需要装在10个箱子里,用天平称1至1000克的物品却不需要10个砝码,只用7个就够了。

差别在于:装苹果的盒子只以能是选择拿或者不拿,而天平则可以不放砝码,或者把砝码放在左边,或者放在右边。所以,我只用两个砝码:1克和3克,就可以称出1至4克的任意整数克。

因此,解装苹果的问题需要用到二进制,解天平砝码的问题则需要用到三进制。二进制有0或1,真或假,开或关的两种状态。三进制则就有三种状态,0、1、2或-1、0、1(平衡三进制)。

在生活中,也有不少东西具有三种状态。对于天平称东西的问题(尤其是那些在XX个小球中找出X个不同的智力题)或者一些带有约束条件的过河问题,都可以用三进制来建模和解决。

进位制是一个很有意思的话题,以学习十进制和二进制的思维方式,我们就很容易的类推出各种进制的表现型式和性质,甚至于还可以捣鼓出“负2进制”之类的东东。感兴趣的TX可以考虑拜读Donald E. Knuth的神书TAOCP的第二卷。

好吧,其实这篇文章算是看了《进位制与数学游戏》一书的一小点收获了,在这本书中,作者不厌其烦的为一个相同的数学模型创造出了无数的问题和实例,所以在看完整本书后,能发现的收获也就只有那么一小点。

最后联想到了一个以前学编译原理时老师讲过的题,当时在课堂上我还真是没能自己做出来:

构造一个DFA,用于识别字母表∑={0,1}上可以被3整除的二进制数。

进位制与数学游戏》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据