我们用一个等臂天平来称物体的质量,如果我们要称的物体质量范围在1到40克(整数),请问我们最少需要几块砝码可以完成这项物体质量的称量?
A: 3 B: 4 C: 5 D: 6 E: 7
答案：B 4块
思路一：
从1开始：缺少1，+1(需要重量为1的砝码) 2：缺2，但是前面最大可能满足的元素为1，所以下个砝码可以为3（3-1=2） 3： 4： 5：缺5，而前面的砝码可以最大表示4，所以为了满足5，下个砝码可以为4+5=9（尽可能稀疏） OK，现在我们前两个砝码可以表示范围为1-4；所以《9-4，9+4》的范围统统可以表示，也即《5，13》都可以表示了。 14：缺少14，前面砝码最大可以表示为13，所以为了满足14的要求，下个砝码应该为13+14=27，如此，前面3个砝码的最大范围为1-13，故而，《27-13，27+13》的范围便统统可以表示了【14，40】 于是最少需要4个砝码
思路二：
此题可以看成用多少个数可以表示1-40之间任何一个数。砝码有三种状态，放在物体同侧，放在物体另一侧，并不使用。 所以这些数之间可以加可以减，也可以不计算在内。考虑用对称三进制来计算，即，-1，0，1三个状态。40可以用1111来表示，所以最多只用四个砝码就可以表示1-40之间所有数。
扩展：如何实现称出1∼n 克的物品，请问最少需要几颗砝码？
#include <iostream> using namespace std; int main(){ long long T,n; cin>>T; { while(cin>>n){ long long ans = 0; long long t = 1 , sum = 0; while(sum<n){ ans++; sum+=t; t*=3; } cout<<ans<<endl; } } return 0; }