记得当年搞NOIp时，我犯过一个相当严重的错误：错误地把Floyd算法的i, j, k三层循环的位置顺序搞颠倒了。直到准备省选时我才突然意识到，Floyd算法应该最先枚举用于松驰操作的那个“中间变量”k，表示只经过从1到k的顶点的最短路；而我却一直习惯性地以为i, j, k应该顺次枚举。令人惊讶的是，这个错误跟了我那么久我居然从来都没有注意到过。后来，我发现有我这种经历的人不止一个。惯性思维很可能会让你接受一些明显错误的算法，并且让你用得坦坦荡荡，一辈子也发觉不了。
    假使你需要把一个数组随机打乱顺序进行重排。你需要保证重排后的结果是概率均等、完全随机的。下面两种算法哪一种是正确的？其中，random(a,b)函数用于返回一个从a到b（包括a和b）的随机整数。

1. for i:=1 to n do swap(a[i], a[random(1,n)]);
2. for i:=1 to n do swap(a[i], a[random(i,n)]);

查看更多 »

    最近忙着迎新，很久没有更新了。见了很多可爱的MM，让人欲火焚身。管萌MM是我们这个专业08的新生，人气相当高。在这里祝她生日快乐。好了，最近的情况就聊到这儿。
    Wilson定理指出，对于任一个质数p，都有(p-1)! ≡ -1 (mod p)，换句话说(p-1)! + 1能被p整除。为了证明这一点，让我们来考虑一个圆周上的p等分点。顺次连接这p个点我们可以得到一个正p边形，让它随便旋转多少个360/p度所得到的图形都和原来一样。类似地，跳跃着连接起第1, 3, 5...个点，或者两个两个地跳开来（连接1, 4, 7...个点），你可以得到一个星形的广义正p边形，它们同样满足类似的旋转对称性质。由于跳过k个点和跳过p-k-2个点是一回事，因此这种类型的多边形一共有(p-1)/2个。注意像这种“k个点k个点地跳着连接”的连接方式一定会遍历所有的点最后回到出发点：假如连接d个点后你就提前回到出发点了（而没有遍历完所有点），那一定还有若干组大小为d的点集没被连过，这样的话总点数就是d的倍数，与p是质数就矛盾了。
    除了这种旋转对称的“广义正p边形”以外，其它的多边形随便旋转多少都不能和原来全等。假设有图形最少只需要旋转d个点的位置(d>1)之后就与原图形重合，那么p一定是d的倍数，否则当到了k·d<p<(k+1)d时p-k·d就成了更小的与原图重合的旋转角度；然而p是d的倍数与p是质数矛盾。这告诉我们，非旋转对称的多边形总是p个p个的成组出现，因此它们的数目能被p整除。
    另一方面，连接圆周上的各点所能形成的多边形总数为(p-1)!/2，这是因为规定了起始点后，多边形就由剩下的p-1个点的排列确定，但每个多边形都各算了两次（顺时针、逆时针遍历各一次）。而前面已经提到过，广义的正p边形有(p-1)/2个。这样的话，非旋转对称的多边形总数就等于

  (p-1)!/2 - (p-1)/2 = 1/2 [(p-1)! + 1 - p]

    这个数目能被p整除当且仅当(p-1)! + 1能被p整除。

    来源：http://www.cut-the-knot.org/blue/GeometricWilson.shtml

    有趣的是，“p是质数”这一条件也是必要的。假设一个合数p也能整除(p-1)! + 1，这意味着它的某个大于1的因子d也能整除(p-1)! + 1；但同时d还能整除(p-1)!，这显然是不可能的。

    不知大家有过硬盘坏道没，反正有一次我是遇上了，珍贵的collection顷刻间化为乌有。信息时代，每个人都面临着一个新的问题：如何储存你的重要文件最为安全？大多数人会选择多弄它几个备份，虽然这种办法的效率和“性价比”都不高。有没有什么高效而又节省空间的办法来保证数据安全呢？最近，ttsiod写了一篇关于Linux小软件Rsbep的文章，里面提到的算法可以保证大段数据丢失以后仍然能复原原来的数据。算法基于一种叫做Reed-Solomon的编码方式。

    Reed-Solomon编码的核心思想非常有趣：任意k个点都惟一地确定了一个最高次数为k-1次的多项式，如果我们把要传送的信息用一个多项式函数上的点来表示，那么我们可以用更多的点来描述这一信息，这样即使某些点的位置在传输过程中发生了错误，接收者也能根据其它的点来复原全部信息。考虑一个大小为n的有限域（由于一个字节有2^8=256种可能的值，n通常取256），其元素分别为x_0, x_1, x_2, ..., x_n；而我们要传输的数据长度为k。首先我们把这k个字节的数据当作有限域的前k个非0元素所对应的函数值，确定出它们所对应的k-1次多项式函数f；然后计算出n-1个非0元素的函数值f(x_1), f(x_2), ..., f(x_n)，作为最终的编码发送出去。注意我们的元素是一个有限域，因此多项式的值仍然在这个域里面（范围仍然是0到255）。在实际应用中，我们通常取k=223，这样的话223个字节的数据将加强为一段255字节长的数据，其中有32个字节是附加的信息。这种编码的纠错能力很强，即使有16个字节在传输中发生错误，我们也能通过剩余的信息复原出原始数据。

