小黑屋的一道数学题·解

Renee

这里开始放这题目的解：
http://bbs.islga.org/read-htm-tid-37671.html


Part 1:

我会尽量把整个过程讲的浅显易懂一些，因此我把整个讲解过程分成三段，而在回顾我们那个问题前，我们先来看一个稍微简单一些的问题：

（注意这个问题是我临时想的，你骨骼不到）

假设有一个变量n，它属于一个十分特别的变量类型Hdl，这种变量类型有以下特性：

1]Hdl类型变量相互之间只有一种操作：相等比较。

比如表达式(n==n1)的结果只有两种可能，真或者假。(n1也属于n所属的变量类型)。

2]然后这个变量类型无法转换成其余任何类型，只有整数int可以单向地转换为它，我们就假定转换函数为I2H(int)。

3]对于任何给定的Hdl类型变量，它必有一个值，而且这个值必定是一个整数（但是没有任何官方函数可以让你把它转换成一个整数，你也无法直接将Hdl的值打印出来），也就是说Hdl和int之间是一一对应的关系。

然后问题来了：

对于一个给定的，值未知的n(类型为Hdl),我们如何完成一个自定义函数H2I(Hdl)，可以得到n中所存放的整数的值？

也许你能想到——用遍历：

我们可以做一个循环来对整型变量i遍历所有整数，然后将其I2H并将结果与n相比较。直到n==I2H(i)时跳出循环。

--------------------------

很普通的解决方案，那这道题得到结果了么？没有？

紧接而来的问题是：如何遍历？

对于整型变量i，遍历所有整数的方案有：

1]从负无穷遍历到正无穷(之间的整数)

2]先遍历所有正整数，再遍历所有负整数

3]0，1，-1，2，-2……这样的遍历法。

4]其余遍历方式不举。

是不是我可以随便选一个呢？


这里的关键就是，遍历法1和2都是行不通的。

对于方案1，因为负无穷不是一个数，所以你连第一个假设值设为几都不知道，这个算法开始都开始不了，你总不能"set i=负无穷大"

对于方案2，如果n里所保存的数是一个负数，那么你一辈子也遍历不到了。因为你得先遍历所有正整数，而正整数有无穷多个。 那么H2I()这个函数就陷入死循环了。

而方案3才是可行的。因为无论n的值是几，我总能在2|n|+1次内遍历到它。n必然是有有限整数，那么2|n|+1必然也是个有限整数。

不过方案3并非唯一方案，以任何一个整数x为中心，我们都能用x,x+1,x-1……的方式遍历到任意给定的n。


很不错吧？虽然n的取值范围是无穷多个，本该有无穷个选择。但是我们用方案3（或类似方案），把问题从无穷多个选择变成了，n的简单一次方程，而n是一个整数，它是不可能无穷大的。因此找到n的次数也成了一个整数。于是函数H2I()里的循环体必定会有出口。

Renee

Part 2

回到那个潜艇的wt~~

也许大家会想，这潜艇的初始位置都不知道，而且它的位置每时每刻都在变。我怎么才能确保炸中啊？

思路如下：

反正你炸弹每秒扔一次对不对？潜艇每秒前进整数格对不对？潜艇初始位置也是整数点对不对？那么你扔炸弹的位置也必然是在所有整数里选。

但是“所有整数”的容量还是没有比“所有实数”的前景更光明，都是无穷多个，因此要进一步考虑。

假设我们设潜艇初始位置为x，速度为y，而我们扔炸弹的时间为t(x和y和t都属于整数，其中t是正整数)。那么我们潜艇的位置n必然是：

n=y*t+x

对吧？如果我们正好在t时刻往数轴上的点n投掷炸弹，那么就中了。好了这里有几个未知数呢？三个？要注意：t你是知道的啊。你第一次尝试的时候t是1，第二次尝试的时候t是2。所以t不是未知量，而是由你尝试的次数决定的，你每次尝试的时候必然知道尝试了几次，那么t也是确定的。

那么要得到n，其实只有2个未知数(x,y)。因为(x,y)在t=0的时候就已经确定了，不会随着t的改变而改变。


所以整个问题只需要简化为对整数对(x,y)的遍历就可以了。 如果写成程序语言，我们只要在循环体内对x和y进行遍历，至于t，将其初值设为0，然后每次循环+1就行了。

那么我们在P3讨论x,y的遍历。

Renee

Part 3

知道了这题目本质上可以化为对整数对(x,y)的遍历后，我们是不是可以用P1的方案对x和y进行遍历了啊。

然后这里存在第三个问题：

如何遍历？

你也许会反问说：“这问题不是问过了么？就按照P1的方案不就好了？”

但是在这里，新的关键点在于x和y是互不相关的两个独立变量。如果你使用传统的遍历方式：固定一个值，遍历另一个值->然后固定那个值变动一次，遍历另一个值……即从左到右从上到下依次遍历
(0,0),(0,1),(0,-1),(0,2),(0,-2)……
(1,0),(1,1),(1,-1),(1,2),(1,-2)……
……
这样的方式

依然是行不通的。因为y有无限多种可能。 你遍历完第一行需要无限次，x=1的那行你永远也取不到。

因此这里套用P1的思路是对的，但是不能纯粹照搬，要取P1的方案的本质。P1的方案本质是啥？——以一个特定位置为中心，对称地取值。


