首页 > Linux运维技术面试 > 算法:进制的力量(1)

算法:进制的力量(1)

2014年10月28日

算法:进制的力量(1)

http://blog.163.com/[email protected]/blog/static/600557512011102062426697/

有一个小国家,以生产高级葡萄酒闻名,全国的经济命脉也全依仗葡萄酒出口贸易。

某一年,另一大国向这小国下了1024瓶最高级红酒的订单,并预付了丰厚的定金。假如交易成功并获得好评,类似生意将滚滚而来,会为全国人民带来很多年富 足 的生活。于是全国人民同心协力,终于耗尽那一季的所有资源制成了1026瓶质量超高的名贵红酒,其中两瓶送交国家博物馆留为纪念,余下1024瓶准备付 运。

但是,有一个对这国家极度憎恨的恐怖分子为了破坏这宗交易,不惜偷偷混入生产运输团队中,并在1024瓶酒中的其中两瓶酒内下了强力的生化毒药。此毒药药 性强烈,只需极少份量(约0.01毫升)便可置人于死,但如混酒饮下则中毒者24小时内并无异样,但24小 时过后的15分钟内会立即七孔流血暴毙。

在1024瓶酒要运上飞机的26小时前,恐怖分子的身份和计划都曝光了,但是因为他及时自杀了,官员们只确定了他在其中两瓶酒里下了生化毒药及其药性,但完全不知道是哪两瓶。

这时全国陷入一片恐慌,假若不把1024瓶酒及时运送到目的地,哪怕是少了一瓶,都作违约论,国家要赔偿巨额的违约金,财政上会出现严重赤字,未来好几年 的人民生计将会非常艰辛。但是假若把有剧毒的酒售卖出口并造成人命伤亡,将会对全国赖以为生的葡萄酒出产业造成无可挽救的声誉伤害,以后也休想做其他国家 的 生意了。

就在这危急关头,监狱里有65名快将行刑的死囚站了出来,为了他们的亲人和朋友,决定自告奋勇,以身试毒,望能挽回这一笔对全国人民至关重要的生意。国家为了犒赏他们,不论试毒结果生死都会给与其家人一笔优厚奖金。

时间还有25小时多一点,官员们已经聚集了全国很多熟手包装工人,花了大半小时把1024瓶红酒拆装,从每瓶酒内提取了数毫升份量作试毒用途,然后又把它们全部重新包装。

现在距离最后时限还有24小时30分钟,65名自愿试毒的死囚和1024杯可能有毒的酒(每杯上都有标贴对照其相应的酒瓶号码)已经准备好了,现在只欠一个完善有系统的试毒程序来解决这难题……

 

问题的求解的关键在于对二进制的了解:

我们所生活的世界是个十进制的世界,当你从超市出来,给服务员结帐时; 按下手机按键,给家人或是朋友打电话时,实际上你已经在不知不觉中用到了十进制的思想。十进制用0,1,2,3,4,5,6,7,8,9十个阿拉伯字母来 表达所有的数的概念,至于为什么采用十进制,一个简单有力的答案是人有十个手指。比如中美洲的玛雅人,他们所采用的则是二十进制,至于为什么是二十进制, 一个答案是玛雅人基本上是光脚的,算上了脚趾,正好是二十个。当然对于进制也有很有趣的历史,不过和题目无关,就此打住。

而于此同时,我们生活的又是一个二进制的世界,你所用的电脑,手机,一切你所能接触到的电子产品,最底层的最数据的表示,基本运算都是二进制的。而此题,是对二进制表示一道精彩的题目。

我们先考虑一种简单的情况:1024里只有一瓶毒药的情况,我们该怎么做。我们先对所有酒进制标号(0,1,2…1023),如果有人问为什么要从0开始,而不是1开始,如果阁下的专业是数学或计算机或相关的话,先去图书馆好好看下书。

从人的角度出发,不考虑其他情况,每个喝下酒的情况只有两种,生存或是死亡,这意味我们可以用二进制来表达他们喝完的状态,0:表示喝完挂了,1:表示喝完没挂。

从酒本身的角度出发,1024=2^10;也就是说,我们只需要用十个位,就能表达出1024种状态。

把酒的状态定为问题空间,人的状态定为解空间,我们可以把题目看成是从问题空间到解空间的一个映射关系.而这个关系用二进制很容易完成一一映射。

(1)从50人中随便找10个,标号为(0,1,2,3,4,5,6,7,8,9);

(2)将已经标好的酒用二进制表示(0)=>(0000000000),(1)=>(0000000001)….,(1023)=>(1111111111)。

(3)对每瓶酒,采取如下策略:若相对应的位的数据为1,则对应的人喝,如(1010101010),则第(0,2,4,6,8)这五个人都喝有该酒。

用该策略后,24时后,对于序列(0,1,2,3,4,5,6,7,8,9)若有人死了,则将其相应的位置为(1),反之,置为0,则其表示的二进制序列则为第几瓶酒有毒。(为什么)。

这是只有一瓶酒有毒的情况,现在我们考虑两瓶有毒的情况。

******************************************************************************************

两瓶酒有毒的情况要复杂一多,如果我们还是用原来的方法考虑,则最后得到的状态则是两瓶酒的并集。比如现在有酒(0101010101)和(1010101010),则我们最后的情况是十个全都挂了,而可以十个人都挂的情况的组合可以有很多种组合。

当然如果我们能把两瓶酒各自的映射分开来,用我们前面的讨论过的方法,问题自然迎刃而解。但我们如何将两瓶毒酒的映射分开来?

 

还是按原来二进制的方法表示:

将65个人分三组

I,10人 :A2,B2,C2,D2,E2,F2,G2,H2,I2,J2;

II,10人: A1,B1,C1,D1,E1,F1,G1,H1,I1,J1;

III,45人: AB,AC,AD,AE,AF,AG,AH,AI,AJ,BC,BD,BE,BF………HI,HJ,IJ;

 

采取如下策略:

对于每一瓶酒,化成二进制(如:0101010101),对于I组位为1(B2,D2,F2,H2,J2)的人喝,对于II组位为0(A1,C1,E1,G1,I1)的人喝.

对 于第(III)组的人,若相应的两个位互不相等,则喝之 (0(A),1(B),0(C),1(D),0(E),1(F),0(G),1(H),0(I),1(J)),以有A的为 例,0(A):1(B),1(D),1(F),1(H),1(J),则该组中的(AB,AD,AF,AH,AJ)喝之。

这样,二十四小时后,我们可以唯一界定哪两瓶酒有毒了。(为什么)

本文的评论功能被关闭了.