我们把一个边长为2的正方形划分成4个小正方形,每个小正方形里作一个内切圆,然后在原来的大正方形中间作一个同时外切于这4个圆的小圆(红色标注)。我们把这个小圆叫做“中心圆”。你怎么来求这个中心圆的半径?
仔细观察其中一个小正方形,思路就出来了:红色的中心圆变成了一个90度扇形,它的中心位于单位正方形的一角,并且外切于直径为1的圆。可以看到扇形半径加上圆的半径等于单位正方形对角线的一半,这样我们就得出,中心圆的半径等于(sqrt(2)-1)/2。
对于一个立方体同样如此。我们把立方体切成8个小立方体,得到的8个球体中间夹住的那个中心球半径就应该为(sqrt(3)-1)/2。你会发现一个惊人的事实,在超立方体中,位于16个四维球体间的中心球半径为(sqrt(4)-1)/2 = 1/2,它竟然与那16个小球一样大。真正可怕的事情发生在九维立方体中,此时的九维中心球半径为(sqrt(9)-1)/2 = 1,竟然内切于最初的九维立方体!而到了十维空间后,中心球的直径将超过十维立方体的边长,这个中心球将突破立方体的边界!被围在里面的中心球居然比原来的N维立方体还大,这显然违反了大多数人的直觉;如果你能想象出这个画面来,你就牛B了。科幻小说中把对十维空间的感知能力作为文明发达程度的标准,除了一些相关的宇宙模型外,这可能也是其中一个原因吧。
几何
神奇的分形艺术(一):无限长的曲线可能围住一块有限的面积

很多东西都是吹神了的,其中麦田圈之谜相当引人注目。上个世纪里人们时不时能听见某个农民早晨醒了到麦田地一看立马吓得屁滚尿流的故事。上面这幅图就是97年在英国Silbury山上发现的麦田圈,看上去大致上是一个雪花形状。你或许会觉得这个图形很好看。看了下面的文字后,你会发现这个图形远远不是“好看”可以概括的,它的背后还有很多东西。
在说明什么是分形艺术前,我们先按照下面的方法构造一个图形。看下图,首先画一个线段,然后把它平分成三段,去掉中间那一段并用两条等长的线段代替。这样,原来的一条线段就变成了四条小的线段。用相同的方法把每一条小的线段的中间三分之一替换为等边三角形的两边,得到了16条更小的线段。然后继续对16条线段进行相同的操作,并无限地迭代下去。下图是这个图形前五次迭代的过程,可以看到这样的分辨率下已经不能显示出第五次迭代后图形的所有细节了。这样的图形可以用Logo语言很轻松地画出来。

你可能注意到一个有趣的事实:整个线条的长度每一次都变成了原来的4/3。如果最初的线段长为一个单位,那么第一次操作后总长度变成了4/3,第二次操作后总长增加到16/9,第n次操作后长度为(4/3)^n。毫无疑问,操作无限进行下去,这条曲线将达到无限长。难以置信的是这条无限长的曲线却“始终只有那么大”。
当把三条这样的曲线头尾相接组成一个封闭图形时,有趣的事情发生了。这个雪花一样的图形有着无限长的边界,但是它的总面积却是有限的。换句话说,无限长的曲线围住了一块有限的面积。有人可能会问为什么面积是有限的。虽然从上面的图上看结论很显然,但这里我们还是要给出一个简单的证明。三条曲线中每一条的第n次迭代前有4^(n-1)个长为(1/3)^(n-1)的线段,迭代后多出的面积为4^(n-1)个边长为(1/3)^n的等边三角形。把4^(n-1)扩大到4^n,再把所有边长为(1/3)^n的等边三角形扩大为同样边长的正方形,总面积仍是有限的,因为无穷级数Σ4^n/9^n显然收敛。这个神奇的雪花图形叫做Koch雪花,其中那条无限长的曲线就叫做Koch曲线。他是由瑞典数学家Helge von Koch最先提出来的。本文最开头提到的麦田圈图形显然是想描绘Koch雪花。
分形这一课题提出的时间比较晚。Koch曲线于1904年提出,是最早提出的分形图形之一。我们仔细观察一下这条特别的曲线。它有一个很强的特点:你可以把它分成若干部分,每一个部分都和原来一样(只是大小不同)。这样的图形叫做“自相似”图形(self-similar),它是分形图形(fractal)最主要的特征。自相似往往都和递归、无穷之类的东西联系在一起。比如,自相似图形往往是用递归法构造出来的,可以无限地分解下去。一条Koch曲线中包含有无数大小不同的Koch曲线。你可以对这条曲线的尖端部分不断放大,但你所看到的始终和最开始一样。它的复杂性不随尺度减小而消失。另外值得一提的是,这条曲线是一条连续的,但处处不光滑(不可微)的曲线。曲线上的任何一个点都是尖点。
分形图形有一种特殊的计算维度的方法。我们可以看到,在有限空间内就可以达到无限长的分形曲线似乎已经超越了一维的境界,但说它是二维图形又还不够。Hausdorff维度就是专门用来对付这种分形图形的。简单地说,Hausdorff维度描述分形图形中整个图形的大小与一维大小的关系。比如,正方形是一个分形图形,因为它可以分成四个一模一样的小正方形,每一个小正方形的边长都是原来的1/2。当然,你也可以把正方形分成9个边长为1/3的小正方形。事实上,一个正方形可以分割为a^2个边长为1/a的小正方形。那个指数2就是正方形的维度。矩形、三角形都是一样,给你a^2个同样的形状才能拼成一个边长为a倍的相似形,因此它们都是二维的。我们把这里的“边长”理解为一维上的长度,那个1/a则是两个相似形的相似比。如果一个自相似形包含自身N份,每一份的一维大小都是原来的1/s,则这个相似形的Hausdorff维度为log(N)/log(s)。一个立方体可以分成8份,每一份的一维长度都是原来的一半,因此立方体的维度为log(8)/log(2)=3。同样地,一个Koch曲线包含四个小Koch曲线,大小两个Koch曲线的相似比为1/3,因此Koch曲线的Hausdorff维度为log(4)/log(3)。它约等于1.26,是一个介于1和2之间的实数。
我们常说分形图形是一门艺术。把不同大小的Koch雪花拼接起来可以得到很多美丽的图形。如果有MM看了前面的文字一句也不懂,下面这些图片或许会让你眼前一亮。
放图前留下一句话:
Matrix67原创
转贴请注明出处


