小黑屋的一道数学题·解

eff · 发表于 2010-1-30 23:03:42

我表示完全看不懂为什么要用这种东西。。哈希不是挺好的莫

Renee · 发表于 2010-1-30 23:15:44

你以为这个是jass？

cccty1l · 发表于 2010-1-30 23:17:28

eff大叔，你这样恶意卖萌是不对滴- -!

eff · 发表于 2010-1-30 23:36:27

只是说为什么需要这样的一个算法。。。。拿来解决什么问题呢。。

- 至少我想不出计算机里面为什么需要这种算法

Renee · 发表于 2010-1-30 23:41:02

拿来解决的问题不就在你眼前么，潜艇扔炸弹问题呗。

难道你小学时候做数学题应用题还真考虑过拿来解决什么现实问题了？

eff · 发表于 2010-1-30 23:50:25

小学时候碰到的认为没有啥意义的问题都丢掉了。。事实证明后来也在没用过。。。
（所以咱从来都不是好学生）

緋桜 · 发表于 2010-1-31 01:23:13

学习了...
数学什么的最讨厌了...

(由此引发了再次对四维宇宙的思考,唉)

louter · 发表于 2010-1-31 10:26:33

头目我没看懂啊，如果我a1取10000，d取1，那不管是P1还是P3当n为一确定常数时不都是永远取不到当前an为多少么，因为那两种的变化趋势都小于或等于an

foodszhu · 发表于 2010-1-31 11:06:30

相当不错的问题啊。。。。整数的离散性。。。代表了他的有限范围的有穷性。。。。。再加上方向。。。速度实际上是一定的。。。。在每一个t内。。。范围其实上已经确定了。。。或许何以看作一个很简单的追击问题。。。一个速度恒定。。。方向未知。。N个加速度定值。。方向一定。。。。最后必然有一人会追上。。。把这个问题最后抽象成N维无限数组的有限次遍历算法。。。。果然很强呢。。。。
只是不知道最简的算法是否存在。。。。若存在又是什么？？

疯人￠衰人 · 发表于 2010-1-31 11:47:23

话说
我没看懂题目
也没看懂答案

首先是题目
匀速运动：是不是匀速直线运动呢？
每秒投放：那么，也就是说潜艇每移动一次，也只能投一次炸弹？如果只是一次投放，仅以概率学上来看，命中是小概率事件，基本上可以认为是不可能的。原因如下，如果潜艇的活动在一个有限范围内，比如（|x|<n,|Y|<n），因为坐标都是整数，那么对于潜艇的一个确定位置，如果炸弹的位置概率是均匀分布的，那么命中的概率为1/n/n。
因为头目的条件是无穷范围内，所以命中概率是无穷的平方分之一，即0.
一个概率为无穷的平方分之一的概率进行有限次实验，命题不可能实现，也就是炸不到

vivid · 发表于 2010-1-31 11:48:13

在数轴上不是直线运动是什么……

Conflux · 发表于 2010-1-31 12:10:11

咱要丢的炸弹是直接丢在潜艇上的，不是丢在那里等着被潜艇撞。

潜艇所在的位置是可以通过
·假设的初始位置
·假设的速度
·假设的方向
·经过的时间
这4个参数确定的，其中时间是一个自增的变量，初始位置的取值范围是所有整数，有方向的速度取值范围也是所有整数。
于是问题就被简化为，如何遍历一个由初始位置和速度组成的二维整数空间。

http://bbs.islga.org/read.php?tid=37671&page=2#434740

foodszhu · 发表于 2010-1-31 13:29:59

即对应任意一组（x,y)...都有n=x+ty......t是自变量。。。每次通过是否击中来判断n是否为所求。。。即这组（x,y）是否满足。。。。关系
当这组（x,y)...均不是无限大（小）时。。。。需要实验的（x,y）组数也是有限的。。。。应该是这样理解吧。。。组数也就是4xy。。。。
。。。。倒是在想能不能化简一下遍历算法。。。比如说当....t=1时。。。n不等于1（即没击中）那么x+y不等于1。。。之类的就可以把很多种情况排出了。。。。依次类推这样当MAX(|x|,|y|)很大时。。。。组数就要比楼主大人算的小很多了。。。。。可惜这个方法还是要和大人的方法结合。。而且说实话。。运算次数没有改变。。甚至更麻烦了。。下午想想有没有其他的更简单的遍历

疯人￠衰人 · 发表于 2010-1-31 13:41:22

引用第35楼Conflux于2010-01-31 12:10发表的回 33楼(疯人￠衰人) 的帖子 :
咱要丢的炸弹是直接丢在潜艇上的，不是丢在那里等着被潜艇撞。
潜艇所在的位置是可以通过
·假设的初始位置
·假设的速度
.......

我的问题就是
如果你遍历A[ i]，寻找a=A[ i]
那么如果你遍历每个A[ i]时,a也变化了
那么你怎么能遍历出结果?
而且这题是问证明有限步
这个怎么证明？
我认为可以有限步实现
就是概率不为0

Renee · 发表于 2010-1-31 13:59:54

证明必定是有限步可以看20楼~~

因为t就是步数~~

Renee · 发表于 2010-1-31 14:03:53

引用第31楼louter于2010-01-31 10:26发表的 :
头目我没看懂啊，如果我a1取10000，d取1，那不管是P1还是P3当n为一确定常数时不都是永远取不到当前an为多少么，因为那两种的变化趋势都小于或等于an

我不知道你说的a1 d an都是啥~~我的p1到p3都没出现过这样的变量名~~

Renee · 发表于 2010-1-31 14:05:44

引用第37楼疯人￠衰人于2010-01-31 13:41发表的 Re:回 33楼(疯人￠衰人) 的帖子 :

我的问题就是
如果你遍历A[ i]，寻找a=A[ i]
那么如果你遍历每个A[ i]时,a也变化了
那么你怎么能遍历出结果?
.......

你是没看明白~~我遍历的根本不是潜艇位置~~而是潜艇的速度和初始位置~~这两个值是不会改变的~~

たこルカ · 发表于 2010-1-31 15:01:53

表示8只触手不够用

疯人￠衰人 · 发表于 2010-1-31 15:22:58

引用第40楼Renee于2010-01-31 14:05发表的 Re:Re:回 33楼(疯人￠衰人) 的帖子 :

你是没看明白~~我遍历的根本不是潜艇位置~~而是潜艇的速度和初始位置~~这两个值是不会改变的~~

确实是没有看明白啊
不过初始位置也是在无限范围内的
能遍历出来么？

Conflux · 发表于 2010-1-31 15:35:41

初始位置是一个整数不论多大总会轮到它的
未命名.GIF

		自动登录	找回密码
密码			点一下

小黑屋的一道数学题·解

回 33楼(疯人￠衰人) 的帖子

Re:回 33楼(疯人￠衰人) 的帖子

Re:Re:回 33楼(疯人￠衰人) 的帖子

Re:Re:Re:回 33楼(疯人￠衰人) 的帖子