请教一道看似简单，却不平凡的算法题！

xyfree

之前发的还在修改中。

emacsnw

这个貌似是我四年前发的一道老题。怎么被挖出来了。:wink:

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

ps：该公司是Google.

redspider

出题的人是不是找不到数学模型对应的实际应用，就扯出了一道能无限延伸的墙？

cjaizss

可以证明:
对于数列{f(n)}
f(n)满足:
1.正项数列
2.严格单调增数列
3.{f(n+1)/f(n)}数列为无穷大数列
则以下算法当m趋向于无穷大的话,最差系数趋向于3
每次向相反方向搜索f(n)步

cjaizss

可以证明:
对于数列{f(n)}
f(n)满足:
1.正项数列
2.严格单调增数列
3.{f(n+1)/f(n)}数列为无穷大数列
...
cjaizss 发表于 2010-02-28 17:34

  我们无论选择f(n)=n!
还是选择f(n)=2^(n^2)
还是f(n)=n^n
都有以上性质
而选择
f(n)=a^n这样的形式,则不具备以上性质

xyfree

出题的人是不是找不到数学模型对应的实际应用，就扯出了一道能无限延伸的墙？
redspider 发表于 2010-02-28 16:10

我倒觉得比较像是字符串里的搜索

xiaohangge

回复 25# cjaizss

3楼分析的后半部分是不是有问题？ 他计算的总步数s并不对吧？
   

xiaohangge

回复 25# cjaizss


    3楼分析的后半部分是不是有问题？ 他计算的总步数s并不对吧？

gtkmm

我求解了一类类似于sin函数的折线,
不太好画, 我就不画了.


从原点引出两条射线, 使得折线在射线和Y轴之间的部分, 包含了折线函数的完整值域.
之后求射线的角度最大值.

解了一个表达式, 如下:   (a^2+1) / (a^2+a^2-1)+(a^3+a^3)+(a^2)的最大值
其中a是每次掉头, 所要走的新路程对应上一次的倍数. 这个表达式的最大值,就是射线的角度, 也就是K值.


当a=2时取最大值, 此时角度为1/7

这是当门在距离N处, 正好走到很接近N时, 没有发现, 掉头了, 向回走. 之后再回来时出现的.