- 主题:一道谷歌面试题
初始-1完美躲过,,,,你们都不验算的吗?
【 在 Richbunny 的大作中提到: 】
: 第一枪打0
: 第二枪打2
: 第三枪打0
: ...................
--
FROM 124.126.7.*
第一反应是蚂蚁轨迹是一条起点未定,斜率为1的线,手枪射击实际是一条任意形状的曲线,然后什么形状的曲线会跟蚂蚁的射线有交点。
【 在 stub 的大作中提到: 】
: 有一个无限长的整数刻度的坐标轴,有一只蚂蚁在某一个整数刻度上,但是具体位置未知,现在蚂蚁每秒钟都会向正方向前进一格。你有一把手枪,每秒钟你能向坐标轴的某个刻度开一枪,之后只能知道打中还是没打中,请你设计一种开枪的策略,保证最终一定能打中这只蚂蚁。
--
FROM 213.95.148.*
想想蚂蚁从2出发,你打不中的
【 在 Richbunny 的大作中提到: 】
: 第一枪打0
: 第二枪打2
: 第三枪打0
: ...................
--
FROM 213.95.148.*
直接沿x=0折叠平面,那么蚂蚁必然在右侧
【 在 mafama 的大作中提到: 】
: 放在二维坐标轴上,蚂蚁的轨迹实际上是一根斜率为1 ,截距为任意整数的射线,题目的要求可以理解为,我们需要构建一个函数,使其与蚂蚁的函数在某个整数位上相交。由于蚂蚁初始点任意,所以无论怎么选取初始点,都会有两种情况:初始蚂蚁在左面,和初始蚂蚁在右面。因此需要构筑一个区间,区间上沿斜率大于一,区间下沿斜率小于一,这样,不管蚂蚁在左还是在右,都可以相交。此外,函数构造要保证不会正好错过交点。
: 设蚂蚁初始点为A,步数为X,则蚂蚁函数为Y=A+X;
: 构建一个函数,上沿为:当X为奇数,Y=(3X+1)/2,斜率大于1;
: ...................
--
FROM 213.95.148.*
赞总结,只是1和4是等价的。
【 在 raelag 的大作中提到: 】
: 总结版上思路,一共有4种:
: 1. 反推初始位置法,每打一枪对应一个初始位置,逐步检验。
: 2. 函数法,蚂蚁的走势是一条斜率45°直线,需要用一条斜率比它大和和一条斜率比它
: ...................
--
FROM 213.95.148.*
这里的左右是指题中一维数轴上的左右,转化为二维坐标系的函数图像的话,实际是上下
【 在 moudy 的大作中提到: 】
: 直接沿x=0折叠平面,那么蚂蚁必然在右侧
--
FROM 117.65.188.*
左打一枪油大一枪,次数无穷多,必然击中
【 在 stub 的大作中提到: 】
: 有一个无限长的整数刻度的坐标轴,有一只蚂蚁在某一个整数刻度上,但是具体位置未知,现在蚂蚁每秒钟都会向正方向前进一格。你有一把手枪,每秒钟你能向坐标轴的某个刻度开一枪,之后只能知道打中还是没打中,请你设计一种开枪的策略,保证最终一定能打中这只蚂蚁。
--
FROM 221.218.139.*
标准答案:蚁蚁那么可爱,怎么能用枪去打呢
【 在 stub 的大作中提到: 】
: 有一个无限长的整数刻度的坐标轴,有一只蚂蚁在某一个整数刻度上,但是具体位置未知,现在蚂蚁每秒钟都会向正方向前进一格。你有一把手枪,每秒钟你能向坐标轴的某个刻度开一枪,之后只能知道打中还是没打中,请你设计一种开枪的策略,保证最终一定能打中这只蚂蚁。
--
FROM 123.185.111.*
人家无限,你还正负1...
【 在 iMx (围城) 的大作中提到: 】
: 从0刻度往1方向开一枪,往-1方向再开一枪
:
:
: 【 在 stub (stub) 的大作中提到: 】
--
FROM 221.223.192.*
这个题给我的感觉和判断一个链表是否有环是一类问题,解法也是相似的。
【 在 stub (stub) 的大作中提到: 】
: 有一个无限长的整数刻度的坐标轴,有一只蚂蚁在某一个整数刻度上,但是具体位置未知,现在蚂蚁每秒钟都会向正方向前进一格。你有一把手枪,每秒钟你能向坐标轴的某个刻度开一枪,之后只能知道打中还是没打中,请你设计一种开枪的策略,保证最终一定能打中这只蚂蚁。
--
FROM 59.109.219.*