一旦出现，永不消失

2010年8月13日 Earthson 没有评论

最终人择原理(Final anthropic principle (FAP)): “包含智慧的资讯处理过程一定会在宇宙中出现，而且，一旦它出现了就不会灭亡。” (Barrow和Tipler，1986)——摘自wikipedia

乍一看，这样论断太不靠谱，因为有太多的因素导致生命消失，这一论断确实是不可思议的。然而，仔细一想，这一论断其实来自于Choas（混沌）：系统一旦变得足够复杂，他将不可逆转的变得越来越复杂。这一模式被打破的概率，是如同时间逆转这种事件般不可思议的事

要理解这些是“困难”的，因为来自物理的现实总会带来不必要的误导！注意以下论述：

“人择原理”最初表达：自然定律惊人地适合生命的存在。

为什么？因为生命存在，而且它已经存在！如果这一条不成立，那怎么会有生命呢？另一方面，生命总是适应于它所存在的宇宙，这也是它存在的一个原因。我们应该注意到，没错，是适应！因为我们的宇宙是这个样子的，所以有我们这样的生命，但是，宇宙的不同发展方向，将完全会导致完全不同的场景，可能是完全不同的宇宙常数，完全不同的空间，也许有完全不同的生命。

生命是适应于它所存在的宇宙的，正因为如此，我们宇宙的某些条件并不能成为生命存在的必要条件。说说我前几天还有的一个误区吧:我一直认为，生命的存在依赖于负熵。地球是一个开放系统，有源源不断的负熵输入（稳定的），这些足以维持系统内部的有序（生命）。事实上，地球上的生命也确实非常依赖于这一点。为什么呢？因为负熵给予了系统极大的活力，给予了系统足够的初始复杂度，并且，它是一个外部的进化优势。没错，地球生命适应了这一点。如果负熵的输入不存在了，生命也将能适应这一点，我毫无疑问的相信。

chaos导致，即使是一个确定的系统，也会导致不可思议的事发生。即使是基于非常简单的基本模式，也许最终也会表现出惊人的复杂。更令人不可思议的是，这种复杂会形成模式，会发生自发的组织和进化！如果你对达尔文的进化论有足够的领悟，并不难理解这一点。没错，进化论是一个典型的chaos自进化现象。复杂一旦到达这个模式，他将变得越来越复杂，这一切几乎是不可逆转的。即使出现一个突发的事件，把已有的状态打乱，也很难彻底毁灭，因为彻底把所有的复杂降到一个限度是几乎不可能的，只有上帝（如果它存在的话）才能精确定位每一个复杂系统的位置并把它完全摧毁而不论它有多小，因此复杂被彻底击垮的概率，如同时间逆转般完全不可思议。

人择在某种程度上帮助了人们揭去物理具有误导性的特性，让我们更清楚的看到世界的本质

对混沌有所不解的朋友可以看下这部纪录片——《神秘的混沌理论》（The Secret Life of Chaos）-BBC

分类: 混沌 标签:

Warehouse and Truck(joj 2679)

2010年8月10日 Earthson 没有评论

2010吉林省赛E题Warehouse and Truck。卡车在仓库装了货物，送到各个商店（ 所有点都在一条直线上），耗费是当前载重量乘以距离（在每个商店卸下货物之后载重量发生变化）。

比赛的时候没找到算法，这题郁闷很久，一直到现在^^其实想想，当初比赛的时候连什么是DP都不知道。当时在数学上还有些癖好——根本无视递推，当时的我看来，只有通项才是有意义的-_-!确实太固执。。。
当然，我还是找到了解的形式：


显然，一旦到达一个端点，它应该一路直冲到另一端。在到达端点之前，有各种折返，但是可以确定每次折返都是越过仓库的（如果它折回来，必然是越过仓库以后再折回去的）。如上所说，这都是显然的。。。其实依照这些就可以很快导出递推，只不过当时的我对递推很不敏感，这真是杯具。

当然，后来我看了DP，我又发现自己陷入了一个尴尬的情况——我试图用看到过的DP方式去套。确实，很多简单的DP，这种方式是有效的。但是，这题很特殊，我尝试了各种套都失败了。。。
在前天晚上，我重新审视了这题的解的形式，我发现递推并不难构建（当然，这不是说式子本身不复杂，事实上，我觉得他很长）

首先，折返必然是穿越仓库(x=0)的。我们令i表示仓库左边的点，j表示仓库右边的点（我想我不需要用太多晦涩难懂的数学语言来描述这一点），
我们用d_{i,j}表示遍历i,j范围内所有点，但不越出这个范围的最优开销（其实就是一个字问题）。当然这是不够的，根据上面的解的形式，最优解必然在到达一个端点（i或者j）之后，直接转到另一个。我们需要区分两种情况：i\rightarrow{j} \;or\; j\rightarrow{i}然后这确实足够了

