我遇到了这个问题:假设有两个重量1和3,你可以称重1,2(乘3-1),3,4(乘3 + 1)(使用平衡两侧).现在找到最小权重数,以便您可以测量1到1000.
所以答案是1,3,9,27 ......
我想知道你是如何达成这样一个解决方案意味着3的权力.思考过程是什么？
资料来源:http://classic-puzzles.blogspot.com/search/label/Google%20Interview%20Puzzles
解决方案:http://classic-puzzles.blogspot.com/2006/12/solution-to-shopkeeper-problem.html
小智 5
这就是我解决问题的方法.假设您有权重a_1,a_2,...,a_r.
现在你可以减轻重量x你有
a_i1 + a_i2 + ... + a_ik = x + a_j1 + a_j2 + ... + a_jl
即x = Sum e_i*a_i
其中e_i是-1,0或1.
即我们需要将每个数字写为a_i与系数1,0或-1的线性组合.
现在我们知道我们可以将基数3中的任何数字写为3的幂与系数(数字)0,1,2的组合.
类似的事实是,当我们在基数3中写一个数字时,我们也可以使用数字1,0和-1!
我们需要获得所有可能数字的事实导致您可能能够使用3的幂.
拼图是如此构造,它实际上运作良好,你可以很容易地证明它.
同样的想法可以适用于你有弹簧平衡的类似问题(即只有一个平底锅).这里的系数是0和1,而2的幂立即浮现在脑海中.
另一个问题:
假设我说你有两个每个重量的副本和一个共同的平衡,并且必须权衡从1到61的所有重量.你会选择哪个重量？