借用点其它的东西,你或许可以三等分角
大家都知道,我们永远不可能尺规三等分任意角。借助一些其它的工具是可以办到的,即使所借助的东西“微不足道”,“几乎可以不算”。下面提供四种比较简单的方法。
ONE~~~~~~~~~
至今仍有不少人认为这种方法可以推翻“三等分角不可能”的结论。而事实上,这种方法仍然算借用了外物。
尺规不能三等分角,但可以三等分圆(自己试)。也就是说,只用直尺和圆规可以画出120度的角来。现在给你一个任意角,那么你可以把它对应的扇形卷成一个圆锥,三等分这个圆锥底面的圆。还原成扇形后,你会看到这个角所对应的圆弧已经被平分为三份了。
TWO~~~~~~~~~
把要三等分的角AOB放在圆中,作为圆心角。从B出发作射线交圆于D,交AO延长线于C,当CD等于圆的半径时角ACB就是角AOB的1/3。你可以试着自己证明一下。
证明:设∠DCO=x。由CD=DO知∠DCO=∠DOC,于是∠DOC=x,进而∠BDO=2x。由DO=BO知∠BDO=∠DBO,于是∠DBO=2x,进而∠AOB=∠ACB+∠DBO=3x。
结论是正确的,可惜如果不在尺子上作标记的话图是作不出来的。
THREE~~~~~~~
我们要三等分角BAC。作CD垂直于AB,垂足为D。作CE平行于AB。AE交CD于F。适当移动E的位置(仍然保持CE//AB),当EF=2AC时,∠EAB=1/3∠CAB。
证明很简单:找出EF的中点后,于是EM=FM=CM=AC,那么∠CAM=∠CMA=2∠AEC,又因为CE//AB,所以最终可得∠CAE=2∠EAB,也即∠EAB=1/3∠CAB。和方法二一样,尺子上面没有刻度的话是作不出这个图的。
FOUR~~~~~~~~
如果你手上有一张纸的话,你可以用折纸的方法三等分角。
把角XAY(蓝色标明)放在纸的一个直角上,AY靠着纸的边缘。在纸的另一直角边上确定两点P和Q使得AP=PQ,过这两个点分别作平行于AY的直线。现在,把纸折起来,让Q点落在AX上,A点落在过P的那条平行线上,那么A和P的落点就确定了三等分线的位置(红色线段)。怎么证明呢?
证明:为了便于叙述,我们把A、P、Q的落点分别命名为A'、P'、Q',折痕的端点分别为B和C。过A'作A'D垂直于AY。∠AA'D = 90°- ∠A'AD = ∠BAA'。又AB=A'B,于是∠BAA'=∠BA'A。加上A'D=PA=P'A',AA'是公共边,足以说明△AA'P'≌△AA'D (SAS)。这样,∠AP'A'和∠AP'Q'都是直角。又注意到AP=PQ即A'P'=P'Q',于是△AP'A'≌△AP'Q'。以A为顶点的三个直角三角形全等,也即对应的三个角相等。
做人要厚道
转贴请注明出处
趣题:哪条线段最长,哪条线段最短

最近cut-the-knot上的一些新东西比较有意思。今天下午没事干,我翻译一些我觉得好玩的和大家分享。
上图显示了用直线将一个四分之一圆分为面积相等的两份的三种方法。这三条线段中,哪一个最长,哪一个最短?
答案在下面。

第一种方案的线段长度等于圆的半径;
第二种方案的线段长度显然大于半径,因为红色线段和半径长度相等,但它还不足以平分扇形面积。
第三种方案的线段长度显然小于半径。
因此,线段长度为②>①>③。
什么是离散化?
如果说今年这时候OIBH问得最多的问题是二分图,那么去年这时候问得最多的算是离散化了。对于“什么是离散化”,搜索帖子你会发现有各种说法,比如“排序后处理”、“对坐标的近似处理”等等。哪个是对的呢?哪个都对。关键在于,这需要一些例子和不少的讲解才能完全解释清楚。
离散化是程序设计中一个非常常用的技巧,它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。下面我将用三个例子说明,如何运用离散化改进一个低效的,甚至根本不可能实现的算法。
《算法艺术与信息学竞赛》中的计算几何部分,黄亮举了一个经典的例子,我认为很适合用来介绍离散化思想。这个问题是UVA10173(http://acm.uva.es/p/v101/10173.html),题目意思很简单,给定平面上n个点的坐标,求能够覆盖所有这些点的最小矩形面积。这个问题难就难在,这个矩形可以倾斜放置(边不必平行于坐标轴)。
这里的倾斜放置很不好处理,因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α,那么答案就很简单了:矩形面积最小时四条边一定都挨着某个点。也就是说,四条边的斜率已经都知道了的话,只需要让这些边从外面不断逼近这个点集直到碰到了某个点。你不必知道这个具体应该怎么实现,只需要理解这可以通过某种方法计算出来,毕竟我们的重点在下面的过程。
我们的算法很显然了:枚举矩形的倾角,对于每一个倾角,我们都能计算出最小的矩形面积,最后取一个最小值。
这个算法是否是正确的呢?我们不能说它是否正确,因为它根本不可能实现。矩形的倾角是一个实数,它有无数种可能,你永远不可能枚举每一种情况。我们说,矩形的倾角是一个“连续的”变量,它是我们无法枚举这个倾角的根本原因。我们需要一种方法,把这个“连续的”变量变成一个一个的值,变成一个“离散的”变量。这个过程也就是所谓的离散化。
我们可以证明,最小面积的矩形不但要求四条边上都有一个点,而且还要求至少一条边上有两个或两个以上的点。试想,如果每条边上都只有一个点,则我们总可以把这个矩形旋转一点使得这个矩形变“松”,从而有余地得到更小的矩形。于是我们发现,矩形的某条边的斜率必然与某两点的连线相同。如果我们计算出了所有过两点的直线的倾角,那么α的取值只有可能是这些倾角或它减去90度后的角(直线按“”方向倾斜时)这么C(n,2)种。我们说,这个“倾角”已经被我们 “离散化”了。虽然这个算法仍然有优化的余地,但此时我们已经达到了本文开头所说的目的。
对于某些坐标虽然已经是整数(已经是离散的了)但范围极大的问题,我们也可以用离散化的思想缩小这个规模。最近搞模拟赛Vijos似乎火了一把,我就拿两道Vijos的题开刀。
VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永远是离散化的经典问题。大意是给定平面上的n个矩形(坐标为整数,矩形与矩形之间可能有重叠的部分),求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”(把矩形所在的位置填上True)。可惜这个想法在这里有些问题,因为这个题目中坐标范围相当大(坐标范围为-10^8到10^8之间的整数)。但我们发现,矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值, 100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说,实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面,省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数,于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标(或纵坐标)进行一次排序并映射为1到2n的整数,同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。
最后简单讲一下计算几何以外的一个运用实例(实质仍然是坐标的离散)。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id=1238)中,标程开了一个与时间范围一样大的数组来储存时间段的位置。这种方法在空间上来看十分危险。一旦时间取值范围再大一点,盲目的空间开销将导致Memory Limit Exceeded。我们完全可以采用离散化避免这种情况。我们对所有给出的时间坐标进行一次排序,然后同样用时间段的开始点和结束点来计算每个时刻的游戏数,只是一次性加的经验值数将乘以排序后这两个相邻时间点的实际差。这样,一个1..n的数组就足够了。
离散化的应用相当广泛,以后你会看到还有很多其它的用途。
2007.04.05补充:
VOJ1056那个例子看来还是有人不明白。
我发一张示意图,注意左边的10*7的数组是如何等价地转化为右边两个4*4的数组的
Matrix67原创
转载请注明出处