如何制造个数最少的单位砝码,如 1g,2g,3g,4g……,使得这些单位砝码能称出1g到100g之间的任何整数克的物体?
最直观的感受是直接使用1,2,4,8......,64 。也就是20,21,22......26,一共7个砝码,因为任何数字都可以表示成二进制数,比如100用二进制表示就是:1100100,所以使用22,25,26三个砝码即可。任何数字都可以表示为二进制数,在这里就意味着任何重量都可以用上述2n砝码表示。
但这是最少数量的砝码吗?
这要视情况而定,如果只能在天平的一边放砝码,另一边放物品,这就是最少的方案。因为对于砝码而言只有两种状态:放与不放,对于n个砝码,可能出现的总体状态有2n种状态,要表示100个数据则要保证2n>=100,得最小的n=7,意思就是说不管什么砝码方案,至少都要7个砝码。而前面我们猜想的方案正好是7个砝码,正好是理论推导出的最少砝码个数,不会比这个数目更少了,所以是一个最少的方案。
如果允许天平两边都放砝码,也就是说物品可以和砝码放在一边,上述2n砝码方案就不是最少的方案了。
因为砝码有三种状态:不放、放左边和放右边。
对于n个砝码,可能出现的总体状态有3n种状态,要表示100个数据则要保证3n>=100,的最小的n=5,意思就是说不管什么砝码方案,至少都要5个砝码。
接下来我们尝试一下能不能找到5个砝码的方案。
任意一个数都可以表示成三进制的数,比如100用三进制表示就是10201,通过减法,我们又可以把任意一个三进制数化成只有0和1的形式,比如将10201化成10201=11001-100。而且减数与被减数相同位上的数字必然不会同时为1,假如化成减法形式后相同位同时为1,比如110-10,两个数的十位上都为1,结果必然是100,没有2,所以不用化简,矛盾。
综上,30,31,32......34一共5个砝码一定可以表示出从1到30+31+32+...+34=121的所有数(注:不是35-1)