谜题：找到权重的最小数量

我遇到了这个问题：说给定两个权重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

来源

2010-04-07 avd

你能给出原始问题的链接吗？ – 2010-04-07 04:27:22

您需要提供更多信息：当您有1和3时，您如何测量2？（我假设你使用的是尺度，在这种情况下我知道它是如何工作的，但是你应该在问题中拼出来。） – 2010-04-07 04:30:01

让我改变问题：给定一组整数作为输入。取整数的一个子集，并随机应用加法或减法。一个例子是采取1，2和3，并应用 - ，+，然后变成1 - 2 + 3。每个应用程序产生一个整数。输出是一组所有可能的应用程序。查找生成[1..1000]输出集合的最小输入。 – 2010-04-08 08:40:20

定理：您需要权重3^0至3^N覆盖值1至S（N）=总和（3^i）用于我= 0到N

证明：

你给的基本情况，其中N = 1
现在假设这对于N < M.对于情况N = M，我们将具有权重3^0 = 1至3^M，我们已经知道其涵盖了高达S（M-1）的值。考虑到通过交易方对每个权重的比例，我们可以将所有负值都表示为-S（M-1），并且这些权重也相同。这足以证明我们可以将S（M-1）+1到S（M）表示为3^M + X，其中-S（M-1）< = X < = S（M-1）。但是如果S（M-1）+ 1> = 3^M-S（M-1），则S（M）= S（M-1）+ 3^M。也就是说，如果对于i = 0到M-1，满足（2 * 3^i）3^M < = 1 + 2 * S（M-1）= 1 +这一点对我来说似乎很清楚，但我已经喝了几杯鸡尾酒，而且证明并不是你真正想要的东西，所以我将最后一步作为练习给读者。
通过归纳法，QED。

来源

2010-04-07 04:54:58 Grumdrig

这是通过了解答案而做的。但是，如何在第一时间找到解决方案。虽然很好的证明。 – avd 2010-04-07 05:08:57

有很多有关解决问题技巧的有趣书籍;有趣和有价值。在像这样的问题中，首先解决一个更简单的问题是一种很好的技术。看看它为什么适用于N = 1，然后N = 2，并希望出现一个可以编码的模式。 – Grumdrig 2010-04-07 19:08:37

假设您有一组权重，您可以使用它权衡任何数字，最多为n。现在你想扩展你的权重集来权衡更多的数字，这意味着你想权衡n + 1，n + 2等等。增加权重n + 1，n + 2，...，2n将是多余的。该系列中的下一个重量应该是（（所有以前的重量的总和）* 2）+ 1）

我认为你只是从基本情况1开始，然后继续工作。为了打到2号，你的选择是{2,3,4 ...}。 4 - 1不能到达，2是多余的。之后又出现一个数字。

来源

2010-05-05 21:32:00 0x4f3759df

这是我如何解决了这个问题。假设你有权重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的幂与系数（数字）0,1,2组合写出基数3中的任何数字。

一个类似的事实是，我们也可以使用数字1,0和-1，当我们在基数3写一个数字！

，我们需要得到所有可能的号码事实导致这样的事实，你有可能可以使用的3

权力让人不解的是这样构成的，它的实际工作进行的顺利，你可以证明这一点容易。

同样的想法可以应用于类似的问题，你有弹簧平衡（即只有一个锅）。这里的系数是0和1，并且2的幂次立即出现在脑海中。

而另一个问题：

假设我说你有，每个配重和平衡通用的两个副本，不得不权衡从1所有的权重达到61个，你会选择哪一个权重？

来源

2010-05-17 20:20:50

在基本层面上考虑问题：

如果你想找到的最小权重20公斤，

最初：20 = 1 + 1 + 1 + 1 + 1 + 1 .... （20次）。使用二进制，你可以通过仅使用奇数权重将其分解为一半。

=> 1, 2, 4, 6, 8, 10...20 (for all odd weights even no.s can be "added" by 1) 
     ... 2+1, 4+1, 6+1...18+1.

的3

1  3  6  9  12  15  18  21  24  27 

    2  4 5  7 8 10 11 13 14  16 17  19 20  22 23  25 26 

     _________________ _________________ __________________ ___________________

现在，如果“减法”，也被认为是，即在同时使用的锅，然后我们可以采取倍数我们看到所有的权重可因此通过增加生产减去1〜3的

IMP的多：1高于

下一页的基本单元，我们可以做出3加法和减法的基本单位，因为它可以推断出所有其他数字。因此，考虑3-6-9,9-12-15,16-17-18等可以采取的设置，并且中间项可以被消除。

因此，我们有，

1  3    9     15     21     27 

    2  4 5 6 7 8 10 11 12 13 14  16 17 18 19 20  22 23 24 25 26 

          _________________ __________________ __________________

现在9是我们的基本单元，因为我们可以通过9直接访问来自1的任何数量。如果我们加上或减去，我们得到了18的缝隙。因此，我们已经消除了中产条款：现在

1  3    9               27 

    2  4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

          _________________________________________________________

，经过27 1每一个数字可以推断。因此，27成为我们的基本单位，下一个可以访问的差距将涉及加法和减法27，给出54.

因此，我们可以得出结论，3的幂正被重复，因为3的幂之间的差总是3 （N）。

因此证明。

来源

2015-06-12 10:20:34

谜题：找到权重的最小数量

回答

相关问题