作者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