| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4729 人关注过本帖
标题:在一堵无限长的墙上找门的问题,求最有效率的算法
只看楼主 加入收藏
lrmymycn
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2006-8-23
收藏
 问题点数:0 回复次数:26 
在一堵无限长的墙上找门的问题,求最有效率的算法

你面对着一堵墙,左右2边都无限长

墙上有一扇门,有可能在左边也有可能在右边,你只有站在门前才能看到这扇门

求找这扇门最有效率的算法 O(n),门离你初始位置有n步

我的做法是 0 1 -1 2 -2 3 -3 。。这样一直找下去

不知道对不对,请教


付上原题,希望没有理解错误

You are facing a wall that stretches infinitely in both directions. There is a door in the wall, but you know neither how far away nor in which direction. You can see the door only when you are right next to it. Design an algorithm that enables you to reach the door by walking at most O(n) steps where n is the (unknown to you) number of steps between your initial position and the door.

搜索更多相关主题的帖子: 有效率 算法 
2006-08-25 15:37
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 

你的想法应该是对的,
这其实跟找迷宫的出口差不多,只不过它只有两个方向.
其实也就是广度优先搜索.


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-08-25 17:38
ww84020209
Rank: 1
等 级:新手上路
帖 子:190
专家分:0
注 册:2006-8-21
收藏
得分:0 

这样也能算最快???


2006-08-26 16:12
lrmymycn
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2006-8-23
收藏
得分:0 

楼上的有什么好的建议吗?

2006-08-27 01:13
SunShining
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:31
帖 子:2215
专家分:0
注 册:2006-2-17
收藏
得分:0 
[QUOTE]0 1 -1 2 -2 3 -3 [/QUOTE]

这种方法应该是可以的..不过为了减少时间.须使用临时变量记载上次步子的位置..

[glow=255,violet,2]闭关修炼ing...[/glow] [FLASH=360,180]http://www./chinaren.swf[/FLASH]
2006-08-27 12:35
lrmymycn
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2006-8-23
收藏
得分:0 

OK。多谢回答

2006-08-27 21:15
flylee
Rank: 5Rank: 5
等 级:职业侠客
帖 子:309
专家分:374
注 册:2004-8-10
收藏
得分:0 
顺便说一下,2楼的说这是广度优先搜索,其实并不是
广度优先搜索指的是,比如在树中,先把一层节点搜索完后再进行下一层的搜索,而深度优先搜索就是把一个节点不断扩展搜索下去,直到叶节点,然后再返回其父节点重复这种动作
一般来说广度优先搜索适合用来求解一些最短路径或者最短操作数之类的问题,而深度优先搜索除了编程比较简单之外实在想不出有什么优势,而许多更高级的算法是一些判断的函数结合进这两种搜索之中,比如迭带加宽、迭带加深、启发式搜索等
2006-08-28 14:57
xinfresh
Rank: 4
等 级:贵宾
威 望:13
帖 子:594
专家分:0
注 册:2006-1-13
收藏
得分:0 
大家都是推测罢了,虽然我也认为这种方法不错,但有没有谁可以从理论上证明一下它就是最有效的呢?毕竟"口说无凭"么

E-mail:xinfresh@QQ:383094053校内:http:///getuser.do?id=234719042
2006-08-28 20:17
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
以下是引用flylee在2006-8-28 14:57:28的发言:
顺便说一下,2楼的说这是广度优先搜索,其实并不是
广度优先搜索指的是,比如在树中,先把一层节点搜索完后再进行下一层的搜索,而深度优先搜索就是把一个节点不断扩展搜索下去,直到叶节点,然后再返回其父节点重复这种动作
一般来说广度优先搜索适合用来求解一些最短路径或者最短操作数之类的问题,而深度优先搜索除了编程比较简单之外实在想不出有什么优势,而许多更高级的算法是一些判断的函数结合进这两种搜索之中,比如迭带加宽、迭带加深、启发式搜索等

这题楼主的做法其实就是先把距离是1的一层节点搜索完后再进行距离是2的一层的搜索,(1 -1, 2 -2, 3 -3 );
怎么不是广搜?

汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-08-28 23:09
ww84020209
Rank: 1
等 级:新手上路
帖 子:190
专家分:0
注 册:2006-8-21
收藏
得分:0 

这明显不是最快的,最快的算法是0,1,-2,4,-8,16,。。。
0 1 -1 2 -2 3 -3 。。这种算法复杂度为n*(2n-1),也即O(n^2)
而0,1,-2,4,-8,16,。。。,这种算法复杂度为3n-2,也即O(n)
明显是0,1,-2,4,-8,16,。。。快!!!


2006-08-29 12:57
快速回复:在一堵无限长的墙上找门的问题,求最有效率的算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019806 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved