| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4735 人关注过本帖
标题:在一堵无限长的墙上找门的问题,求最有效率的算法
只看楼主 加入收藏
flylee
Rank: 5Rank: 5
等 级:职业侠客
帖 子:309
专家分:374
注 册:2004-8-10
收藏
得分:0 
不明白楼上所说的
如果门的位置是-1,那怎么找到门?
2006-08-29 16:53
ww84020209
Rank: 1
等 级:新手上路
帖 子:190
专家分:0
注 册:2006-8-21
收藏
得分:0 
有什么不懂啊。
那0,1,-1,2,-2,。。。你懂吗?

2006-08-29 17:11
SunShining
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:31
帖 子:2215
专家分:0
注 册:2006-2-17
收藏
得分:0 
以下是引用ww84020209在2006-8-29 12:57:58的发言:

这明显不是最快的,最快的算法是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,。。。快!!!



看来俺真的重新看看复杂度的概念了..
当时我也想过这个算法...
可还是单纯的认为在某些时候LZ的应该快....


[glow=255,violet,2]闭关修炼ing...[/glow] [FLASH=360,180]http://www./chinaren.swf[/FLASH]
2006-08-29 18:10
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
以下是引用ww84020209在2006-8-29 12:57:58的发言:

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

最坏情况下,楼主的算法是最快的.

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

楼上的你知不知道我的O(n)表示的是什么呢?
要求最有效率的算法 ,也就是要求人跑的路程最少
O(n)表示人跑的路程!


2006-08-29 18:30
lrmymycn
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2006-8-23
收藏
得分:0 
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.

这里是说steps,但是好像做路程的话题目会比较有趣

我去问问老师先

感谢大家帮忙
2006-08-30 02:06
ww84020209
Rank: 1
等 级:新手上路
帖 子:190
专家分:0
注 册:2006-8-21
收藏
得分:0 

你那个steps和我的路程是一个意思。
steps就是指所走的总步数。


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

刚问了,这里的steps是只脚步,不是指步骤,和楼上说的一样

2006-08-30 13:52
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
以下是引用ww84020209在2006-8-29 18:30:32的发言:

楼上的你知不知道我的O(n)表示的是什么呢?
要求最有效率的算法 ,也就是要求人跑的路程最少
O(n)表示人跑的路程!



是偶没理解好题意,太土了偶..................


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-08-30 17:59
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
要求人跑的路程最少
这个思想是正解

我得找只笔来算算

[此贴子已经被作者于2006-9-3 17:38:32编辑过]


我的征途是星辰大海
2006-09-03 17:37
快速回复:在一堵无限长的墙上找门的问题,求最有效率的算法
数据加载中...
 
   



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

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