騰訊暑期實習筆試題 有趣的梅式砝碼問題

無意間看到這樣的一個題目，題目内容是：

用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，不論是加法或者是減法。

很值得思考的問題~~