查看更多 »

如果一个矩形可以分割为若干个小矩形，每个小矩形都有至少一边为整数长，则原矩形同样有至少一个长度为整数的边。换句话说，用至少有一边的长度是整数的小矩形拼成一个大矩形，大矩形也有至少一条整数长的边。

    不假，利用数论知识我们真的可以证明这个和数论八杆子打不着的题目。证明的关键就在于，质数有无穷多个。给定一个满足要求的大矩形，如果你宣称它的每条边都不是整数，它们都至少多出了大小为ε的“零头”。那么，我就找出一个足够大的质数p，使得1/p < ε，然后说明有一条边的长度除去整数部分后的“零头”不会超过1/p。这样的话，至少有一边恰好是整数长才行。
    仍然是把大矩形放在平面直角坐标系上，左下角对齐原点(0,0)。考虑所有形如(i/p, j/p)的点所形成的点阵（其中i, j均为整数）。我们需要把整个点阵平移到一个合适位置，使得点阵中没有点恰好落在小矩形的边界上。这总是可以办到的，例如我们算出每个小矩形的横边到点阵中离它最近的点的距离，取所有这些最近距离中最小的非0的值，然后竖直方向上移动一个比这还小的距离；另一个方向亦是如此。注意到每个小矩形内部所含的点数都是两个数的乘积，由于其中至少有一个数是p的倍数，因此每个小矩形内都有p的倍数个点。那么，整个大矩形所含的点的个数（即每个小矩形所含点数之和）也是p的倍数。大矩形内的所有点的个数也是两个数的乘积，然而p是质数，因此两个数中至少一个是p的倍数（数论的一个基本结论）。那么，对应的那条边就应该是整数长，并且最多有1/p的误差。

（三）（四）两种证明均来自http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/May1999.html

jintianhu2000在这个帖子里说：

这是本人读高中时发现的一个数学猜想，一直不能证明或推翻
 
任何一个不能被3整除的偶数，如488，按下列步骤：
若该数为偶数，则把它各位数之和的平方作为新数；若该数为奇数，则把它各位数之和的立方作为新数。再把那个新数重复以上步骤（数就各位数之和平方，奇数就各位数之和立方），一步步计算下去，肯定能在9步内变为1。
如：
  488(偶)    4+8+8=20      20*20=400
  400(偶)    4+0+0=4       4*4=16
  16(偶)     1+6=7         7*7=49
  49(奇)     4+9=13        13*13*13=2197
  2197(奇)   2+1+9+7=19    19*19*19=6859
  6859(奇)   6+8+5+9=28    28*28*28=21952
  21952(偶)  2+1+9+5+2=19  19*19=361
  361(奇)    3+6+1=10      10*10*10=1000
  1000(偶)   1+0+0+0=1     1*1=1   （共9步）
 
哪位高手能证明或推翻它？？

