首页 > 其他 > 详细

腾讯暑期实习笔试题 有趣的梅式砝码问题

时间:2014-05-02 22:16:09      阅读:463      评论:0      收藏:0      [点我收藏+]

无意间看到这样的一个题目,题目内容是:


用4个砝码称出1到40的重量的物体,这四个砝码的重量分别是多少??


此处有一点必须注意,很多人一拿到题目(包括我自己),一下子就想到了二进制的解法,可是立刻就发现,二进制的40需要的位数大于4位,也就是说不靠谱。


更加值得注意的是,二进制的方法用在此处,相当于只是将砝码做加法,并未考虑减法,见过天平的同学都知道,砝码是可以和物体放在一边的。因此是可以做减法的。


看了大多数人的题解,提到了,这是一个“梅式砝码”的问题,首先:作出如下假设:(有点类似数学归纳)

假设现在有a1,a2,a3,....,am个砝码,移动可以称出 (1  到  a1+a2+a3+....am)这些重量的物体

那么再增加一个重量为 b =  (a1+a2+...+am)*2+1 的物体,那么就可以称出重量为  1  到  (a1+a2+...+am)*2+1 的物体。

虽然这个结论很显然,但是做一个小推断吧:

首先,通过 这 a1,a2,a3,....,am    m个砝码,可以得到数字  1,2,3 , 。。。 , (a1+a2+...+am)。

其次,加入  b 之后,可以得到的重量: 1,2,3 , ..., (a1+a2+...+am)依然可以得到。

接着利用b分别去减上述得到的重量

可以得到: 

b - 1 =( a1 + a2 + ... +am)*2;  

b - 2 =( a1 + a2 + ... +am)*2-1;

..... , 

b - (a1+a2+...+am) = (a1+a2+...+am)+1;

将这些重量逆序。便是  (a1+a2+...+am)+1 到  ( a1 + a2 + ... +am)*2 +1 的重量了。

显然,可以通过上述递推式得到答案为 1,3,9,27



关于此问题的一些思考:

当我把这道题问其他人的时候,一致想到的都是进制相关的问题,也就是说40用二进制表示需要的位数是大于4的,那么不能使用二进制来考虑,他直接脱口而出答案,让我特别惊讶,他的理由是:不能使用二进制,那就是用3进制啊。

这难道只是巧合吗?至今想不明白。。。既然所有的进制都能表示所有的整数,那么为什么其他进制不可以呢。唯一能够想到的限制便是这里的砝码的个数只能是1,也就是说在该进制表示下,各个位上的数字只能是1,不论是加法或者是减法。

很值得思考的问题~~

  






腾讯暑期实习笔试题 有趣的梅式砝码问题,布布扣,bubuko.com

腾讯暑期实习笔试题 有趣的梅式砝码问题

原文:http://blog.csdn.net/xuqingict/article/details/24837547

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!