一道有趣的华为笔试题

黑色洗面奶

上周去华为终端固网面试，有到题目很有意思，现公布给大家

题目：1到40的整数，选取其中四个作为天平的砝码重量，这四个砝码的组合可以称出1到40的任意整数重量，这四个数字是什么？

7colors

没思路，顶上去

我的品牌ccc

与钱币差不多

shanxi

把砝码放在一端的话，至少需要6个砝码：1，2，4，8，16，32
砝码允许放在两端的话，至少需要4个砝码：1，3，9，27
情况类似的原因，只解释一下第二种情况：
称出1克需要一个1个的砝码，同样2克也需要一个2克的砝码，1克、2克的砝码则可以称出1、2、3，同样1克、3克可以称出1克、（3-1）克（放在两端）、3克、（3+1）克，再添加一个9克的则可以称出1克到13克的任意整数克，推广的话：用1，3，3^2,……3^n-1克可以称出从1克到（1+3+3^2+……+3^n-1)即1/2（3^n-1）克中的任意一切整数克。
当量程给定时，要确定最少必备的砝码，只需把最大的克数化为进位数，在求各位数码时余数只许是1，0或-1即可。
更为准确的表达是：
要称出1克到n克中的任意整数克数，再只允许放在一端情况下的关键是把：1+x+x^2+……+x^n分解成1+x^a+x^2a+……+x^ma的形式；
同样在两端允许放砝码的情况下则是把：x^-n+x^(-n+1)+……+x^-1+x+x^2+……+x^n分解成x^-(ma)+……+x^-a+1+x^a+……+x^(ma),其中n为要求的最大克数，a就是所需的砝码克数。
比如上个例子（放在两端的情况下）共有8种可能,给出的组合是用砝码最少同时也是唯一没有重复用砝码

[ 本帖最后由 shanxi 于 2007-8-11 11:30 编辑 ]

黑色洗面奶

shanxi好佩服你呀，你这些知识怎么学来的，分享下，我现在做软件测试才1年多，感觉好多东东要学习，压力好大

changlang530

晕！原来这么简单