因为从i到j最优解必然是i\rightarrow{(j-1)} \;or\; {(j-1)}\rightarrow{i}的最优解末端往右到j。同样，对称的，可以得到j到i的，这样就得到了d_{i,j} \;and\;d_{j,i}。

这个递推，虽然描述简单，求起来却很麻烦。鉴于式子过长,代码就不贴了，因为我自己看起来都够呛（表达式很长）。这样的递推时间上是O(n^2)的，其实因为是对分的，所以常数很小^^

想了下，还是把状态方程写出来。我们令L_{i,j}为i到j的距离，令H_{i,j}为剩余货物的量（就是i到j所有点的货物全部写下之后剩下的货物），于是，我们有以下方程：

d_{i,j}=\min\;\{\;d_{i,j-1}+H_{i,j-1}\cdot L_{j-1,j}\;\;,\;\;d_{j-1,i}+H_{i,j-1}\cdot L_{i,j}\;\}
d_{j,i}=\min\;\{\;d_{j,i+1}+H_{i+1,j}\cdot L_{i,i+1}\;\;,\;\;d_{i+1,j}+H_{i+1,j}\cdot L_{i,j}\;\}

***如果递推特征不是很明显的话，或许分析解的特征，可以找到更多思路

分类: ACM 标签:

费马素数

2010年8月10日 Earthson 没有评论

费马素数指的是形如2^{2^m}+1的素数。现在考虑一个一般的形式p=a^m+1,a>1 在什么情况下p必为合数？

注意到以下式子

显然，等号后面是一个整数。我们令b=-1，如果m是一个奇数我们将发现a^m+1能被a+1整除。如果考虑置换m={2^s}\cdot{m},a=a^{2^s}，注意到a^m+1的值并没有变化。但是a^m+1能被a+1整除（同上），所以如果m含有2以外的因子（除非是1），则a^m+1必为合数。

至于等号后面的剩余部分，它是如同梅森素数般难缠的家伙，注意到他的项数是一个素数，以后慢慢研究

分类: Math 标签:

关于Dijkstra算法

2010年7月21日 Earthson 没有评论

其实Dijkstra算法只是基于以下显而易见的事实：

所有未知的路径都是由已知路径生成的，当然我们找到其中最小的那条（也许不止一条^^）。
如果所有边的权都是正的(这也是有负权Dijkstra失效的原因)，那么显然，新生成的路径的权值都不会比原来的小。
那么显然所有生成的路径都不会小于原来最小的那几条，这些路径显然就是最短路^^。
显然的，我们不需要关注那些不会再生成新路径的点，接着我们把刚才找到的这个点也变成这种类型的（这个好办，把它能生成的直接路径都生成了），接着，情况又和刚才一致了^^

考虑初始情况，就是我们第一次出发的那个点，到达这个点的权值显然是0，接着从它出发生成它能直接产生的新路径（就是和它直接连着的点），然后again and again…

分类: ACM 标签:

循环节

2010年6月1日 Earthson 2 条评论

记得以前我之前写过一篇分数循环节相关的文章，今天扩展一下：讨论下分数的循环解和指数mod p的循环节

考虑a/m在p进制下的输出（gcd(a,m)=1）和f(n)的循环节.首先说一下前者，因为前者的循环可以由后者直接得到！两者是同步的！当然有一种方式能使你很快意识到这一点

给出以下描述，如果t是使gcd(p^{t-1},m)最大的最小正整数,那么t就是循环起始的位置。简单的说，从t开始，\forall{n}\in{N^*},n\geqslant{t},g=gcd(p^{t-1},m)都不再变化(这个g后面会用到)。

显然当n小于t时gcd(f(n),m)和后面的gcd(f(n),m)不同,所以它n小于t时的f(n)不可能和后面的n>=t时的f(n)的任何一个相等，t之前的n就不会出现在循环内！当然，这还不能证明t就在循环内

当然由欧拉定理，我们可以马上得到，当gcd(p,m)=1时，循环节存在（欧拉函数的值必为循环节的倍数），且必然是从n=1开始的

然后注意到以下事实：

于是f(n)=g\cdot (\frac {a \cdot p^{n-1}}{g}\;\; mod \;\frac{m}{g})此时gcd(p^{n-1} , \frac{m}{g})=1，这和gcd(p,m)=1的情况其实是同构的.

令a= \frac{p^{t-1}}{g},m= \frac{m}{g},n=n-t，你就得到了和初始的式子一样的一个新式，用上面的欧拉定理你可以证明这次的这个是循环的，因为gcd(p,m)=1了，最后，别忘了这个是从第t位开始的（因为有变换n=n-t），而且结果需要乘以g（因为之前把这个公约数给提出来了）。

这个循环可以一一映射到分数的循环节，如果你把那个小学就学过了的竖式想得够彻底的话，这一切都是显然的

分类: Math 标签: