主题:【原创】由一个简单的面试题想起的 -- 东方射日
共:💬43 🌺18
假设开始步长是 L,那么下一次步长应该是 L-1。因为你已经试过一次。
第一次如果破了:
f(n) = 1 + f(L-1);
第二次才破:
f(n) = 1 + f(L-1);
第三次才破:
f(n) = 1 + 1 + f(L-2);
所以:(当步长减到1时,你应该刚好走到终点)
L + (L-1) + .. + 1 = n - 1 (最后一步)
n=(L+1)*L/2 + 1
当n=100, L=13 (约等于)
补充:参照“走南闯北”给出的论文,我意识到这个结论是对最坏情况的(L=14)。平均情况还是得用上面的动态算法。
- 相关回复 上下关系8
🙂Google面试题 流云 字416 2007-03-06 16:53:02
🙂要澄清一下问题阿 林小筑 字1173 2007-03-06 14:51:41
🙂概率极小,与极大极小可能有不同解 孔老大 字524 2007-03-03 05:31:36
🙂楼主能不能说说是哪个公司的面试? octane99 字0 2007-03-02 23:17:12
🙂不太懂高等数学, 胡思乱想一下,第一个应该从第二层起 三力思 字48 2007-02-28 11:00:53