- 主题:一道谷歌面试题
蚂蚁每秒前进一格，和蚂蚁一动不动，其实没有什么区别。一开始选中一个位置，蚂蚁初始位置和所选位置的偏移为d，只要从零开始往正负两个方向对d进行搜索就可以了。从这个角度来说，即使蚂蚁每秒前进一百格，也一样会被找到
【 在 stub 的大作中提到: 】
:
: 有一个无限长的整数刻度的坐标轴，有一只蚂蚁在某一个整数刻度上，但是具体位置未知，现在蚂蚁每秒钟都会向正方向前进一格。你有一把手枪，每秒钟你能向坐标轴的某个刻度开一枪，之后只能知道打中还是没打中，请你设计一种开枪的策略，保证最终一定能打中这只蚂蚁。
#发自zSMTH@NOH-AN00
--
FROM 36.28.146.*
可以的。翻下前面的答案，很多人都提到过了
不确定的是蚂蚁的初始位置，其速度和方向都是确定的。打枪的速度可以根据蚂蚁速度进行调整，不会出现追不上的情况。假设蚂蚁的速度是v，时间步数是t(从0开始)，一个简单的搜索策略:
v * t + floor((t+1)/2) * (t % 2 ? 1 : -1)
【 在 imTaler 的大作中提到: 】
: 动不动区别大了。你的打枪扩张速度低于蚂蚁移动速度，就永远也追不上了。
:
--
FROM 115.192.115.*
换一个角度去想，搜索的不是蚂蚁的当前位置，而是蚂蚁的初始位置
如果硬要从追赶（移速快于蚂蚁）和被追赶（移速慢于蚂蚁）的角度去解释，所谓漏洞指的是追赶的时候节拍不对错过了和蚂蚁的交汇，那么后续蚂蚁肯定会慢于蚂蚁的分支击中。不信的话按照前面的公式，自己举个例子就明晰了
【 在 iMx @ [Programming] 的大作中提到: 】
:
: 能追上，肯定扫过的地方有空隙，漏洞是怎么解决的？
:
: 【 在 chrstl (某个庸人) 的大作中提到: 】
: : 可以的。翻下前面的答案，很多人都提到过了
#发自zSMTH@NOH-AN00
--
FROM 112.224.161.*