亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

  免費注冊 查看新帖 |

Chinaunix

  平臺 論壇 博客 文庫
123下一頁
最近訪問板塊 發(fā)新帖
查看: 8263 | 回復(fù): 28
打印 上一主題 下一主題

[算法] 請教一道看似簡單，卻不平凡的算法題！ [復(fù)制鏈接]

論壇徽章:
0
跳轉(zhuǎn)到指定樓層
1樓 [收藏(0)] [報告]
發(fā)表于 2006-01-18 03:41 |只看該作者 |倒序瀏覽
請教我面試某公司時碰到的一道算法題：

1. 你面對一堵左右無限延伸的墻；
2. 該墻有且只有1扇門，它在離你 n 步遠的地方；
3. 你不知道 n 的大小，也不知道門在你左邊還是右邊；
4. 你一次能夠向左或者向右走一步，你只有走到門所在的位置才能出去。
請設(shè)計一個O(n)的算法，找到這扇門。
請問在最壞情況下，你這個O(n)算法的常數(shù)系數(shù)最小是多少？也就是說，在最壞情況下，你找到門需要走的步數(shù)
S <= K*n+C, K和C都是常數(shù)，求最小的K。

歡迎大家討論。

論壇徽章:
0
2樓 [報告]
發(fā)表于 2006-01-18 08:16 |只看該作者

迷宮問題

請參考清華出版社出版的數(shù)據(jù)結(jié)構(gòu)

論壇徽章:
0
3樓 [報告]
發(fā)表于 2006-01-18 09:45 |只看該作者
走法很簡單,但復(fù)雜度估計比較繁

[ 本帖最后由 yzc2002 于 2006-1-18 09:49 編輯 ]

walk.JPG (57.26 KB, 下載次數(shù): 54)

walk.JPG

論壇徽章:
0
4樓 [報告]
發(fā)表于 2006-01-18 13:32 |只看該作者
每次是上一次的2倍

如果用1.618倍,會不會好一些,當(dāng)然計算出的步數(shù)要取整的

論壇徽章:
0
5樓 [報告]
發(fā)表于 2006-01-18 13:43 |只看該作者
你怎么證明是每次2倍，而不是3倍或者1.4倍最優(yōu)？這樣只是提出這是一種O(N)的算法，但沒有證明這樣最優(yōu)吧？

論壇徽章:
0
6樓 [報告]
發(fā)表于 2006-01-18 14:56 |只看該作者
原帖由 emacsnw 于 2006-1-18 13:43 發(fā)表
你怎么證明是每次2倍，而不是3倍或者1.4倍最優(yōu)？這樣只是提出這是一種O(N)的算法，但沒有證明這樣最優(yōu)吧？


題目沒有問設(shè)計的O(n)如何最佳，而是要你設(shè)計一個O(n) 的算法。

論壇徽章:
0
7樓 [報告]
發(fā)表于 2006-01-18 16:09 |只看該作者
原帖由 AndyFastow 于 2006-1-17 22:56 發(fā)表


題目沒有問設(shè)計的O(n)如何最佳，而是要你設(shè)計一個O(n) 的算法。


有問O(n)算法系數(shù)K最小多少。

論壇徽章:
0
8樓 [報告]
發(fā)表于 2006-01-18 16:29 |只看該作者
可以得出k最小為4:

t.JPG (17.91 KB, 下載次數(shù): 47)

t.JPG

論壇徽章:
0
9樓 [報告]
發(fā)表于 2010-02-27 11:23 |只看該作者
這道題目，一般性的證明感覺有點難度

論壇徽章:
0
10樓 [報告]
發(fā)表于 2010-02-27 11:37 |只看該作者
不知道怎么做��！
您需要登錄后才可以回帖 登錄 | 注冊

本版積分規(guī)則 發(fā)表回復(fù)

  

北京盛拓優(yōu)訊信息技術(shù)有限公司. 版權(quán)所有 京ICP備16024965號-6 北京市公安局海淀分局網(wǎng)監(jiān)中心備案編號：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年舉報專區(qū)
中國互聯(lián)網(wǎng)協(xié)會會員  聯(lián)系我們：huangweiwei@itpub.net
感謝所有關(guān)心和支持過ChinaUnix的朋友們 轉(zhuǎn)載本站內(nèi)容請注明原作者名及出處

清除 Cookies - ChinaUnix - Archiver - WAP - TOP