两个经典面试题--1248码,漂亮的二进制思想

   1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，每天结束的时候,工人会向你要一段金条。如果只允许你两次把金条弄断，你如何给你的工人付费？

   2.有1000个苹果，将它们放在100个箱子里，怎么放才能让我向你要苹果的时候，你都能整箱整箱的给我,你的给法是否唯一?

 

这两个题目我想很多人都曾做过，如果你会做第一个题目，那你也应该会做第二个...如果不会,请看文章标题的提示...

 

 

 

 

 

 

    下面就个人理解给出这种二进制的思想:

    我第一次看到的是第二个题目，一开始，没什么思路，只是一步步的试，比如说，如果要一个苹果，我就必须要有一个箱子里放1个苹果，这是没法改的，如果要两个苹果，我要么是给一个放有2个苹果的箱子，要么是给两个各放有1个苹果的箱子，显然后面那种不行，因为当向我们要三个苹果的时候，我们至少要用掉三个箱子...后来突然想到高中涂高考志愿卡时,遇到的一个有趣的1248码,卡片只给出四个涂色框,第一个表示1第二个表示2,第三个表示4,第四个表示8,如果我们的号码中有个数字是7,我们就将1 2 4都涂上.

    很好,由1,2,4,8这几个数字,我们可以看出,它们能组成1-15中的任何一个数字,如果我们就用这种方法,用掉4个箱子,那第五个箱子,我们就必须要放16个苹果,这样一来,可以组成1-31中的任何一个数字,第六个箱子我们得放32个...依此类推,我们放的是1,2,4,8,16,32...惊讶的发现:这组数字的规律是一个以2为比的等比递增数列,自然而然想到二进制化十进制的方法,11111111B=2的7次幂+2的6次幂+2的5次幂+2的4次幂+...  如此一来,如果我们让每个箱子各对应一个具有10bit的二进制的一位,1表示在第n个箱子放2的n次幂个苹果,我们可以算出,0000000000B~1111111111B的表数范围为:0-1023,而且可以看出,每一个在这中间的数都可以唯一的对应一个二进制数,也就是说针对不同数目的苹果,我们给箱子的时候,只有一种给法,因为只有1000个苹果,所以最后一个箱子我们没有放512个苹果,而是只放了489个,那么1-488只有唯一的给法,489-1000有两种给法.(更正一下:只有489-511有两种给法...1-488和512-1000都只有唯一的给法...)

   显然,第一个题目也是用到了这种思想,我们可以将金条分成1、2、4三段,不管哪天工人向我们要金条,我们都能给他,比如说:工人第一天没有要金条,第二天要的时候,我们给他2段,第三天他没有要,第四天他要我们给金条,于是我们将那块四段的给他,收回那个2段的...