查看更多 »

    下面给出一种算法，该算法只需要使用加法运算和比较运算就可以求出n个数的最小公倍数：每一次操作都把当前最小的那个数加上它的初始值，直到所有数都相等为止。下面这个列表显示了用这个算法寻找30, 12, 18三个数的最小公倍数的全过程。初始时12是三个数中的最小数，于是该数加上12；接下来18成了最小的数，于是该数加上18变成了36；此时第二个数24又变成了最小数，于是再加上其对应的初始值12；以此类推直到三个数都变成相同的数180为止，这个180就是30, 12, 18的最小公倍数。

30 12 18
30 24 18
30 24 36
30 36 36
60 36 36
60 48 36
60 48 54
60 60 54
60 60 72
90 60 72
90 72 72
90 84 72
90 84 90
90 96 90
120 96 90
120 96 108
120 108 108
120 120 108
120 120 126
150 120 126
150 132 126
150 132 144
150 144 144
150 156 144
150 156 162
180 156 162
180 168 162
180 168 180
180 180 180

    这个算法为什么是正确的呢？它有什么实际用途呢？

查看更多 »

    又回来更新啦！虽然还有两门课没考，但今天已经轻松了不少。梦魇般的现代文学史总算是结束了。抱了两天两夜的佛脚，结果考试时一看卷子，仍然没一道会的题目。不定项选择多选少选均不得分，都是些文学常识题，给四篇我从没见过的小说名字问哪些是第一人称叙事，或者给四个人名字问哪些是笔名之类的。天哪……以后的古代文学史咋办啊。
    先强烈推荐一本好书。前几天在TopLanguage看到有牛人推荐Proofs from THE BOOK这本书，当即决定买了下来。这几天复习累了我都在看这本书，真的是很好很强大，里面汇集了很多著名问题的经典证明，包括很多我一直想找但没找到的证明。好了不多废话了，下面进入正题。

    很早以前，我们曾经研究过质数，证明了质数有无穷多个。后来，我们又学到了另外两种证明质数无穷多的方法。这两种方法的基本思路相同：寻找一个无穷大的集合，里面的数两两互质。只用有限个质数明显不能得到无穷多个两两互质的数，于是我们立即可知质数必然有无穷多个。今天，我们将证明两个比质数无穷多更强的定理。这两个证明都出自Proofs from THE BOOK的第一章。

    定义函数π(x)为“小于等于x的质数有多少个”。无妨规定x为一个正整数。我们将用初等微积分方法证明当x趋于无穷时π(x)也趋于无穷并给出π(x)的一个下界。我们将说明，对于所有x，π(x)>=log(x)-1，即x以内的质数至少有log(x)-1个。
    为了说明这一点，让我们考虑所有不超过x的质数的倒数的等比级数(1 + 1/p + 1/p^2 + ..)的乘积，即。
    回忆等比级数的公式，则我们有：

    第二行的一些变换非常巧妙。第二行中间的不等号是一个关键，用到了一个基本事实：第k个质数显然比k大。最后的连乘中前一项的分子和后一项的分母正好抵消，最后消完了就只剩了一个π(x)+1。
    另一方面，想像一下把(1+1/2+1/4+...)(1+1/3+1/9+...)(1+1/5+1/25+...)...展开的样子，很显然展开后的每一项都是一个所有质因子都不大于x的数的倒数，即Σ(1/m)，其中m取所有仅含1..x范围内的质因子的数。显然，原本就比x小的数，其质因子当然不可能超过x，这就是说从1到x的所有正整数都是属于m的。利用一些微积分的基本知识，我们可以立即得出Σ(1/m) >= 1+1/2+1/3+...+1/x >= log(x)。地球人都知道，log(x)是没有上界的，于是质数的个数也没有上界。
    这里还有一个类似的问题，大家可以对照着看看。

查看更多 »

对于哪些n，存在一个1到n-1的排列S_1, S_2, ..., S_n-1，使得T_1, T_2, ..., T_n-1也是一个1到n-1的排列，其中，

T_1 = S_1 mod n,
T_2 = (S_1 + S_2) mod n,
T_3 = (S_1 + S_2 + S_3) mod n,
.......
T_n-1 = (S_1 + S_2 + ... + S_n-1) mod n.

查看更多 »