称重物问题

Joseph

一个商人有一个40克的砝码，由于跌落在地而碎成4块。后来，称得每块碎片的重量都是整克数，而且可以用这4块来称从1至40克之间的任意整数克的重物。问这4块砝码片各重多少？

老猫

很棒的题目！Joseph 上面的是天平秤。

要是你觉得难，可以先做这道：

有一个杠杆秤，货物和砝码的比例是100：1，就是 10克的砝码用来秤1公斤的货物。现在你到商店买了一个这种秤。

而店里的砝码只有 10克、20克、30克、40克......都是十的倍数。考虑到你的货物都是按整公斤卖的，而一般顾客最多买30公斤。那么，你怎么才能买数量最少的砝码，就能一次称出顾客所要的货物质量。

你最少需要几个砝码，这几个砝码分别是多重的。

zyl1p

我来试试。考虑后的答案是 1、3、9、27

考虑的思路是按数字大小排列四个数字A\B\C\D，那么如果A和B能产生的数字为1~X的话，那么加上C可以产生（C-X）～（C+X)范围的数字，同理推算D，而使A+B+C+D=40.

老猫

先说说 来来豆 的答案：1、3、9、27 是正确的，但是思路不算太好。

再看看我在二楼的题目，其实这是一个学计算机基础的人都应该知道的东西，就是“二进制数”，

要想通过不重复的整数相加来得到 0～N 之间的所有整数，答案就是一串的二进制数：

1、10、100、1000、10000......，换算为“十进制数”就是：1、2、4、8、16......

所以，我二楼题目的答案就是：一共五个砝码，分别为：10、20、40、80、160克，利用他们可以一次秤出 31公斤的货物。

那么，来来豆的 1、3、9、27...... 又是什么数呢？ 大家想想。。[em06][em06][em07][em07][em08][em08]

zyl1p

1、3、9、27分别是3的0、1、2、3次方，

因为只能有4个数字，所以用加减来代替二进制数所需要的数字的方法，3－1代替2；3＋1代替4；9－1代替8；27－9－3＋1代替16；27＋9－3－1代替32，这样1、2、4、8、16、32都有了，也就能组成0～N的所有整数了。

不知对否？

Joseph

Gaspard Bachet de Méziriac解法：
假如有一系列砝码A，B，C，…，把它们适当地分放在两个盘上，就能称出从1到n的所有整数克的重物。如果有一块新砝码P，它的重量p超过原有砝码的重量总之和n，超过量为原有砝码重量的总和加1：
p-n= n+1，
或者
p=2n+1，
那么，把砝码P加入砝码组A、B、C、…之后就能称出从1至p+n=3n+1的所有整数克的重物。
这是因为，原有砝码组足以称出所有从1至n克的重物，为了称出1个p+x或p-x克的重物，这里x表示从1到n的任一个数，把砝码P放在砝码盘上，再把砝码A，B，C，…分别放在两个盘上，使砝码盘或称量盘上的重量偏重x克。
此法成立后，这个题目就容易解答了。
为了使两个砝码A和B能称出最多重量，A必须是1克，B必须是3克，这两个砝码能称出1，2，3，4克的重物。
如果选第三块砝码C，使它的重量
c=2×4+1=9（克），
那么用A，B，C三块砝码就能称出从1至c+4=9+4=13克的所有重物。
最后，如果选第四块砝码D，使它的重量
d=2×13+1=27（克），
那么，这四块砝码A，B，C，D便能称出从1至27+13=40克的所有重物。
结论：这个砝码的四块碎片的重量分别为1，3，9，27克。

老猫

以下是引用老猫在5/8/2004 5:49:08 PM的发言： ： 那么，来来豆的 1、3、9、27...... 又是什么数呢？ 大家想想

以下是引用zyl1p在5/8/2004 6:01:47 PM的发言：

1、3、9、27分别是3的0、1、2、3次方，不知对否？

对的，或者你这么说：1、3、9、27 是“三进制数”的：1、10、100、1000......

数学游侠

设有重量为整数个称量单位的砝码A、B、C…，试问其从1个称量单位开始能够连续称量的最大范围，以及此时砝码的重量分布情况。

解：当只有一个砝码A时，能称量的只有1，即连续称量的最大范围为1（即3⁰），砝码重量分布为A=3⁰；

当有二个砝码A、B时，连续称量的最大范围在前者基础上增加后续的3¹个数，即前一个砝码A三种不同的使用情况与B的组合个数（B－A、B、B+A），连续称量的最大范围为1到（3⁰+3¹），砝码重量分布为A=3⁰、B=3¹；

当有3个砝码A、B、C时，连续称量的最大范围增加后续的3²个数，即前二个砝码A、B各三种不同使用情况之一与C的组合个数（C－B－A、C－B、C－B+A、C－A、C、C+A、C+B－A、C+B、C+B+A），连续称量的最大范围为1到（3⁰+3¹+3²），砝码重量分布为A=3⁰、B=3¹、C=3²；

如此递推…

当有n个砝码即在（n－1）个的基础上增加一个砝码N时，连续称量的最大范围增加后续的3^n－1个数，即前（n－1）个砝码各三种不同使用情况之一与N的组合个数，连续称量的最大范围为1到〔3⁰+3¹+3²+…+3^n－1=（3ⁿ－1）/2〕，砝码重量分布为A=3⁰、B=3¹、C=3²、…、N=3^n－1。

因此，4个重量为整数克的砝码，最大称量范围为1到（3⁴－1）/2，即1到40，此时4个砝码的重量分布应为3⁰=1、3¹=3、3²=9、3³=27。

steel_lee

称重问题，主要看题目的前提，如果前提，允许在天平的2端放置砝码（包括可以在放物端放砝码的话），则可以采用3的N次方方式编码，如果只允许在天平的1端放置砝码，则只能是2的N次方方式编码，这样可以确保砝码数量最少。

情况一：只能放天平一边

采用2⁰....2ⁿ方式编码，2^n＋1－1>=P，P是最大能称出的质量数，证明方法，可参见二进制数的数字表示。

情况二：能放天平两边

采用采用3⁰....3ⁿ方式编码，（3^n＋1－1）/2>=P，P是最大能称出的质量数,证明方法可用递归，上面也说到了。

情况三：其实还有一种可以减少1个砝码数量的方法。

如果题目里面没有说明必须必须明确称出物品质量，而是说物品质量，严格控制在1－P之间，而且都是整数，只要求称出这个物品质量，则可以用2*3ⁿ的方式，譬如称3的物品，可以用2，（2，6）称出这个物品比2重，比4轻，所以只能是3。

不过不知道还有没有更少的编码方案了。