说有一个潜水艇，初始时位于数轴上的某个整数点，并沿着数轴以每秒整数个单位的速度做匀速运动（但你不知道具体的初始位置和移动速度是多少，移动方向也是未知的）。每一秒你都可以在某个整数点投放深水炸弹，如果此时潜艇正好在你放炸弹的位置，这个潜艇就被炸掉了。你是否有办法可以保证炸毁潜艇？
这是可以办到的。不管初始时潜水艇在哪儿，它的速度有多大，我总能在有限的时间里炸毁潜艇。假设潜艇的速度为 a ，初始位置为 b ，则在第 t 秒时它的位置就在 a*t + b 。把所有可能的有序数对 (a,b) 看作是平面直角坐标系上的整格点，每次考虑其中的一个点；假设第 i 秒考虑的点是 (a_i, b_i) ，那就在 a_i * i + b_i 处放一个炸弹。如此重复做下去，每次排除一种情况，直到击中目标为止。现在的问题就是，用怎样的顺序遍历平面上的所有格点才能保证每个 (a,b) 都会在有限的时间里访问到。这个方法就多了，比如从原点开始以一条螺旋线为路径一圈一圈地遍历周围越来越远的点。
这个问题展示了一些典型的数学思维在传统智力题方面的应用，它背后的数学方法非常深刻。
来源：http://www.reddit.com/r/math/comments/as2d5/sinking_the_submarine_a_puzzle/
sofa
沙发下面是…..
板凳下面是…..
地毯下面是。。。
地板下面是……
地下室下面是…..
(a,b)的有序对不是无限的吗？怎么能保证一定能取到呢？
是和哪个抓狐狸一样的类型吧
哪个→那个
是可数的步数内吧。。。。。。
前面几层的队形保持得真好，ORZ
对于这个问题，潜艇速率(不考虑方向)为V，那么路程就是S = V*t，炸弹的速率为v[t]，路程就是Sum[v[k],{k,1,t}] = f[t]*t，此时只要保证V*t == f[t]*t，也就是函数f[t] = V就可以。如果考虑方向，炸弹奇偶时间来回在两个方向折腾，保证f[t],f[2t]其中一个为V就行，求出这样的f[t]，考虑了5分钟，不知可行，望大侠赐教。。。
有点没看懂。题目中潜艇的速度和初始位置都是未知的，也就是说(a_i, b_i)也是未知的，那么答题人面对的是整个二维平面的点，因为你不知道潜艇是在这个平面上走过的哪一条线……
可数个可数集之并仍然是可数集
确实挺深刻的，呵呵
关键在于。。要想到第t秒的位置是a*t+b，而且（a,b）可以看作二维平面的点。。
不对吧 每一秒只能放一次炸弹 就表示每一行只能选一个点 那谈什么遍历啊
每秒钟投弹的位置对应于“这一秒”认定的a,b确定的位置。也就是说如果没打到就肯定不是这个a，b
不过没看出这个数学方法深刻在哪。。
M67牛无暇答疑，我就来凑凑热闹吧：
我们知道，潜艇的速度 a 和初始位置 b 都是一个固定的整数（显然是有限值），不随时间变化。另外，对每一个正整数时刻 t，潜艇所处位置必定是 a*t+b，所以如果我们在某一时刻 t0 选择的两个整数 (x,y) 恰好就是 (a,b)，那我们往 x*t0+y 位置投放的炸弹必定能击中潜艇。
好了，我们按 x+y 递增的方式去探索 (a,b) 那一点，即对于各相继的时刻 t=1,2,3,4,5,…，我们选择的 (x,y) 分别为
(0,1),(1,0), (0,2),(1,1),(2,0), …
那么我们可以断定，不管你给定的 (a,b) 是哪个点，由于它在我们的探索过程中保持不变，所以我们必定能在某个时刻 t，其探索到的点 (xt,yt） 就是 (a,b).
比如 (a,b) 为 (2,1)，那么我们来看看需要多少时间的探索才能够找到它：
(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1).
数一下，发现我们在时刻 t=8 便可击中潜艇。
就是说，按我们这种尝试方式，我们击中潜艇的时刻 t 是潜艇速度 a 及其初始位置 b 的函数： t=f(a,b).
我来凑凑热闹，嘻嘻
没错，螺旋线也差不多是最优的算法了。
这样当a或b充分大时，所需要的时间正比于π(a2+b2)
类似的推理，当潜水艇位于二维的平面时，必须每一时刻要一排的深水炸弹同时投放，才能在有限时间内炸到。
三维空间中的飞船，必须要一个面的攻击波了。
哈哈，我一直在跟踪这个主题的讨论。
事实上，依照类似的推理，当潜艇位于有限维向量空间上，并且初始位移和恒定速度都是该空间上的格点，那么仍然存在类似的算法，每一整数时刻投放一枚炸弹，能在有限时间内击中潜艇。
对于这个问题，我想讨论击中潜艇的最佳算法应该是一个比较有趣的方向。
嗯嗯，潜艇的位置，是个可数集，是整数点嘛。
一维二维三维都可以，只要保证每一秒探索的点是代表不同的潜艇初始位置就行了。就是把你的探索顺序（可数当然有顺序）乘上时间…
挺不错的！
啊～20楼让我恍然大悟，这个问题困扰了我好几天的说，多谢啦～～
对于不同的a、b，在t时刻潜艇是可以有相同的位置的，那么似乎存在比题中方法所需步数更少的方法……
哎呀，我完了
2007年某公司面试我的时候就是这道题……
I was recommended this website by my cousin. I
am not sure whether this post is written by him as no one else know such
detailed about my difficulty. You are incredible! Thanks!
Feel free to surf to my web blog :: vpn special coupon code 2024