PCEVA,PC绝对领域,探寻真正的电脑知识
开启左侧

研究一下,从一大堆元素里,找出无用元素的快速算法

[复制链接]
haierccc 发表于 2020-11-13 13:55 | 显示全部楼层 |阅读模式
点击数:4543|回复数:14
本帖最后由 haierccc 于 2020-11-13 19:39 编辑

我在一次做实验的过程中,碰到一个问题,我抽象成如下场景,大伙看看该怎样解决。
如下图,有2个电台,为了使这2个电台互通,必须要连接3根线,分别是K1,K2和K3,注意是要”同时“接这3根线电台才能通:
无标题.png
然后,在这2个电台之间,还有多余的3根线,这里用红色表示,因为画不下就写标签了:
无标题.png
于是我们看到,这2个电台之间连接了6根线。
对于一个旁观者而言,他看到了电台之间有6根线,而且他还知道这6根线里肯定有多余的。
现在,他想把这多余的线找出来撤掉,只留下K1,K2和K3。
怎样的算法能在最短的时间内,经历最少的尝试次数找出这3根线呢?
求解。
印第安纳琼斯 发表于 2020-11-13 15:16 | 显示全部楼层
那旁观者怎么观察知道哪根线是必须的呢?
尊称 发表于 2020-11-13 16:34 | 显示全部楼层
排序算法应该可以吧
查找快速排序,以及算法分析,我记得有
haierccc  楼主| 发表于 2020-11-13 18:08 | 显示全部楼层
印第安纳琼斯 发表于 2020-11-13 15:16
那旁观者怎么观察知道哪根线是必须的呢?

这就是我的问题啊
haierccc  楼主| 发表于 2020-11-13 18:08 | 显示全部楼层
尊称 发表于 2020-11-13 16:34
排序算法应该可以吧
查找快速排序,以及算法分析,我记得有

应该有,这个问题应该经常遇到
印第安纳琼斯 发表于 2020-11-13 19:31 | 显示全部楼层
本帖最后由 印第安纳琼斯 于 2020-11-13 20:03 编辑
haierccc 发表于 2020-11-13 18:08
这就是我的问题啊

所以旁观者每拿起一根线就要问你这根线对不对是不?

这就好比一个师傅带一个刚上班的学徒,去摸排一堆没有标注的电线?不过我觉得这个实操流程应该不是你这道题的目的。

既然是三根有用三根没用,那么最快,运气最好的就是一下子拔掉三根线,发现电台仍正常通信,那这三根就是“天胡”,速度最快咯。如果发现只有一根或两根有用,那么剩下的就在剩下的三条线之中,依此排除即可)。但是这三根线到底是同时接上才能确定有用,还是其中一根接上就能确定有用,所以前面才想问旁观者如何排查咯。

如果六条线都是一样的,那可以先把线全拆掉,任意在一头短路其中三条,然后另一个人在另一头用电表测试出是哪三条,接着短路那头断开其中一条,在另一头的再次电表测量那三条线,即可确认一条线,记作K1。然后再随机并上一条,测量,又确定一条,记作K2;如此再重复,记作K3。然后按顺序接好。
haierccc  楼主| 发表于 2020-11-13 19:38 | 显示全部楼层
印第安纳琼斯 发表于 2020-11-13 19:31
所以每拿起一根线就要问你这根线对不对是不?

不仅仅是                  
尊称 发表于 2020-11-14 02:09 | 显示全部楼层
印第安纳琼斯 发表于 2020-11-13 19:31
所以旁观者每拿起一根线就要问你这根线对不对是不?

这就好比一个师傅带一个刚上班的学徒,去摸排一堆没 ...

古代有个数学难题是这样说的

有十二枚金币,其中有一枚假币,重量不同,用一个天平选出这枚假币,试问多少次最少?


这个问题我从大学宿舍带到单身宿舍,解决这个问题的时间从几天到几个小时不等,充分能验证脑袋瓜子灵不灵? 楼主这个问题是算法不是解决方法,算法的目的是找到答案的方法,而不仅仅是答案本身。曾经单身宿舍的时候,饼干桶买的时候送的拼图,边要拼接,图案也要拼接,完成这个拼图知道答案秒拼,但上述最聪明的脑子也找不出一个答案,真的很难拼。我用搜索树的算法电脑瞬间打印出成千个答案,这就是算法和答案的区别所在。呵呵呵呵
尊称 发表于 2020-11-14 02:20 | 显示全部楼层

你到底要的是答案还是找到答案的方法?
haierccc  楼主| 发表于 2020-11-14 07:26 | 显示全部楼层
尊称 发表于 2020-11-14 02:20
你到底要的是答案还是找到答案的方法?

是方法。我想了一个方法,应该可行,但不知道是不是最优的。
① 拔下所有的线
② 挨个接上,假如说接到K3,电台就通了,于是我得出结论:K3肯定是其中之一
③ 拔下所有的线,首先接K3
④ 再随机往下接,假如说接到K1电台通了,于是我又知道,K1也是其中之一
⑤ 拔下所有的线,接入K3和K1,再随机往下接。。。
这样就能试出来所有的有效线路了。
这样能行不?

haierccc  楼主| 发表于 2020-11-14 07:30 | 显示全部楼层
印第安纳琼斯 发表于 2020-11-13 19:31
所以旁观者每拿起一根线就要问你这根线对不对是不?

这就好比一个师傅带一个刚上班的学徒,去摸排一堆没 ...

你说的方法是我在下方说的方法么?
但我是一条一条的试。
haierccc  楼主| 发表于 2020-11-14 07:32 | 显示全部楼层
尊称 发表于 2020-11-14 02:09
古代有个数学难题是这样说的

有十二枚金币,其中有一枚假币,重量不同,用一个天平选出这枚假币,试问多 ...

一个是考验编程,一个是考验算法。利用PC的蛮力搜索的确也是方法之一,我记得叫“穷举”,当年在学编程的时候也这样写过。
团结 发表于 2020-11-14 08:29 | 显示全部楼层
随机拔掉一根线,还通就是没用的不通了就是有用的再插上,很快就能找出来
haierccc  楼主| 发表于 2020-11-14 08:34 | 显示全部楼层
团结 发表于 2020-11-14 08:29
随机拔掉一根线,还通就是没用的不通了就是有用的再插上,很快就能找出来 ...

是的                        
印第安纳琼斯 发表于 2020-11-14 13:02 | 显示全部楼层
本帖最后由 印第安纳琼斯 于 2020-11-14 13:34 编辑
尊称 发表于 2020-11-14 02:09
古代有个数学难题是这样说的

有十二枚金币,其中有一枚假币,重量不同,用一个天平选出这枚假币,试问多 ...

开始的条件不够,所以就随便举咯。
现在知道是三根同时接通才能“灯亮”,那就一条一条拔掉试。随机排好顺序,然后逐条试,最多拔5条,运气好只需拔3条。还有一种奢侈的方法,就是“做一个监测工具接上”,哪根线有信号,灯就亮,这样就能在电台不中断工作的情况下拔掉线。就像外挂之类

您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回顶部