作者happykyoko (老被好人当的人)
看板Prob_Solve
标题[问题] 找墙上的门问题
时间Thu Mar 19 00:18:04 2009
Door in a wall. 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.
我这学期开始修演算法
但或许我真的没有数理方面的天份吧
演算法教什麽几乎都不懂
这题是我课本的例题
类似益智问答的演算法题目
我们老师很重视这一题 但是我却完全看不懂
这题是在无穷远的墙上找门
老师当初是给我们提示说
人站在墙前却不知道门到底左边右边 也不知道门多远
所以可以先往右走n步 找不到就回到原点再往左走n步
而找不到又回到右边再加n步的距离 以此类推
这个概念老师在说的时候能够理解
但是要我写成演算法我就卡住了
一开始我是想到离散数学有教过证自然数可数的题目
有觉得跟离散有点像 但是又不敢确定
百思不得其解只好上来问人了
请求哪位教我这题该怎麽写才好 m(_ _)m
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.170.14.206
1F：推 ars1an:以2^i级数作步数来左右寻找 03/19 04:29
2F：→ netsphere:其实这跟演算法无关了吧 因为演算法已经告诉你了 03/19 21:52
3F：→ netsphere:剩下的是程式设计实做了 . 大概两层loop解决吧 03/19 21:53
4F：→ happykyoko:演算法课本的例题跟演算法无关@@? 03/20 02:06
5F：推 alden:重点是要证明这个方法是O(n)吧? (方法就是你原文写的) 03/21 09:20
6F：推 freeform:问题的确在於不知道n,却必须控制步数在O(n)。可以想到的 03/21 16:29
7F：→ freeform:必须快速增加左右搜寻的步数，也就是在某次的搜寻步数 03/21 16:31
8F：→ freeform:与之前的总步数在same order。所以我想一楼的方法就可以 03/21 16:32
9F：推 ledia:一楼对, 这跟演算法有关, 一次增加的比例太少会超过 O(n) 03/22 22:51
10F：→ ledia:需要演算法证明 (虽然还算 trivial) 03/22 22:51
11F：推 yyc1217:可以换成没有上限的去猜一个商品的价钱 03/28 20:05