免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 8020 | 回复: 28

[算法] 请教一道看似简单,却不平凡的算法题! [复制链接]

论坛徽章:
0
发表于 2006-01-18 03:41 |显示全部楼层
请教我面试某公司时碰到的一道算法题:

1. 你面对一堵左右无限延伸的墙;
2. 该墙有且只有1扇门,它在离你 n 步远的地方;
3. 你不知道 n 的大小,也不知道门在你左边还是右边;
4. 你一次能够向左或者向右走一步,你只有走到门所在的位置才能出去。
请设计一个O(n)的算法,找到这扇门。
请问在最坏情况下,你这个O(n)算法的常数系数最小是多少?也就是说,在最坏情况下,你找到门需要走的步数
S <= K*n+C, K和C都是常数,求最小的K。

欢迎大家讨论。

论坛徽章:
0
发表于 2006-01-18 08:16 |显示全部楼层

迷宫问题

请参考清华出版社出版的数据结构

论坛徽章:
0
发表于 2006-01-18 09:45 |显示全部楼层
走法很简单,但复杂度估计比较繁

[ 本帖最后由 yzc2002 于 2006-1-18 09:49 编辑 ]
walk.JPG

论坛徽章:
0
发表于 2006-01-18 13:32 |显示全部楼层
每次是上一次的2倍

如果用1.618倍,会不会好一些,当然计算出的步数要取整的

论坛徽章:
0
发表于 2006-01-18 13:43 |显示全部楼层
你怎么证明是每次2倍,而不是3倍或者1.4倍最优?这样只是提出这是一种O(N)的算法,但没有证明这样最优吧?

论坛徽章:
0
发表于 2006-01-18 14:56 |显示全部楼层
原帖由 emacsnw 于 2006-1-18 13:43 发表
你怎么证明是每次2倍,而不是3倍或者1.4倍最优?这样只是提出这是一种O(N)的算法,但没有证明这样最优吧?


题目没有问设计的O(n)如何最佳,而是要你设计一个O(n) 的算法。

论坛徽章:
0
发表于 2006-01-18 16:09 |显示全部楼层
原帖由 AndyFastow 于 2006-1-17 22:56 发表


题目没有问设计的O(n)如何最佳,而是要你设计一个O(n) 的算法。


有问O(n)算法系数K最小多少。

论坛徽章:
0
发表于 2006-01-18 16:29 |显示全部楼层
可以得出k最小为4:
t.JPG

论坛徽章:
0
发表于 2010-02-27 11:23 |显示全部楼层
这道题目,一般性的证明感觉有点难度

论坛徽章:
0
发表于 2010-02-27 11:37 |显示全部楼层
不知道怎么做啊!
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP