請教一道看似簡單，卻不平凡的算法題！

xyfree

之前發(fā)的還在修改中。

emacsnw

這個貌似是我四年前發(fā)的一道老題。怎么被挖出來了。:wink:

具體答案我也不清楚，我的回答大致和3樓/8樓差不多。

ps：該公司是Google.

redspider

出題的人是不是找不到數(shù)學模型對應(yīng)的實際應(yīng)用，就扯出了一道能無限延伸的墻？

cjaizss

可以證明:
對于數(shù)列{f(n)}
f(n)滿足:
1.正項數(shù)列
2.嚴格單調(diào)增數(shù)列
3.{f(n+1)/f(n)}數(shù)列為無窮大數(shù)列
則以下算法當m趨向于無窮大的話,最差系數(shù)趨向于3
每次向相反方向搜索f(n)步

cjaizss

可以證明:
對于數(shù)列{f(n)}
f(n)滿足:
1.正項數(shù)列
2.嚴格單調(diào)增數(shù)列
3.{f(n+1)/f(n)}數(shù)列為無窮大數(shù)列
...
cjaizss 發(fā)表于 2010-02-28 17:34

  我們無論選擇f(n)=n!
還是選擇f(n)=2^(n^2)
還是f(n)=n^n
都有以上性質(zhì)
而選擇
f(n)=a^n這樣的形式,則不具備以上性質(zhì)

xyfree

出題的人是不是找不到數(shù)學模型對應(yīng)的實際應(yīng)用，就扯出了一道能無限延伸的墻？
redspider 發(fā)表于 2010-02-28 16:10

我倒覺得比較像是字符串里的搜索

xiaohangge

回復 25# cjaizss

3樓分析的后半部分是不是有問題？ 他計算的總步數(shù)s并不對吧？
   

xiaohangge

回復 25# cjaizss


    3樓分析的后半部分是不是有問題？ 他計算的總步數(shù)s并不對吧？

gtkmm

我求解了一類類似于sin函數(shù)的折線,
不太好畫, 我就不畫了.


從原點引出兩條射線, 使得折線在射線和Y軸之間的部分, 包含了折線函數(shù)的完整值域.
之后求射線的角度最大值.

解了一個表達式, 如下:   (a^2+1) / (a^2+a^2-1)+(a^3+a^3)+(a^2)的最大值
其中a是每次掉頭, 所要走的新路程對應(yīng)上一次的倍數(shù). 這個表達式的最大值,就是射線的角度, 也就是K值.


當a=2時取最大值, 此時角度為1/7

這是當門在距離N處, 正好走到很接近N時, 沒有發(fā)現(xiàn), 掉頭了, 向回走. 之后再回來時出現(xiàn)的.