进位制与数学游戏

现有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整除的二进制数。

2011新年好

好多人都在盘点2010,那我也跟风盘一下。

2010年,我做了这些事:

– 写了20篇博客

博客空间总访问量16842 PageView(Google Analytics数据),比去年上涨23%。首页、折腾My BookSSH隧道折腾O2 Joggler加速Linux编译这几个页面的PV占总PV的50%。博客的RSS订阅数刚刚超过了100(以Google Webmaster Tool数据)。

开通了Google AdSense,两个多月以来收入是$0.01,也就是只有一次点击——我自己点的。

– 完成2010年的计划

开车学完了,4月份开始,9月份结束,所有项目一次顺利通过。2010的财务收入支出相当清晰,不翼而飞的开销占总开销的0.2%。时间管理,不敢说自己做得很好,但有很多时候感觉比以前更充实,开始使用Remember The Milk来避免忘事。

– 参与了4个自由软件项目

1. 电子书开源固件OpenInkpot的中文化,提交了一个Patch。但这个项目在6月份以后几乎处于休眠状态,前景不明。

2. 电子书管理软件calibre的开发,完成了豆瓣元信息插件、豆瓣封面下载插件、盛大Bambook设备接口、Bambook SNB文件格式支持等功能。同时参与它的中文化工作。

3. GNU中文翻译小组。在加入这个沉寂的小组6年后,终于提交并发布了包括GNU首页在内若干页面的翻译。但由于这个项目活跃度仍然很低,还有不少页面翻译由于没有得到审核而没有发布。

4. 继续开发PockeTwit。由于饭否刚刚回归,PockeTwit的只针对饭否回归发布了一个新版本,还没有更多的新功能加进去。也还没有能把饭否的支持并回PockeTwit的主干。

– 我自己的自由软件项目

1. LGuo的电子运行图。发布了一个新版本2.60,主要改进了多平台和多语言的支持。

2. 豆饭。饭否回归后发布了一个新版本,没有新的功能增加。曾经把它分支成“豆推”用于支持Twitter,现在已经并回主线,成为一个隐藏功能。

3. Windows Mobile上的火车时刻表和余票查询。这个软件数据来源是12306.cn的实时数据,所以会比离线时刻表更有价值,但在POC完成后一直放在那里没动了。当时停滞的原因是我画不出一个自己满意的界面……后来没有动力再做的原因是我觉得做客户端软件不如做个可以良好支持手机浏览器的Web版更有价值。

– 几个重要的IT产品

1. 汉王N510电子书。没花钱,因为它关注了OpenInkpot和calibre。

2. LEGO Mindstorm NXT 2.0。去美国的时候犹豫再三还是决定买下了。不过迄今为止还没有用它原创出一个我自己满意的作品,倒是为leJOS贡献了一点文档中文化。

3. 盛大Bambook电子书。我承认我这个买得头脑发热,不过还是因为它更多的参与了calibre项目。我写的calibre的Bambook插件正在参加盛大的Bambook程序达人赛,从目前来看,有望把投资回本,欢迎大家去为它投票。

4. O2 Joggler。去年的My Book因为硬件升级阵亡,所以入了O2 Joggler。于是博客的很大一部分流量也从My Book的那篇文章转移到了O2 Joggler的文章。

5. Linode VPS。秒杀到了免费赠送$100的Linode VPS,打算长期使用。

– 旅游

美国5日游(Blog文章(1)(2)(3)(4)(5)),新疆8日游送别京沪线最后一趟绿皮1462次+滁州琅琊山4小时游,创103万人次记录的上海世博一日游

2011年,希望能做这些事:

2011年应该会是忙碌的一年,要做的事很多,为了不在这里给自己太多的压力,就写个“没有鸭梨”的吧:2009年底中国发射了第一颗业余通信卫星希望一号(HO-68),2010年一直想着要试验一次卫星通联却没有实现,就把这个愿望放到2011年吧。小卫星的寿命非常有限,希望能抓住这次机会。CQ satellite, this is BG4XTR, calling CQ and standing by.

几分钟前好友给我带来了新年的第一个好消息:2012年维也纳新年音乐会将由曾经执棒2006年维也纳新年音乐会的马里斯·杨松斯(Mariss Jansons)指挥,2006年的音乐会给我留下了深刻的印象,所以一直很期待他可以再次登台。期待10多个小时后即将开始的2011年维也纳新年音乐会,也期待365天后的2012年维也纳新年音乐会。新年音乐会总是在新年的第一天为我带来新一年全新的气息。