给出成对距离的里程碑位置

Question

有一条'n'个里程碑的直道.您将获得一个数组,其中包含所有里程碑对之间的距离,以某种随机顺序排列.找到里程碑的位置.

例:

考虑一条有4个里程碑的道路(a,b,c,d):

a --- 3Km --- b --- 5Km --- c --- 2Km --- d

a和b之间的距离是3

a和c之间的距离是8

a和d之间的距离是10

b和c之间的距离是5

b和d之间的距离是7

c和d之间的距离是2

所有上述值以随机顺序给出,例如7,10,5,2,8,3.

输出必须是3,5,2或2,5,3.

假设给定数组的长度是n.我的想法是:

1. 通过求解二次方程来计算里程碑的数量,说它是x.
2. 有P(n,x-1)种可能性.
3. 验证每个可能的排列.

有没有更好的解决方案来解决这个问题？

Answer 1

好的。我会给出我的想法，这可以减少排列的数量。

查找 n 很简单，您甚至可以运行逆阶乘https://math.stackexchange.com/questions/171882/is-there-a-way-to-reverse-factorials

假设： 目前我不知道如何找到这些数字。但我想你已经以某种方式找到了这些数字。找到 n 和元素后，我们可以应用它来部分减少计算。

考虑这样一个问题，

|<--3-->|<--6-->|<--1-->|<--7-->|
A       B       C       D       E

现在正如你所说，他们将给出的总和（也以随机顺序）3,9,10,17,6,7,14,1,8,7。

但你可以采取任何组合（大多数情况下都是错误的），

6-3-1-7. (say this is our taken combination)
Now,

6+3 -> 9 There, so Yes    //Checking in the list whether the 2 numbers could possibly be adjacent.
3+1 -> 4 NOT THERE, so cannot
1+7 -> 8 There, So Yes
6+7 -> 13 NOT THERE, So cannot be ajacent

心理念：

对于相邻的 2 个数字，它们的和必须在列表中。如果总和不在列表中，则数字不相邻。

优化 ：

因此，3 和 1 不会出现在附近。6 和 7 不会出现在附近。

因此，在进行排列时，我们可以消除

*31*,*13*,*76* and *67*组合。其中 * 是前面或后面的 0 个或多个数字。

即，不要尝试 4 的排列！= 24次，我们只能检查3617,1637,3716,1736。即只有4次。即节省了 84% 的计算量。

最坏的情况下 ：

假设你的情况是 5,2,3。现在，我们必须执行此操作。

5+2 -> 7 There
2+3 -> 5 There
5+3 -> 8 There

糟糕，您的示例是最坏的情况，我们无法在此类情况下优化解决方案。