(算法)天平问题

题目:

我们用一个等臂天平来称物体的质量,如果我们要称的物体质量范围在1到40克(整数),请问我们最少需要几块砝码可以完成这项物体质量的称量?

思路:

将上述问题转换为一个数学问题,即通过什么样的数字组合来表示某个范围整数。

具体到题目,就是怎么样来表示1到40,可以很快想到我们表示整数的方法,二进制、十进制等等。

那么选择哪种进制呢?肯定是进制数越大,需要的位数越少,但同时也需要考虑实际情况——天平,第二个要点是最少。

砝码对于天平而言,只有三种选择:1、物体同侧,2、物体异侧,3、不放上天平。

很快,我们就可以得到答案,我们可以通过三进制来表示,3^3 < 40 <3^4,因此只需要4个数即可表示1~40,即1,3,9,27.

所以,最少需要4块砝码可以完成这项物体质量的称量。

考虑一下二进制,2^5 < 40 < 2^6,因此需要的是6个数。

原文地址:https://www.cnblogs.com/AndyJee/p/5042464.html