use*_*331 0 java algorithm dynamic-programming combinatorics
如果我们愿意的话,我的一位教授给了我们一个在假日期间考虑的问题,而且我不确定解决问题的正确方法.
问题如下:我们有N条线(1≤N≤10^ 6)从A点到B点,但不知道哪条线末端对应于哪条线开始.有三种方法可以解决这个问题:
目标是计算A和B之间所需的最小旅行次数.
例如,对于3根电线,我们需要2次行程:我们连接两根电线并调用第三根电线A.然后我们前往另一点并测试哪根电线未连接到任何其他两根电线.这必须是电线A.然后我们将A与另一根电线连接,称之为B并返回.现在我们必须找到连接到A的电缆,这必须是B,第三个必须是C.
不幸的是,对于某些N来说,不可能弄清楚哪条线是哪条,例如N = 2.(我很确定N = 2是唯一的一条).N = 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
然后找到连接的对端.假设您找到BC,并且DE已连接.然后连接AB,CD.这将为您提供一条从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最初连接而BC是一对,你知道4对应于C.再次连接3-4.
A__B C__D E
| | | | |
\___\__\___
\ \ \
| | |__| |
1 2 3 4 5
看看1或2中的哪一个用5进行,然后你知道哪个对应于D,因此另一个用于E.
您可以使用此方法识别任意数量的奇数线.
对于偶数线,它类似于奇数:
步骤1,做同样的事情,但保持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,似乎没有办法识别它们,除非你被允许携带1个以上的电线,或者至少带一个二极管:P