java - 使用某些操作找到相应的电线起点和终点所需的行程数

Question

我的一位教授给了我们一个问题，如果我们愿意的话，可以在假期中考虑，但我不确定解决该问题的正确方法。

问题如下: 我们有 N 根电线(1 ≤ N ≤ 10^6)，它们从 A 点到 B 点，但不知道哪根电线末端对应哪根电线起点。可以通过三种方式解决这个问题:

• 在 A 点和 B 点之间行驶
• 连接电线。 (这意味着您使用一部分电线并将它们连接起来，这样您就可以将它们的末端用作一个单一的末端)
• 测试电线是否连接。 (你可以把它想象成电源线:例如，如果一些电线连接在 A 点，你在 B 点为这些连接的电缆之一供电，你可以看到连接了哪些电缆，因为它们也将被供电)

目标是计算 A 和 B 之间所需的最少行程数。

例如对于 3 根电线，我们需要 2 次行程:我们连接两根电线并将第三根电线称为 A。然后我们走到另一点并测试哪根电线没有连接到其他两根电线中的任何一根。这必须是电线 A。然后我们将 A 与另一根电线连接，称之为 B 并返回。现在我们必须找到连接到 A 的电缆，这必须是 B，第三根必须是 C。

不幸的是，对于某些 N 来说，无法弄清楚哪根电线是哪根电线，例如对于 N = 2。(我很确定 N = 2 是唯一的)。 N = 1 表示零行程。

非常感谢任何有关如何处理此问题的建议。

Answer 1

碰巧我以前解决过类似的难题。

对于 N > 2，您始终可以通过 2 次行程来识别电线。

---

对于奇数根线(我以5根为例)

A  B  C  D  E
|  |  |  |  |

|  |  |  |  |
1  2  3  4  5

(假设你现在在“数字”这边)

首先像这样连接线:

A  B  C  D  E
|  |  |  |  |

|__|  |__|  |
1  2  3  4  5

然后前往“Alphabet”一侧。应该有一根电线没有连接到任何另一端(通过与另一端的电导率测试)。假设那是A，那么你就知道A对应5

然后找到连接的末端对。假设您发现 B-C 和 D-E 相连。然后连接A-B，C-D。这将为您提供一根从 5 到 E 的长电线。

A__B  C__D  E
|  |  |  |  |
\__________    
           \
|__|  |__|  |
1  2  3  4  5

回到“数字”这边。断开这边的所有连接

A__B  C__D  E
|  |  |  |  |
\__________    
           \
|  |  |  |  |
1  2  3  4  5

然后测试哪根线与5导通。假设是3，则知道3对应B。假设3-4原来是连在一起的，B-C是一对，就知道4对应C。再接3-4。

A__B  C__D  E
|  |  |  |  |
\___\__\___    
     \  \  \
|  |  |__|  |
1  2  3  4  5

看看 1 或 2 中哪一个与 5 行为，然后你就知道哪个对应于 D，因此另一个对应于 E。

您可以使用这种方法来识别任意数量的奇数线。

---

对于偶数根线，与奇数根类似:

第一步，做同样的事情，但不连接2根线

A  B  C  D  E  F
|  |  |  |  |  |

|__|  |__|  |  |
1  2  3  4  5  6

到 Alphabet 一侧，这一次，您应该会发现 2 根电线不与任何其他电线导通(假设为 A 和 F)。保持其中之一不变(假设 F)。按照奇数法将 A 连接到 E。

回到数字端。你会发现 5 或 6 中的一个不与任何其他导线导通(假设 6)，你知道它对应于 F。

A__B  C__D  E  F
|  |  |  |  |  |
\__________    |
           \   |
|__|  |__|  |  |
1  2  3  4  5  6

因此，您确定了 6-F 和 5-A。其余的只是上面描述的奇数情况。

---

是的，对于 N = 2，似乎无法识别它们，除非允许您多带一根电线，或者至少带一个二极管 :P