智商吧 关注:203,472贴子:1,885,348
  • 41回复贴,共1

电线问题,较难

只看楼主收藏回复

有一根1km长的电线烧断了(外表看不出断点),工程师要找出断点并修好,检测的方法是这样的:
在电线上选择两点接入工程师的设备然后通电,如果有电说明这两点间的电线是好的,反之则说明这两点间有断点。以上过程记为一次。
工程师要把断点的位置缩小到1cm的范围内才能修好,那么问题来了,要使用什么样的策略才能用最少的次数(指期望)完成任务呢?期望的最少次数是多少?


IP属地:广东来自Android客户端1楼2015-09-02 16:55回复
    @人工智能编程1 @粟密 @悟谶语
    最好带过程


    IP属地:广东来自Android客户端2楼2015-09-02 17:45
    收起回复
      二分法即可。


      IP属地:陕西3楼2015-09-02 18:55
      收起回复
        以3267(√100000)cm为一个间断测一次,遇到断点。在断点范围里以1cm为间断测。期望就是3267??


        IP属地:上海来自Android客户端4楼2015-09-02 19:26
        收起回复
          帮顶


          IP属地:北京来自iPhone客户端5楼2015-09-03 00:29
          收起回复
            2分法,17次


            来自Android客户端6楼2015-09-03 06:57
            收起回复
              2^16<100000
              2^17>100000
              所以17次最少


              IP属地:北京7楼2015-09-03 13:10
              回复
                其实在现实中接入2次就够了,然后用感应电笔检测


                IP属地:广西来自Android客户端9楼2015-09-03 13:25
                收起回复
                  用N分法:
                  每一轮中要发现断点所在区间,最少测1次,最多测N-1次,平均N/2次。
                  而一轮试验可以把范围缩小到1/N。
                  所以,要想把范围缩小到1/100000,需要做:【以N为底log100000】那么多轮(黑括号表示“只入不舍取整”)。
                  所以,总的期望是【以N为底log100000】*N/2次。
                  下面用纯数学证明此式N为2时最小即可。因时间关系祥细证明略。应该不太难。


                  IP属地:陕西10楼2015-09-03 16:29
                  收起回复
                    有更笨的检测方法么


                    IP属地:广东来自Android客户端11楼2015-09-03 17:57
                    收起回复
                      直接连接一端,另一端用个滑动接头,滑到哪通了就是断点


                      来自Android客户端12楼2015-09-03 20:08
                      收起回复
                        给我一个收音机,楼主


                        来自iPhone客户端13楼2015-09-03 22:44
                        收起回复
                          dd


                          来自iPhone客户端14楼2015-09-04 09:40
                          回复