可行方案有很多，这里举两个例子：

比如将(x,y)想象成一个直角坐标系，不过可取的点只有那些整数对的点。那么我们就可以随便取一个点作为基点(方便起见，我们取0,0)。然后之后的每次都慢慢以其为中心，以画同心圆或者同心方的方式取值即可,以下就是一种可行的取值顺序
(0,0)
(-1,-1)
(-1,0)
(-1,1)
(1,-1)
(1,0)
(1,1)
(-2,-2)
(-2,-1)
(-2,0)
(-2,1)
(-2,-2)
(2,-2)
(2,-1)
(2,0)
(2,1)
(2,2)
……

这样，我们就得以将遍历次数t(

重申一遍，在这个算法里遍历次数就是时间t,别忘了

)变成直接由x和y决定的函数了。而x,y这两个值必定是有穷整数，那么这个算法里的遍历次数t就必然也是个有穷整数。

于是再一次的，我们把有无限多种取值可能的整数对(x,y)问题变成了遍历次数为一个有限的整数的问题。

算法怎么写？我们可以采用loop until的方式

这里我们把(x,y)作为我们假设的值，而未知函数GetN(int t)为t时刻潜艇的位置，i为t时该扔的位置，并假设，GetN(int t)返回类型为Hdl，无法直接获得它的值，只能进行比较操作。

t=0
loop
t=t+1
取下一个(x,y)对
i=y*t+x
until (GetN(t)==I2H(i))




于是该题解决。

进一步的思考：

其实按照P1到P3的思路，大家很快就会发现，其实有几个变量根本无所谓，如果这个题目是三个未知数组成的整数对，我们还是可以用有限次遍历来得到给定值——无非把同心方方案改成了同心正方体而已。

那么3个、4个、5个、乃至N个，结果都是一样的。

发这个题目一是为了娱乐，也是为了开拓大家思路，简单地来说，就是要求你想出在N维无限集里靠有限次遍历来获得给定元素的方案。

Renee

引用第3楼寂寞的季节于2010-01-30 20:01发表的  :
貌似不能成立啊……如果是数学的话~我可以有些假设~程序我就不做什么了~

看来你连p1都没看明白。因此你好好看看吧。我现在开始写p2。

血戮魔动冰

………………膜拜~

Renee

引用第6楼寂寞的季节于2010-01-30 20:09发表的  :
哦~那个假设在每判断一次内潜艇移动2的实数距离~方向为正方向起始点可以在任意大于0的地方~那不是永远判断跟不上潜艇了？

你在说什么呢，P1的解法仅限于P1的题目，我写出它是为了启发对原题的解法，而不是叫你照搬这个去解原题。

现在P2出来了，结合P1和P2的话，你有思路了么？

现在我开始写P3

gason

呃，没想到这背后还有故事……原来头目是把handle当作潜艇了呀……

不过如果用哈希表里头的GetHandleId可不可以直接击中潜艇呢？

Renee

引用第9楼gason于2010-01-30 20:20发表的  :
呃，没想到这背后还有故事……原来头目是把handle当作潜艇了呀……

不过如果用哈希表里头的GetHandleId可不可以直接击中潜艇呢？

但是你注意题目中说的，没有官方的hdl->int函数。所以GetHandleId()不能用。

而且我这里说的和jass也不同。这种算法要求函数的语句执行数量没有上限，而jass有(虽然可以用调用触发器来规避)。另外，实际操作中并没有负数handle的对象，而我这题中的Hdl却可以是负数。

gason

Sorry,我刚看完P1,以为头目要发明新的Jass技术了呢……

Renee

于是P1-P3都写完了~~大家若还有什么不理解的地方可以提问~~

vivid

呀，原来可以变成数列了……

Conflux

为头目的P3附图...

Renee

为了方便理解，我把P3算法里的潜艇位置也改成Hdl类型了，t时刻潜艇位置由未知函数GetN(int t)决定，其返回类型为Hdl，以明确其只能比较无法读取的特性。

血戮魔动冰

已经明白了。
核心就是如何遍历无穷吧……

Conflux

核心应该是怎么证明一个集合可数...

vivid

因为不懂程序设计思路不懂数学，所以我没有任何问题……

木有鱼丸

强大的头目……
五体投地～
Orz

Renee

另外，我们可以在这里实际地计算下原点同心方算法中(x,y)整数对被遍历到所需的次数t。

计算方法：

对于没有规定在方形的边上取值顺序的普遍结论，我们就可以取|x|和|y|中较大的值M,以原点为中心，2M为边长画正方形。那么这个正方形里面(包括四条边上)所有的整数对的点子的和，就是我们需要尝试的次数t的最大值。

——想想就知道t肯定是有限整数了吧？方形里的点子数总是可数的吧？

t最大=(2M+1)^2        M=MAX(|x|,|y|)

M为正整数，(2M+1)必然也是正整数，而t为正整数(2M+1)的平方，必然也是个正整数。

而且随着每个方形的边上取点顺序的不同，实际次数t会小于等于这个值，但是大于比它小一圈的方形里的点子数。

故有
(2M-1)^2<t<=(2M+1)^2    M=MAX(|x|,|y|)

cccty1l

话虽然这么说。。。
我想知道我炸掉潜艇一共走了多少路呢？

Conflux

这个... 走了多少路，和我们找到并炸掉它花掉的时间有关。