决不妥协

Farey序列
Farey序列Fn是满足0<=a<=b<=n且gcd(a,b)=1的分数的有序数列。例如：

Farey序列有哪些性质呢？

1.首先来个简单的，除了F1，所有序列都是奇数个，1/2一定是中间的数。

2.如果、、为Farey序列中连续的三项，那么：

对于Farey序列Fn，它有多少项呢？

，即其中的，表示的是k的欧拉函数。

Stern-Brocot树

Stern-Brocot树可以不重复地构造出所有的真分数！如图所示：

构造方法如下：我们假设根节点1/1拥有一对双亲，左边的叫母亲为0/1,右边的叫父亲，为1/0。每个节点的分母等于双亲的分母和，每个节点的分子等于双亲的分子和。沿着树向左走就是将当前节点作为父亲，生成一个新节点，沿着树向右走，就是将当前节点作为母亲，生成一个新节点。这样，我们就能不重复地构造出所有的分数！

可以看到Farey序列相当于将Stern-Brocot树中多余的枝叶给剪掉，然后从左向右排列出来。

为什么要讲这两个东西呢？因为我今天用这个做出了一道题，很有成就感……

2008 ACM/ICPC Asia Regional-HeFei site Problem G

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4275

题目大意是，给定分数a/b，要求找出两个分数，一个小于等于a/b，一个大于等于a/b，且分母小于n，且两者的差达到最小。

实际上，就是将a/b在Fn里定位之后，找离他最近的两个分数。可是Fn的生成我只会O(n)的，而这道题a,b,n的范围都是int型，有20亿之多。于是我就想到了Stern-Brocot树。

 首先可以肯定的是，如果n>=b，那么我直接输出两个a/b就可以了，所以n一定小于b。经过观察，我发现，要求的两个分数，一定出现在根节点到a/b的路径上。这条路径的另一个特性是，他的分母是递增的，相当显然……

假设向左走是L，向右走是R，那么任意一条路径都可以表示成一个由L和R组成的字符串，那么，这个字符串有多长呢？很遗憾，我们发现，对于一些数，比如1/n，他的路径长度是O(n)级别的……可是我们发现，1/n的路径，全部是L，如果我们用Lx来表示L出现了k次，将路径的表示方法压缩一下，那么长度就会大大缩小。路径采用压缩后的表示法需要多少字符呢？我们考虑最差情况，就是LRLRLR……这个时候分母是一个fibonacci数列，也就是说，压缩后的路径长度将在logn这个级别！

于是我的算法就有了一个大体的思路，先求出a/b的压缩后的路径序列，然后在这个序列里快速的找！

可是怎么求这个序列呢？这里直接提供一个结论:

对于分数x/y,如果x>y,那么x/y的路径只需在x-y/y的路径前加一个R，反之，如果x<y，那么x/y的路径只需要在x/y-x的路径前加一个L。

有了这个结论，我们可以采用类似辗转相除法的方法，得到x/y的压缩路径！例如3/4的路径就是L1R2。

然后我们再来看找答案这个过程。首先我们用一个矩阵[0 1 ; 1 0]来表示一个节点的双亲，例如[0 1 ; 1 0]，就表示1/1的双亲，第一行是分子，第二行是分母。向左走的过程，也就是左儿子的双亲矩阵，即是将当前节点的双亲矩阵乘以[1 1 ; 0 1],向右即是乘以[1 0 ; 1 1]。易知，在沿着路径走的过程中，母亲是非降的，父亲是非升的。对于矩阵的幂，我们可以用logn的时间求出，所以对于L2000这样的步骤，我们只需用log 2000的计算次数就能计算出他向左走2000步的双亲矩阵。

于是我们沿着压缩路径走啊走，突然，发现母亲的分母比n大了，这就说明，答案就在我们刚才走的那一步里，例如L200,或者R150。反正是方向+步数的形式，然后我们二分这个步数，就能查到最后一个分母不大于n的母亲了，这就是需要的两个分数中，小于a/b的拿一个！

同样的方法我们可以求出另一个。

整个算法的复杂度是logn的，走的过程又需要logn，所以是O( (logn)^2 )的。

最近选了门和人工智能相关的课。所以又提到了天下闻名的人机之战——卡斯帕罗夫Vs更深的蓝。

几度搜索，发现人机大战的过程远非想象的这么简单，IBM的深蓝赢得也不是那么“光明磊落”，这其中有些秘密，恐怕只有IBM那个小组的人知道了……

卡斯帕罗夫是谁？国际象棋第十三代棋王，独霸世界第一名号近二十年，传说天下间，只有大卡——第十二代棋王卡尔波夫可以与之抗衡。卡斯帕罗夫出道不久的时候挑战当时三十多岁应该算如日中天的卡尔波夫，规则是谁赢到六局算胜，和局不算。姜还是老得辣，卡尔波夫开局就打了个4：0，但是卡斯帕罗夫猛扛了三十多把和局后，终于赢了一盘。接下来的十多盘中小卡愈战愈勇，在48盘后将比分扳成5：3！这个时候国际象棋协会考虑到棋手的健康问题，不准他们下了……后来他们脱离了国际棋联组织，自己比，差不多比了三次，总比分每次都是卡斯帕罗夫小胜或者和局。这就是一代棋王卡斯帕罗夫，让他来代表人类我觉得是非常靠谱的。

而提到深蓝，大家有一个普遍的误区，就是97年那台电脑就是深蓝。其实深蓝早就有了，并且在96年就邀请卡斯帕罗夫进行了第一次人机大战，比赛的结果是4：2，卡斯帕罗夫轻松取胜，并且毫不留情地嘲笑了深蓝拙劣的棋艺……于是IBM要求一年后再来一场，棋王欣然应允。

于是在之后的一年内，IBM投了5000万美元，疯狂改造软件和硬件，终于打造出了这台拥有32个“大脑”的机器，它的名字是“更深的蓝”，就是比深蓝牛逼得多的意思……然后IBM精心打造了一场全程直播的世界瞩目的第二次人机大战！

由于我不懂国际象棋，根本无法了解形势的变化。不过好在有个国际象棋特级大师全程评论了每一场比赛，并且分析了两位“选手”可能的心理活动。这里是中文版的地址：http://www.chessit.net/file_games/kaspyblue97.htm 。英文原版的地址是：http://www.chesscafe.com/text/yaz05.pdf  （yaz01.pdf yaz04.pdf yaz09.pdf yaz11.pdf yaz13.pdf）

从文章中我们发现，卡斯帕罗夫全程都没有采用他最擅长的打法，而是采用的针对性很强的欺骗电脑的打法。也许是出于第一次人机大战的自信，在第一盘中卡斯帕罗夫采用了一种封闭性的布局，并不主动进攻，甚至一直没有越过第四条线。看来他是很清楚搜索算法的，国际象棋指数级的状态数无论是在时间上还是空间上，都不是现在的电脑能够解决的，面对局势不明朗和变化太多的场面，电脑往往会不知所措，采取等待性的招数。卡斯帕罗夫的计划实现的非常成功，第一盘他牢牢控制住了场上局面，侧翼缓慢推进，完美地赢得了比赛。

看来一年间，深蓝的变化不足为虑，一切都在掌握中。

然而第二局，成为了一个永远的疑点。

开局阶段，卡斯帕洛夫仍然下的很主动，而更深的蓝则下的优柔寡断。中局阶段卡斯帕罗夫精心设计了一个圈套，电脑的这一步将会取得明显的阶段性优势，然而在战略层面上则会落入卡斯帕罗夫布下的陷阱。更深的蓝一定会中计的，卡斯帕罗夫坚信，以他一年多来对于人工智能的经验。然而这一刻，更深的蓝在长考十五分钟后，下出了一步让卡斯帕罗夫震惊的棋——它并没有夺取眼前的优势，而是选择了一步现阶段完全没有用，却能对局面产生深远影响的一招。这是一步只有一流的特级大师才能下出的棋。接下来深蓝的每一步都极具克制性，终于彻底击垮了卡斯帕罗夫的心理防线，终于，他认输了。虽然局面上看起来更深的蓝有着很大优势，但是赛后经过无数的分析，认为这一盘实际上还是一个精妙的和局。

这时候卡斯帕罗夫焦躁不安，这不是电脑能下出的棋，他要求IBM提供深蓝思考过程的打印稿，然而IBM拒绝马上提供。

谁也不知道IBM有没有在那15min里给卡尔波夫打电话……

卡斯帕罗夫无心恋战，三四五局都以和棋收场，局面上一直为卡斯帕罗夫所控制，但都因为几个或大或小的失误被更深的蓝经过精巧的计算逼和。实际上，他的心理已经出现了波澜，几度尝试通过冷僻的开局来避开更深的蓝庞大的开局库。

终于，第六局，卡斯帕罗夫崩溃了，19步脆败。

IBM的股票猛涨15%，直接受益1亿美元。发瑞脑消金兽言人激动人心的宣布人机大战告一段落！然而卡斯帕罗夫说“不！才刚刚开始”。

但是IBM二话不说，拒绝了卡氏的复仇申请，马上将更深的蓝肢解，放进了博物馆……

POJ1207 the 3N+1 Problem  直接模拟

POJ3601 Tower of Hanoi
考虑只有一种的情况，则答案为2*Disk[1]-1
接下来，设A[i]为不考虑同等大小盘子顺序移动次数（移动之后，同样大小的盘子顺序正好相反）
          B[i]为考虑同等大小盘子顺序移动次数，则：
          A[i]=2*A[i-1]+Disk[i]
               B[i]=2*A[i-1]+1
                      2*A[i-1]+2*Disk[i]+B[i-1]
               原因是，经过过两次A[i]，正好还原成初始状况。
------------------1.14

POJ1019 Number Sequence
非常有趣的数列……
我的方法是用Num[i]记录1..i的序列长度
用Sum[i]记录Num[1]..Num[i]的长度
考虑数据较小，做两遍顺序查找
第一遍超出位置x属于1..temp的temp
第二遍找x在哪个数上

POJ1014 Dividing
非常非常有意思！
--------------------------------------------------------------------------------
发信人: wu ** (lagrima), 信区: ACM_ICPC
标  题: 关于dividing问题中如何将20000改写为1000问题的严格证明：
发信站: 北大未名站 (2003年03月13日21:49:11 星期四) , 站内信件

对于任意一组数,6的个数为n(n>=

一。如果可以分成两堆，我们可以分成两种情况：
1.两堆里都有6，那么我们可知：把n改为n-2，仍然可分。(两堆各减一个6)
2.只有一堆里有6，设为左边，那么左边的总和不小于6*8=48。
  我们观察，5*6=6*5  ，4*3=6*2  ， 3*2=6  ， 2*3=6 ， 1*6=6
  而 5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 25 + 8 + 3 + 4 + 5 = 45 < 48
  由抽屉原理右边必然存在(多于5个的5 或者 多于2个的4 或者 多于1个的3
                         或者 多于2个的2 或者 多于5个的1)
  即右边至少存在一组数的和等于若干个6，比如右边有3个4
  这样把左边的2个6与右边的3个4交换，则又出现左右都有6的情况。
  根据1，我们还是可以把n改为n-2且可分的状态不变。
综合1，2。我们可以看出只要原来n的个数>=8,我们就可以把它改为n-2，
这样操作一直进行到n<8。我们可以得出结论，对于大于等于8的偶数，可以换成6
对于大于8的奇数，可以换成7。换完之后仍然可分。

二。如果不能分成两堆：
  显然改为n-2时同样也不能分，那么对于大于等于8的偶数，可以换成6
对于大于8的奇数，可以换成7。换完之后仍然不可分。

综合一，二。我们得出结论把不小于8的偶数改为8，大于8的奇数改为7，
原来可分与否的性质不会改变。

以上是对6的讨论，同样的方法可以推出
5的个数 6*4 + 4*4 + 3*4 + 2*4 + 1*4 = 64 < 5*13
    即5的个数多于12时，偶数换为12，奇数换为11
4的个数 6*1 + 5*3 + 3*3 + 2*1 + 1*3 = 35 < 4*9
    即4的个数多于8时，偶数换为8，奇数换为7
3的个数 5*2 + 4*2 + 2*2 + 1*2 = 24 < 3*9
    即3的个数多于8时，偶数换为8，奇数换为7
2的个数 5*1 + 3*1 + 1*1 = 9 < 2*5
    即2的个数多于4时，偶数换为4，奇数换为3
1的个数 多于5则必然可分(在总数是偶数的前提下)
  

--

※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.108.234]

POJ1434 Fill the Cisterns! 二分高度

------------------1.15

POJ2688 Cleaning Robot 先广搜求出各点距离，然后状态压缩DP
------------------1.16
POJ1517 u Calculate e 水题
------------------1.17
POJ3146 Interesting Yang Hui Triangle
将b转化为a进制，求TT(ai+1)
证明如下：http://hi.baidu.com/5l2_/blog/item/5035c422fd32f5a24623e8c7.html
分析1：
          我们知道对于素数p，n！中p的幂次为
          f[n!,p]=[n/p]+[n/p^2]+[n/p^3]……
          
          那么C[n,m]中p的幂次为
          f[c[n,m],p]=f[n,p]-f[n-m,p]-f[m,p]
          
          c[n,m]不能被p整除，意味着f[n,p]=f[n-m,p]+f[m,p]
          于是 [n/p^i]=[(n-m)/p^i]+[m/p^i]对任意i成立
        
设n的p进制表示为(ak……,a0)
          设n-m的p进制表示为(bk……,b0)
          设m的p进制表示为(ck……,c0)
          
[n/p^k]=ak=[(n-m)/p^k]+[m/p^k]=bk+ck                                                        =>ak=bk+ck
          [n/p^(k-1)]=(aka(k-1))=[(n-m)/p^(k-1)]+[m/p^(k-1)]=(bkb(k-1))+(ck(ck-1))   =>a(k-1)=b(k-1)+c(k-1)
         ……
         我们可以得到ai=bi+ci
        
         即当0=<bi<=ai时对任意i成立时 f[n,p]=f[n-m,p]+f[m,p]，即p不整除c[n,m]
        
         所以c[n,m]不被p整除的数有 TT(ai+1) (0=<i<=k)个。
分析2:
         书上例题
         设p为质数，a，b为两正整数，且a,b在p进制下表示为 a=(ak……,a0),b=(bk……,b0) 0=<ai,bi<p
证明 c[a,b]=c[ak,bk]*……*c[a0,b0](mod p)
          证：
               p为质数时易证 (1+x)^p=1+x^p(mod p)
               (1+x)^a=(1+x)^(ak*p^k)……(1+x)^(a0) （mod p）
                          =(1+x^(p^k))^ak……(1+x)^a0（mod p） （1）
               x^b在（1）右边式子的系数为c[ak,bk]*……*c[a0,b0]。
              从而的证 c[a,b]=c[ak,bk]*……*c[a0,b0](mod p)
          
         根据这个结论 我们可知c[a,b]=0(mod p) 当且仅当 存在bi>ai
        
         所以c[n,m]不被p整除的数有 TT(ai+1) (0=<i<=k)个。
------------------1.19
POJ 2361 Tic Tac Toe 井字棋游戏，直接从原始状态开始搜索
POJ 3075 Tic Tac Toe 较上题稍加修改，注意当无空格可填时亦为结束状态
POJ 2602 Superlong sums 祸害百姓的水题，必须要用getchar()读入
POJ 3111 迭代，每次取前K个，求得S，然后以V-W*S为值排序，接着取K个
证明见http://hi.baidu.com/jlw686/blog/item/da222a64dae5fcf5f636541b.html
POJ 1809 Regetni 分类讨论
1.点的类型就4种 （奇,偶）（奇,奇）（偶，奇）（偶,偶）。
2.仅当有两个点类型相同时，三角形面积是整数。
3.点的个数和最后的结果都必须用long long
4.必须用cout，而不是printf lld。很奇怪
------------------1.20
POJ 3274 Gold Balanced Lineup 将数组Hash化。
------------------1.21
POJ 1190 生日蛋糕 NOI99 搜索，加剪枝
POJ 1651 Multiplication Puzzle
动规方程 枚举最后取走的石子： f[i][j]=Min(f[i][k] + f[k][j] + X[i] * X[j] *X[k])
有趣的是，如果将中间的N-2个数都拆成两个，然后，两个为一组，题目就变成了NOIP2006第一题，只不过是个链而不是环
------------------1.22
POJ 1080 Human Gene Functions 简单DP
------------------1.23
POJ 1163 The Triangle DP入门题目
POJ 1579 Function Run Fun 记忆化搜索的入门题目
POJ 2081 Recaman's Sequence 按定义递推+hash表判重
---------------------1.24
POJ 1953 World Cup Noise Fibonacci数列
POJ 1458 Common Subsequence 最长公共子序列
---------------------2.3
UVA 4128 Steam Roller （world final 2008）
拆点最短路，一点拆为5点，分别记录四个方向，以及一个特殊的

拐弯点

UVA 2052 Number Steps(ACM 2000 regionals-Tehran) 水题
SRM430 Div2 275 统计>maxSize的人数和<minSize的人数，输出

其较大值
SRM430 Div2 500 把x的0位用k代替，1全部替换为0
---------------------2.4
SRM430 Div2 1000 状态压缩DP
F[i][j][k]，表示第i个人以j的价格买到画，状态为k时最多经手

的人数，则
if j<=price[i][o] && (o&k==0)
F[i][j][k]+1-->F[o][price[i][o]][k+(1<<o)]
---------------------2.5
SRM430 Div1 500 状态压缩DP
由于只有10个点，每个点的度不超过3，所以每个点用两个二进制

表示。由于最多只有N*(N-1)/2条，也就是最差也只有45条边，我

们可以把这个问题看45个拥有10个属性的物品的背包问题。复杂

度N*(N-1)/2 * 4^N
SRM433 Div2 250 最大和最小的乘在一起
---------------------2.7
SRM434 Div2 250 求五个数中最小的数K，K至少是三个数的倍数
SRM434 Div2 500 取一组数，使得他们的行标号和列标号都为等

差数列，使得这个数为完全平方数
SRM434 Div2 1000 枚举每个字母更改之后的改变大小，取前K个

，高精度运算
SRM433 Div1 250 枚举+KMP
---------------------2.8
SRM433 Div1 500 先枚举最左端点为(0,0)的菱形个数，再拓展到

全部格子
SRM432 Div1 250 先枚举要消去的行，再判断消去了几行 注意K

不一定要用完
---------------------2.10
SRM432 Div2 250 水题，找自信
---------------------2.11
SRM432 Div1 500 一开始想到欧拉路去了，结果纯属多余……只

要根据首尾字母找到联通块，判断是否大于1即可。一开始没想清

，原代码改了又改，无数细节问题，烦死了！
SRM431 Div1 250 请使用atan2函数
---------------------2.12
SRM435 Div1 250 树的遍历
POJ 1700 Crossing River
POJ 3404 Bridge over a rough river
POJ 2573 Bridge
方法贪心：
1)如果N=1或者N=2，所有人直接过桥。
2)如果N=3,由最快的人往返一次把其他两人送过河。
3)如果N>=4,设A，B为走的最快的和次快的旅行者，过桥所需时间

分别为a,b；而Z,Y为走得最慢的和次慢的旅行者，过桥所需时间

分别为z,y。那么
当2b>a+y时，使用模式一将Z和Y移动过桥
当2b<a+y时，使用模式二将Z和Y移动过桥
当2b=a+y时，使用模式一或者模式二将Z和Y移动过桥。
这样问题就变成了N-2个旅行者的情形，递归解决即可。
注：这里的模式1指的是A将Z送过桥，然后返回，再把Y送过桥，

再返回；模式2指的是A和B先过桥，然后A返回，Y和Z过桥，然后B

返回
---------------------2.13
HDOJ 214公开赛
A 水题，A+B
B ax^2+bx+c=0(mod 2^32)是否有正整数解（未AC）
C 将小时，分钟，上下午各看做一维，广搜即可
D 欧拉回路，注意要判断一下连同性
E 字符串处理，trick——EOF和EOD可以作为单词出现在文档中
F 本金+利率求达到预期存款的时间。简单题，顺秒
G 算GPA，水题。
---------------------2.14
ZJU 2008.2月赛
E To Go or Not to Go 分位统计概率，需要用到logn的统计0-x的二进制1个数，WC09论文有讲。
F Apple Pile 强大的题目。由于只吃好苹果，所以只要坏了哪怕1%的苹果都是没用的……所以x和y不影响结果，对于N输出N-1
---------------------2.15
POJ 3623 Best Cow Line, Gold
首先将原串于其相反串合并成一个新串。
用O(n)的算法建立后缀数组，然后设立两个指针，比较后缀大小进行贪心。
---------------------2.17
POJ 2774 Long Long Message
将两串变为一串，就变成了最大LCP问题，直接查询height数组中满足条件的最大值即可。
---------------------2.19

本来打算做到100道的，结果算上topcoder也只完成了一半……其实有51道，不信你数数

来自：http://www.cnblogs.com/drizzlecrj/ 一切随心 

   在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，四人所需要的时间分别是1、2、5、8分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这四人尽快过桥。

    过桥问题详细的描述与解决方案请阅读《过桥问题——经典智力题推而广之五》,共7个小节，作者讲述的非常细致。

    结论我给再叙述一下:

以下是构造N个人(N >= 1)过桥最佳方案的方法：

1)如果N=1或者N=2，所有人直接过桥。

2)如果N=3,由最快的人往返一次把其他两人送过河。

3)如果N>=4,设A，B为走的最快的和次快的旅行者，过桥所需时间分别为a,b；而Z,Y为走得最慢的和次慢的旅行者，过桥所需时间分别为z,y。那么

当2b>a+y时，使用模式一将Z和Y移动过桥

当2b<a+y时，使用模式二将Z和Y移动过桥

当2b=a+y时，使用模式一或者模式二将Z和Y移动过桥。

这样问题就变成了N-2个旅行者的情形，递归解决即可。

注：这里的模式1指的是A将Z送过桥，然后返回，再把Y送过桥，再返回；模式2指的是A和B先过桥，然后A返回，Y和Z过桥，然后B返回

1. pku 1700 Crossing River (pku 3404 Bridge over a rough river)

就是最朴素的过桥问题，问最少所需时间

2. pku 2573 Bridge

在1的基础上加上过桥所需要的步骤

3. zju 1579 Bridge 

这里要用long long 真恶

4. hit 2540 Only One Boat

这个题目是过桥问题的变种,题目的意思就是有N队夫妻,现在要过河，但是只有一条船，并且船每次只能载两个人。要求每一个妻子不能在丈夫不在的情况下与其他男人在一起，无论是船上还是岸上都不可以。问最少的次数使得所有人过河，并打印具体的步骤(spj)。

这个问题最少次数其实是固定的，不难推出如果有n队夫妻，那么全部过河的最少次数是5*n-3。（这个原因我请教了这个题目的作者，他的意思是最优的策略一定是两个人坐船去彼岸，一个人坐船回此岸。因此最少次数是一定的)。知道了最少次数如何去打印具体步骤了，其实我们从样例中3队夫妻的说明中可以得到一些启发，就是说经过若干步之后可以使得一对夫妻"Leave"。 例如3队夫妻的时候，标号为1，2为第一对夫妻（奇数为男，偶数为女，下同）,标号为3，4为第二对夫妻，标号为5，6为第三对夫妻。那么由2，4首先坐船来到彼岸，然后2回去，2和6再来到彼岸回去，然后6回去，让1，3过来，然后1和2离开，3回头，3和5再过去，3和4离开，5回头，5和6过河并离开。 现在转换到n个人的情形。如果n=1或者2，那么很容易就能找到方案了，因此下面的情况针对n>=3的情况，我们可以先让2n和2n-2过河，然后2n回来。(注：这个时候所形成的局面是此岸有n-1对夫妻和一个丈夫，彼岸有一个该丈夫的妻子）。下面2n和2n-4过河，然后2n-4回来，2n-1和2n-3过河，2n和2n-1 离开，2n-3返回。（注：这个时候的局面是此案有n-2对夫妻和一个丈夫，彼岸有一个该丈夫的妻子）。可以看出这是一个递归的过程。下面实现就简单了。

5. zju 2288 Across the River

题目大意: n个男生和m个女生过河.只有一只船,船每次最多装k人且满足如下条件:

任何时候岸边(包括此岸和彼岸)和船上要么没女生.否则女生不比男生少，问最少要渡几次才能使得所有人渡河完毕。

这个题目如果没有说要求彼岸也满足这个要求（即女生不比男生少，或者没有女生），我们可以利用贪心算法解决。

可以总是先把男生给送到彼岸，然后剩下来的部分都是尽量在满足条件的情况下把男生往船上放，然后每次把船从彼岸送回来的人最好是女生。这样可以使得结果次数最少。

但是现在要求的是此案和彼岸都必须满足条件，这样的话我们就只能bfs搜了。数据量不算大。

维基百科，自由的百科全书

蒙提霍尔问题图解

蒙提霍尔问题，亦称为蒙特霍问题或三门问题（英文：Monty Hall problem），是一个源自博弈论的数学游戏问题，大致出自美国的电视游戏节目 Let's Make a Deal。问题的名字来自该节目的主持人蒙提·霍尔（Monty Hall）。

这个游戏的玩法是：参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车，选中后面有车的那扇门就可以赢得该汽车，而另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门，但未去开启它的时候，节目主持人会开启剩下两扇门的其中一扇，露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。问题是：换另一扇门会否增加参赛者赢得汽车的机会率？如果严格按照上述的条件的话，答案是会—换门的话，赢得汽车的机会率是 2/3。

这条问题亦被叫做蒙提霍尔悖论：虽然该问题的答案在逻辑上并不自相矛盾，但十分违反直觉。这问题曾引起一阵热烈的讨论。

[编辑] 问题与解答

[编辑] 问题

以下是蒙提霍尔问题的一个著名的叙述，来自 Craig F. Whitaker 于1990年寄给《展示杂志》（Parade Magazine）玛丽莲·沃斯·莎凡特（Marilyn vos Savant）专栏的信件：

假设你正在参加一个游戏节目，你被要求在三扇门中选择一扇：其中一扇后面有一辆车；其余两扇后面则是山羊。你选择了一道门，假设是一号门，然后知道门后面有什么的主持人，开启了另一扇后面有山羊的门，假设是三号门。他然后问你：“你想选择二号门吗？”转换你的选择对你来说是一种优势吗？

以上叙述是对 Steve Selvin 于1975年2月寄给 American Statistician 杂志的叙述的改编版本。如上文所述，蒙提霍尔问题是游戏节目环节的一个引申；蒙提·霍尔在节目中的确会开启一扇错误的门，以增加刺激感，但不会容许玩者更改他们的选择。如蒙提·霍尔寄给 Selvin 的信中所写：

如果你上过我的节目的话，你会觉得游戏很快—选定以后就没有交换的机会。
—(letsmakeadeal.com)

Selvin 在随后寄给 American Statistician 的信件中(1975年8月) 首次使用了“蒙提霍尔问题”这个名称。

一个实质上完全相同的问题于1959年以“三囚犯问题”（three prisoners problem）的形式出现在马丁·加德纳的《数学游戏》专栏中。葛登能版本的选择过程叙述得十分明确，避免了《展示杂志》版本里隐含的前提条件。

这条问题的首次出现，可能是在1889年约瑟夫·贝特朗所著的 Calcul des probabilités 一书中。 在这本书中，这条问题被称为“贝特朗箱子悖论”（Bertrand's Box Paradox）。

Mueser 和 Granberg 透过在主持人的行为身上加上明确的限制条件，提出了对这个问题的一种不含糊的陈述：

• 参赛者在三扇门中挑选一扇。他并不知道内里有什么。
• 主持人知道每扇门后面有什么。
• 主持人必须开启剩下的其中一扇门，并且必须提供换门的机会。
• 主持人永远都会挑一扇有山羊的门。
  • 如果参赛者挑了一扇有山羊的门，主持人必须挑另一扇有山羊的门。
  • 如果参赛者挑了一扇有汽车的门，主持人随机在另外两扇门中挑一扇有山羊的门。
• 参赛者会被问是否保持他的原来选择，还是转而选择剩下的那一道门。

转换选择可以增加参赛者的机会吗？

[编辑] 解答

问题的答案是可以：当参赛者转向另一扇门而不是继续维持原先的选择时，赢得汽车的机会将会加倍。

有三种可能的情况，全部都有相等的可能性(1/3)：

• 参赛者挑山羊一号，主持人挑山羊二号。转换将赢得汽车。
• 参赛者挑山羊二号，主持人挑山羊一号。转换将赢得汽车。
• 参赛者挑汽车，主持人挑两头山羊的任何一头。转换将失败。

在头两种情况，参赛者可以透过转换选择而赢得汽车。第三种情况是唯一一种参赛者透过保持原来选择而赢的情况。因为三种情况中有两种是透过转换选择而赢的，所以透过转换选择而赢的概率是2/3。

如果没有最初选择，或者如果主持人随便打开一扇门，又或者如果主持人只会在参赛者作出某些选择时才会问是否转换选择的话，问题都将会变得不一样。例如，如果主持人先从两只山羊中剔除其中一只，然后才叫参赛者作出选择的话，选中的机会将会是 1/2。 不过若主持人不知道哪扇门有羊，在参赛者选择后仍开出羊，此时透过转换选择而赢的概率仍为2/3。

另一种解答是假设你永远都会转换选择，这时赢的唯一可能性就是选一扇没有车的门，因为主持人其后必定会开启另外一扇有山羊的门，消除了转换选择后选到另外一只羊的可能性。因为门的总数是三扇，有山羊的门的总数是两扇，所以转换选择而赢得汽车的概率是2/3，与初次选择时选中有山羊的门的概率一样。

[编辑] 笔者的一个小小疑惑

Ａ：车，Ｂ：山羊１，Ｃ：山羊２
以下是”所有”可能性：
－

• 先选Ａ

主持人选Ｂ,不变（Ａ）

主持人选Ｂ,变（Ｃ）

主持人选Ｃ,不变（Ａ）

主持人选Ｃ,变（Ｂ）

• 先选Ｂ

主持人选Ｃ,不变（Ｂ）

主持人选Ｃ,变（Ａ）

• 先选Ｃ

主持人选Ｂ,不变（Ｃ）

主持人选Ｂ,变（Ａ）

－
在以上的组合，可见变与不变亦是一半可能。
这个疑惑留待其他人解答。

解答： 问题出在于，所谓“所有”的可能性，发生的几率并不是相等的。虽然列出了4种情况（选手A，主持人B；选手A，主持人C；选手B，主持人C；选手C，主持人B）但其实前面两种情况发生的几率相等于第三种或第四种情况发生的几率。

选手选择A，B或C的几率，各是1/3

在选手选A的情况下，主持人选择B或C的几率各是一半，既是1/6。 在选手选B（或C）的情况下，主持人必定选择C（或B）。 所以，选择不变换决定，答对的可能性是“先选A”情况下的1/6+1/6，仍是1/3。 选择变换决定，则正确率为“先选A”及“先选B”情况，1/3+1/3，得2/3。

疑问： 参赛者挑山羊一号，主持人挑山羊二号。转换将赢得汽车。 参赛者挑山羊二号，主持人挑山羊一号。转换将赢得汽车。 参赛者挑汽车，主持人挑两头山羊的任何一头。转换将失败。 貌似应为： 参赛者挑山羊一号，主持人挑山羊二号。转换将赢得汽车。 参赛者挑山羊二号，主持人挑山羊一号。转换将赢得汽车。 参赛者挑汽车，主持人挑山羊二号。转换将失败。 参赛者挑汽车，主持人挑山羊一号。转换将失败。

来自：三思科学网络杂志第一期 

作者：异调 

一、一个简单的问题

当我们阅读数学史时，会有这样一种印象，数学家们首先研究简单的
问题，然后研究越来越复杂的问题。经常性地，高深的数学问题是非
常复杂的。只是为了理解问题，我们就得学习非常多的数学知识；而
为了解决它，那就得用更复杂的数学知识了。就算我们在学校里的数
学考试也是如此，最后一题经常被叫做“最后一大题”，“一大题”
是说它表达复杂，里面还有一二三四的小题，要理解题意就得几分钟
的时间。弄不好还理解错了，搞得整道题都白白做，被扣去许多分。

可是数学里不只有这些吓人的“大题”——我是说，数学里还有吓人
的“小题”。这样的“小题”理解起来非常容易，却让无数数学家大
跌眼镜，怎么冥思苦想也不得其解。3x+1问题大概就是其中最著名而
又最简单的一个。它简单到大概任何一个会除2和会乘3的人（比如说，
没文化但是经常买菜的老奶奶）都能理解它的意思，但是困难得让数
学家至今也没有找到好好对付它的方法。

任取一个自然数，如果它是偶数，我们就把它除以2，如果它是奇数，
我们就把它乘3再加上1。在这样一个变换下，我们就得到了一个新的
自然数。如果反复使用这个变换，我们就会得到一串自然数。

比如说我们先取5，首先我们得到3*5+1=16，然后是16/2=8，接下去
是4，2和1，由1我们又得到4，于是我们就陷在4→2→1这个循环中了。

再举个例子，最开始的数取7，我们得到下面的序列：
7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
这次复杂了一点，但是我们最终还是陷在4→2→1这个循环中。

随便取一个其他的自然数，对它进行这一系列的变换，或迟或早，你
总会掉到4→2→1这个循环中，或者说，你总会得到1。已经有人对所
有小于100*2⁵⁰=112589990684262400的自然数进行验算，无一例外。

那么，是否对于所有的自然数都是如此呢？

这看起来是个多么简单的问题啊！

二、克格勃的阴谋？

这个问题大约是在二十世纪五十年代被提出来的。在西方它常被称为
西拉古斯(Syracuse)猜想，因为据说这个问题首先是在美国的西拉古
斯大学被研究的；而在东方，这个问题由将它带到日本的日本数学家
角谷静夫的名字命名，被称作角谷猜想。除此之外它还有着一大堆其
他各种各样的名字，大概都和研究和传播它的数学家或者地点有关的：
克拉兹(Collatz)问题，哈斯(Hasse)算法问题，乌拉姆(Ulam)问题等
等。今天在数学文献里，大家就简单地把它称作“3x+1问题”。

角谷静夫在谈到这个猜想的历史时讲：“一个月里，耶鲁大学的所有
人都着力于解决这个问题，毫无结果。同样的事情好象也在芝加哥大
学发生了。有人猜想，这个问题是苏联克格勃的阴谋，目的是要阻碍
美国数学的发展。”不过我对克格勃有如此远大的数学眼光表示怀疑。
这种形式如此简单，解决起来却又如此困难的问题，实在是可遇而不
可求。

数学家们已经发表了不少篇严肃的关于3x+1问题的数论论文，对这个
问题进行了各方面的探讨，在后面我会对这些进展作一些介绍。可是
这个问题的本身始终没有被解决，我们还是不知道，“到底是不是总
会得到1？”

在1996年B. Thwaites悬赏1100英镑来解决这个问题。我写一下这个
悬赏的文献：Thwaites, B. “Two Conjectures, or How to win
￡1100.”Math.Gaz. 80, 35-36, 1996，好在大家万一证出来时知
道跑哪里去领奖。看在钱大爷的份上，3x+1问题于是又多了个名字，
叫Thwaites猜想。

要是真的有这么一个自然数，对它反复作上面所说的变换，而我们永
远也得不到1，那只可能有两种情况。

1)它掉到另一个有别于4→2→1的循环中去了。我们在后面可以看到，
要是真存在这种情况，这样一个循环中的数字，和这个循环的长度，
都会是非常巨大的；
2)不存在循环。也就是说，每次变换的结果都和以前所得到的所有结
果不同。这样我们得到的结果就会越来越大（当然其中也有可能有暂
时减小的现象，但是总趋势是所得的结果趋向无穷大）。

因为这是个形式上很简单的问题，要理解这个问题所需要的知识不超
过小学三年级的水平，所以每一个数学爱好者都可以来碰碰运气，试
试是不是能证明它。不过在这里我要提醒大家的是，已经有无数数学
家和数学爱好者尝试过，其中不乏天才和世界上第一流的数学家，他
们都没有成功。如果你在几小时内就找到了一个“证明”，那么把它
一步一步地严格地写下来，看看是不是严密正确（我可以肯定它是错
的，我这样的肯定要冒的危险绝不超过连续中十次彩票头奖的概率，
既然我不买彩票，我就没道理不这么肯定 ）。事实上，在互联网上
已经有一些错误的“证明”。据说还有个数学爱好者跑到公证处去公
证他的“证明”，生怕别人把他的好主意偷跑了。

二十多年前，有人向伟大的数论学家保尔·厄尔多斯(Paul Erdos)介
绍了这个问题，并且问他怎么看待现代数学对这问题无能为力的现象，
厄尔多斯回答说：“数学还没有准备好来回答这样的问题。”

三、一些概念，一些纪录

虽然证不出猜想，但是数学家们还是得到了许多很可能很有用的结论。
让我们先来定义几个概念，然后再来介绍这些结论。

从一个自然数开始，用上面这个变换，我们可以计算出一串自然数的
序列。为了形象起见，我们把这串数列叫做以最初用来开始计算的那
个自然数命名的“航班”。比如说，第6次航班就是
6→3→10→5→16→8→4→2→1
我们把一个航班里的最大数字，叫做这个航班的“最大飞行高度”。
比如说，第6次航班的最大飞行高度就是16。我们把航班在数字1“着
陆”之前的数字个数（最初的数字包含在内，但1不包含在内），叫
做这个航班的“航程”（特别定义第1次航班的航程为0）。第6次航
班的航程就是8。如果真有自然数在此变换下永远达不到1，那么这个
航班的航程就是无穷了。

接下去的概念稍微有点复杂。我们把从起点开始（但不包括起点）连
续的不小于起点的数字的个数，叫作“保持高度航程”。举一个例子
来说明这个概念比较方便：第11次航班是
11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
我们看到从起点开始，34，17，52，26，13，40，20都不小于起点11，
共有7个数字，所以第11次航班的保持高度航程为7。后面的航程中虽
然还有数字16大于起始点11，但是它不被算在保持高度航程里了。一
个最简单的推论就是，偶数次航班的保持高度航程总是0，因为开始就
除以2，跌到较低的高度去了。

为什么我们对一个航班的保持高度航程感兴趣？因为如果所有航班的
保持高度航程都是有限的话，3x+1问题就成立了。让我们假设已知所
有航班的保持高度航程都是有限的，用数学归纳法来证明3x+1问题，
也就是所有的航班都在1上“着陆”。我们已经知道第1到第5航班都
是在1上着陆的，现在假设对于所有小于n的数字k，第k次航班都在1
上着陆，我们来看看第n次航班的情况：由于按假设它的保持高度航
程是有限的，所以它迟早会降落在一个比n小的数字上——于是按归
纳假设它就会降落在1上！

我们可以对开始的30班航班列出一个相关数据表来：

航班  航程  保持高度航程  最大飞行高度
1      0         0               1
2      1         0               2
3      7         5              16
4      2         0               4
5      5         2              16
6      8         0              16
7     16        10              52
8      3         0               8
9     19         2              52
10      6         0              16
11     14         7              52
12      9         0              16
13      9         2              40
14     17         0              52
15     17        10             160
16      4         0              16
17     12         2              52
18     20         0              52
19     20         5              88
20      7         0              20
21      7         2              64
22     15         0              52
23     15         7             160
24     10         0              24
25     23         2              88
26     10         0              40
27    111        95            9232
28     18         0              52
29     18         2              88
30     18         0             160

下面要说说几个记录。在上面我们已经说过，目前3x+1问题已经被检
验到100*2⁵⁰=112589990684262400，都没有发现反例。这是葡萄牙阿
弗罗(Aveiro)大学的Tomas Oliveira e Silva的工作，用了很巧妙
的编程方法。他的主页在http://www.ieeta.pt/~tos/3x+1.html

如果一个航班的航程大于所有它前面的航班的航程，我们就把它叫作
“航程纪录航班”，比方说第7航班，它的航程是16，比第1到6次航班
的航程都长，所以第7航班是个航程纪录航班。今天我们已经知道的航
程纪录航班有118个，航程最长的是2234047405400065次航班，它的
航程是1871，这是Eric Roosendaal发现的，他有个个人网站
http://personal.computrain.nl/eric/wondrous/，
里面有各种各样关于3x+1问题的信息，下面的记录也都来自这个网站。

同样的，如果一个航班的保持高度航程大于所有它前面的航班的保持
高度航程，我们就把它叫作“保持高度航程纪录航班”，比方说从上
面的表中我们看到第7航班也是个保持高度航程纪录航班。今天已知的
保持高度航程纪录航班有30个，航程最长是1008932249296231次航班，
它的保持高度航程是1445。

最大飞行高度记录航班就是那些最大飞行高度记录大于所有它前面的
航班的那些航班，现在已知的有76个，最大的是10709980568908647
次航班，到达了350589187937078188831873920282244的高度。

对于一个固定航班N，考虑它在1着陆之前所作的变换，如果把其中除
以2的变换称为“偶变换”并记为E(N)，而把乘以3再加1的变换称为
“奇变换”并记为O(N)。数学家已经证明，O(N)/E(N)<log2/log3。
我们注意到，对有些航班来说，O(N)/E(N)非常接近于log2/log3≈
0.63092975……。有猜想认为它会越来越接近这个数字（也有相反的
猜想，认为不会无限接近），所以大家为此设立了另一个纪录，就是
这个比值比所有以前的航班更接近log2/log3的航班。这样的纪录不多，
现在已知的有15个，其中最后一个是N=100759293214567，I(N)/P(N)
≈0.604938。值得一提的是N=104899295810901231，它的这个比值
还要更靠近，达到0.605413，但是我们不知道它是否是一个纪录，也
就是说，我们不知道所有比它小的航班里，是否还有比这个比值更靠
近log2/log3的。

我们知道，对于任何p，总有至少一个航班，它的航程是p：
2^p→2^p-1→2^p-2→……→4→2→1
但是一般并不需要这么大的航班，就可以达到航程p。在2000年有人提
出要找到最小的航班号，使得它的航程恰好是2000。现在最好的纪录
是第67457283406188652次航班，但谁都不知道这是不是最小的航程为
2000的航班。

计算一个航班的算法是非常简单的——只要除2或乘3加1。但是为了检
验大量的和航次巨大的航班，巧妙的编程方法是非常重要的。上面的
那些纪录都是由几台类似于我们平时使用的那样的计算机得到的结果。
但是如果没有好好地思考和编程，光是硬算，那么使用最先进的计算
机恐怕也得不到这样的结果。

为了验证一个航班的确在1上着陆，并不一定需要把结果计算到1。如
果你已经验证了所有航次小于n的航班都在1上着陆，那么对于第n次航
班，你只要把结果计算到一个小于n的数m就可以了——我们已经验证
过第m次航班在1上着陆。事实上，如果我们只要计算到一个以前的航
班飞行时到达过的数值就可以了，当然这需要记住以前已经到达过的
比较高的高度，这里也必须巧妙地编程使得这样的记忆所使用的内存
比较少。

更重要的是使用数学方法去减少计算量。比如说，任何n=4k+1的航班
最终都会飞到一个比n更小的高度。首先这是奇数，我们乘3加1得到
12k+4，然后连除两次2，就有3k+1<n。所以我们没有必要费功夫去验
证4k+1型的航班。另外偶数次航班第一次变换就被除以2，降低了高
度，所以同样也不需专门验证。只用这样一个小技巧，我们就使计算
量减少到原来的25%。

如果按照这样的思路下去，我们同样不需要考虑16k+3型的航班，只
要考虑到前面的飞行记录：
16k+3→48k+10→24k+5→72k+16→36k+8→18k+4→9k+2→……
而9k+2<16k+3。

我们可以这样追踪下去，考虑256k+i型的航班，其中i取0到255，那
么我们会发现我们需要考虑的类型只有i=27、31、47、63、71、91、
103、111、127、155、159、167、191、207、223、231、239、251、
255。这样我们要作的计算只有最初的8%不到。

而Eric Roosendaal得到上面那些纪录的程序，是建立在对65536k+i
型航班分析的基础上的，其中只有1729种航班需要真正的检验（只有
原来计算量的2.6%）。他的程序还使用了其它的算术技巧，以及可以
同时计算好几个航班。Tomas Oliveira e Silva进一步改进了这些技
巧，从而使得他成为现在3x+1问题验证的世界纪录保持者（他的计算
从1996年8月开始，到2000年4月结束，其间使用了两台133MHz和两台
266MHz的DEC Alpha计算机）。Eric Roosendaal还在和其他人一起
合作进行计算（包括再次验证以前的结果），如果你愿意加入这个研
究项目的话，可以去访问上面给出的他的主页。

四、理论结果

只要稍微动一下脑筋，我们就知道3x+1问题和下面几个命题都是等价
的：
1)所有的航班的航程都有限；
2)所有的航班的保持高度航程都有限；
3)所有的航班中的偶变换的次数都有限；
4)所有的航班中的奇变换的次数都有限；
5)所有的航班的保持高度航程中偶变换的次数都有限；
5)所有的航班的保持高度航程中奇变换的次数都有限。

R. Terra和C. Everett证明了，“几乎所有的航班都会下降到它的起
始点以下”，也就是说“几乎所有的航班的保持高度航程都有限”。
这里的“几乎所有”是有确定的数学意义的，它是指：

——存在一个自然数n₁，在所有小于n₁的航班里，最多只可能有1/10
的航班，它们的保持高度航程无限；
——存在一个自然数n₂，它比上面的n₁要大，在所有小于n₂的航班里，
最多只可能有1/100的航班，它们的保持高度航程无限；
——存在一个自然数n₃，它比上面的n₂要大，在所有小于n₃的航班里，
最多只可能有1/1000的航班，它们的保持高度航程无限；
——等等等等……

这好象很接近证明“所有的航班的保持高度航程都有限”了，于是很
接近证明猜想本身了。但是好好想想，这个结论只不过是说明保持高
度航程无限的航班会越来越稀少罢了，它们还是有可能存在的……更
糟糕的是，这个结论一点也没有排除有其它循环存在的可能。

对于在1上着陆的航班，数学家们也得到了一些结果。他们证明了，存
在一个常数c，当n足够大的时候，在比n小的航班中，能够在1上着陆
的航班的个数大于等于n^c。在1978年R. Crandal首先给出c=0.05，虽
然小了点，但毕竟是开头一步；然后J. Sander给出c=0.3；在1989年
I. Krasikov得到c=0.43；1993年G. Wirsching得到c=0.48；最后在
1995年D. Applegate和J. Lagarias得到c=0.81。看起来我们越来越
接近c=1这个最终目标了。可是我们不知道现在用来得到c的方法是否
还可以再用下去，就好象在试图征服哥德巴赫猜想的过程中，陈景润
用来证明1+2的方法，似乎不能用来证明1+1了。

1995年的这个证明相当特殊。它使用了计算机程序来解一个十分巨大
的方程组，所以这个证明不能用手工来验证。在论文中，我们看见的
不是一个关于c=0.81的定理的证明，而是一个关于如何写出这个巨大
方程组的说明，和由程序计算出来的结果，以及如何使用这些结果来
解释c=0.81。其他的数学家如果想验证这个结果，必须首先看懂关于
方程组的证明和那些解释，再按照里面的说明来写一个程序（很复杂
的！），运行它，再看看结果是否和文章中的相同。目前四色定理的
证明也是如此，所以数学家对此很不满意。

还有一些结果是关于如果有其他不同于4→2→1的循环存在时，对这样
的循环的性质的研究。R. Crandal和N. Yoneda在1978年证明，如果
这样一个另外的循环存在的话，那么它的长度（就是在这个循环中数字
的个数，比如说循环4→2→1的长度就是3）一定要大于275000。1993
年这个体积增大到17087915，最近的结果是102225496。这些结果是
通过分析包括我们前面提到的各种纪录得到的，所以这些结果我们还
是不能完全通过手工来验证。我们看到，如果真有另外的循环存在的
话，那一定是非常非常巨大的！

五、启发式论证

数学中有一种叫“启发式”的论证方法，建立在估计和概率的手段上。
比如说底下的论证方法就是这个类型的：

“每个数字要么是奇数要么是偶数，如果随便取一个自然数，碰到奇
数和偶数的可能性是一样的。如果我们把一次航班中这一系列数值看
作是随机的话，那么使用奇变换和偶变换的可能性也是一样的，所以
平均在每两次变换中我们有一次是n→3n+1，有一次是n→n/2。所以平
均起来，每次飞行高度的变化就是乘以3/2，于是……就会越飞越高。”

这样的启发式论证就推翻了原来的猜想！但是这个论证显然比较幼稚，
因为它没有考虑到，每一次奇变换后随即而来的一定是一次偶变换，
因为如果n是奇数的话，3n+1一定是偶数；而每一次偶变换后随即而
来的却不一定是一次奇变换。J. Lagarias改进了这个启发式论证。
他指出，如果我们把奇变换后再作偶变换考虑在一起，那么这样得到
的结果可以看作是真的“很随机”。于是有1/2的可能性它是奇数，
有1/4的可能性是一个奇数的2倍，有1/8的可能性是一个奇数的4倍，
等等。于是飞行高度的变化就是以下变换的“平均效应”；

——n乘以3/2，这有1/2的可能（奇变换后再作偶变换的结果为奇数）；
——n乘以3/4，这有1/4的可能（奇变换后再作两次偶变换）；
——n乘以3/8，这有1/8的可能（奇变换后再作三次偶变换）；
…………

于是平均来讲，每次变换后高度的变化就是
c=(3/2)^1/2(3/4)^1/4(3/ ^1/8(3/16)^1/16……=3/4
所以高度在总体上来说应该是越来越低，每次大约低25%，最终降到
一个循环上（不过这个论证没有排除有除了4→2→1以外的其他循环）。
这个论证可以使我们使用论证中的模型来计算出，从一个自然数开始，
平均要多少步的这样的飞行（就是保持高度航程中奇变换的次数），
可以使飞行高度降到起始点以下。理论上的数值是3.49265……。如
果我们对3到2000000000（二十亿）之间的航班的保持高度航程中奇
变换的次数取平均值，我们得到3.4926……。这两个结果惊人的一致
性使我们相信上面的启发性模型是正确的。如果它是正确的，那么就
意味着没有保持高度航程无限的航班，于是3x+1猜想就是正确的，至
少可以得出没有飞得越来越高的航班的结论。

可是一个启发性论证，就算再有实验证据来表明它是对的，也只不过
是个论证，只能使我们对猜想的正确性更充满信心。它不能代替真正
的数学证明。比如说，数学家猜想在π的十进位小数表示当中，出现
0到9各个数字的可能性是一样的，对π的数值计算也强烈支持这个猜
想，可是如果没有数学证明，它还是得被叫做一个猜想，而不是定理。

用上面这个启发式的概率模型，我们还可以预半夜凉初透言，对于第n次航班，它
的最大飞行高度不会超过Kn²（对于某个常数K）。数值计算表明对于
K=8，这个公式是正确的（同样地，这可以让我们提出猜想，而不是证
明定理）。

六、会不会永远证不出来？

自从哥德尔发表了他的著名的不完备性定理以来，每次碰到一个十分
困难的问题时，数学家们就免不了疑神疑鬼——这会不会证不出来？

哥德尔的不完备性定理说，在包含皮亚诺的自然数公理的数学公理系
统中，总有不可证明的命题存在。公理系统的这种性质叫不完备性。
比如说，如果我们只取欧氏几何的前四条公理，那么平行公理是不能
用这前四条公理证明出来的，也就是说只有前四条公理的平面几何是
不完备的（这个例子不是很严格，因为欧几里德的公理系统在现代观
点下是不严密的，但是我举这个例子只是为了说明不完备性这个概念，
所以关系不大）。

所以说，如果我们只用皮亚诺的自然数公理，甚至再加上现代的集合
论薄雾浓云愁永昼公理系统，也有可能不能证明3x+1问题。甚至即使3x+1猜想其实是
错误的，我们也有可能不能证明这一点。比如说，我们可能发现一个
航班，我们对它进行计算，发现它飞得越来越高，但是无论如何不能
证明它永远也不会回到1上来。

当然无论什么数论问题都有可能搞得数学家们这样疑神疑鬼，虽然其
实是他们还没有发现证明。不过有一些蛛丝马迹表明我们有必要稍微
严肃点看待此问题，因为3x+1问题离不可证明的问题并不太远。

J. Conway（喜欢数学游戏的朋友可能会记起这个名字来，著名的生命
游戏就是他发明的）在1972年考虑了3x+1问题的推广形式。在3x+1问
题里，我们把数字除以2，然后得到了2种可能的余数（0或者1），按
照余数我们使用2个公式（除以2或者乘3加1）。Conway考虑了除以一
个固定的p，按照余数的不同（这时就有p种不同的余数）分别使用p个
公式的情况。然后他提出了一个类似“在1着陆”的猜想。他在论文中
证明了，这个猜想在集合论薄雾浓云愁永昼公理系统中是不可证的。

事实上，在任何一个包含了皮亚诺的自然数公理的数学公理系统中，
Conway的方法都可以定义一个类似于3x+1问题的不可证命题。当然这
不是说有一个在所有公理系统中都不可证的命题。“不可证”总是相
对于某公理系统而言的。当然，Conway的方法并没有说明3x+1问题本
身是不可证的，也没有说它一定是很困难的（事实上有些3x+1问题的
变种是很容易解决的），但是这毕竟说明，有些很象3x+1问题的命题
是不可证的，这把事情搞得很可疑。

1993年，法莫道不消魂国里尔(Lille)的基础信息实验室使用了Conway的方法来
演示一套基于逻辑规则的编程形式的威力。同许多数学中的例子一样，
先头看上去最没用的课题，会有很具体的用处。

七、各种变种

数学家总喜欢把问题推广，使它更抽象化和一般化，因为这样可以把
一种在具体某个问题上使用的方法的威力应用到一般的情况上去，从
而得到很有可能是出乎意料的结论。

数学家们首先考虑，如果把3x+1问题的规则运用到负整数上去，会产
生什么现象。他们发现了三个不同的循环：
1)-1→-2
2)-5→-14→-7→-20→-10
3)-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122
→-61→-182→-91→-272→-136→-68→-34
他们猜想，这就是所有的循环，而所有的负整数都会掉进其中一个里。

他们还提出了5x+1问题，也就是在奇数的情况下用5x+1来取代3x+1。
这下又有好几个循环：
1)6→3→16→8→4→2→1
2)13→66→33→166→83→416→208→104→52→26
3)17→86→43→216→108→54→27→136→68→34
但是5x+1问题中的第7次航班好象老在那里飞啊飞，怎么也跑不到一个
循环里去，但是谁都不能证明的确如此。

上面Lagarias的那个启发式论证使得数学家猜想，如果q是大于3的奇
数的话，对于qx+1问题，总存在至少一个航程无穷的航班，这看起来
很象是一个“反3x+1问题”。

还有许多其他的3x+1问题的推广，一些结果把它们和其它数学领域联
系起来，比如说素数理论，某些丢番图方程（求解系数为整数的方程
的整数根，比如著名的费尔马大定理就是一个丢番图问题），马尔可
夫链（概率论中的递归理论），遍历理论（一种关于函数混合递归的
理论）。

就算3x+1问题终于被解决了，看看所有这些变种，也够数学家们自娱
自乐上几百年的了。

相关链接

　　　　http://www.ieeta.pt/~tos/3x+1.html
　　　　http://personal.computrain.nl/eric/wondrous/

记得TJT同学曾经问过我(1-x)(1-x^2)(1-x^3)...(1-x^n)展开是什么样子。昨天不小心乱翻书，居然发现了！！

手算前几项，我们会得到1-x-x^2+x^5+x^7-x^12-x^15+x^22+x^26-x^35...

这个东西隐藏着什么规律呢？首先可以发现的一点是正负性是极有规律的——+--++--++--...数字上呢？我们将次数提出来，得到一个序列：

0 1 2 5 7 12 15 22 26 35 40...

然后再将相邻两项相减，得到一个新的序列：

 1 1 3 2 5  3  7  4  9 5...

发现了么？我们把奇数项和偶数项分开看，得到两个序列：

奇数项： 1 3 5 7 9 11 ...

偶数项： 1 2 3 4 5 6 ...

神奇吧！

来自：

 http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/commonalg/misc/strassen/strassen.htm

矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。若A和B是2个n×n的矩阵，则它们的乘积C=AB同样是一个n×n的矩阵。A和B的乘积矩阵C中的元素C[i,j]定义为:　

若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i,j]，需要做n个乘法和n-1次加法。因此，求出矩阵C的n²个元素所需的计算时间为0(n³)。

60年代末，Strassen采用了类似于在大整数乘法中用过的分治技术，将计算2个n阶矩阵乘积所需的计算时间改进到O(n^log7)=O(n^2.18)。

首先，我们还是需要假设n是2的幂。将矩阵A，B和C中每一矩阵都分块成为4个大小相等的子矩阵，每个子矩阵都是n/2×n/2的方阵。由此可将方程C=AB重写为:

　(1)

由此可得:　

C₁₁=A₁₁B₁₁+A₁₂B₂₁                           (2)

C₁₂=A₁₁B₁₂+A₁₂B₂₂                           (3)

C₂₁=A₂₁B₁₁+A₂₂B₂₁                           (4)

C₂₂=A₂₁B₁₂+A₂₂B₂₂                           (5)

如果n=2，则2个2阶方阵的乘积可以直接用(2)-(3)式计算出来，共需8次乘法和4次加法。当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为2。这样，就产生了一个分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2×n/2矩阵的加法显然可以在c*n²/4时间内完成，这里c是一个常数。因此，上述分治法的计算时间耗费T(n)应该满足：

这个递归方程的解仍然是T(n)=O(n³)。因此，该方法并不比用原始定义直接计算更有效。究其原因，乃是由于式(2)-(5)并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性，必须减少子矩阵乘法运算的次数。按照上述分治法的思想可以看出，要想减少乘法运算次数，关键在于计算2个2阶方阵的乘积时，能否用少于8次的乘法运算。Strassen提出了一种新的算法来计算2个2阶方阵的乘积。他的算法只用了7次乘法运算，但增加了加、减法的运算次数。这7次乘法是:　M₁=A₁₁(B₁₂-B₂₂)

M₂=(A₁₁+A₁₂)B₂₂

M₃=(A₂₁+A₂₂)B₁₁

M₄=A₂₂(B₂₁-B₁₁)

M₅=(A₁₁+A₂₂)(B₁₁+B₂₂)

M₆=(A₁₂-A₂₂)(B₂₁+B₂₂)

M₇=(A₁₁-A₂₁)(B₁₁+B₁₂)

做了这7次乘法后，再做若干次加、减法就可以得到:　

C₁₁=M₅+M₄-M₂+M₆

C₁₂=M₁+M₂

C₂₁=M₃+M₄

C₂₂=M₅+M₁-M₃-M₇

以上计算的正确性很容易验证。例如:　

C₂₂=M₅+M₁-M₃-M₇=(A₁₁+A₂₂)(B₁₁+B₂₂)+A₁₁(B₁₂-B₂₂)-(A₂₁+A₂₂)B₁₁-(A₁₁-A₂₁)(B₁₁+B₁₂)=A₁₁B₁₁+A₁₁B₂₂+A₂₂B₁₁+A₂₂B₂₂+A₁₁B₁₂-A₁₁B₂₂-A₂₁B₁₁-A₂₂B₁₁-A₁₁B₁₁-A₁₁B₁₂+A₂₁B₁₁+A₂₁B₁₂   =A₂₁B₁₂+A₂₂B₂₂　

由(2)式便知其正确性。

至此，我们可以得到完整的Strassen算法如下：

procedure STRASSEN(n,A,B,C);
begin
if n=2 then MATRIX-MULTIPLY(A，B，C)
else begin
将矩阵A和B依(1)式分块;
STRASSEN(n/2,A11,B12-B22,M1);
STRASSEN(n/2,A11+A12,B22,M2);
STRASSEN(n/2,A21+A22,B11,M3);
STRASSEN(n/2,A22,B21-B11,M4);
STRASSEN(n/2,A11+A22,B11+B22,M5);
STRASSEN(n/2,A12-A22,B21+B22,M6);
STRASSEN(n/2,A11-A21,B11+B12,M7);                     ;               

end;

end;

Strassen矩阵乘积分治算法中，用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。由此可知，该算法的所需的计算时间T(n)满足如下的递归方程:

按照解递归方程的套用公式法，其解为T(n)=O(n^log7)≈O(n^2.81)。由此可见，Strassen矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。

有人曾列举了计算2个2阶矩阵乘法的36种不同方法。但所有的方法都要做7次乘法。除非能找到一种计算2阶方阵乘积的算法，使乘法的计算次数少于7次，按上述思路才有可能进一步改进矩阵乘积的计算时间的上界。但是Hopcroft和Kerr(197l)已经证明，计算2个2×2矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再寄希望于计算2×2矩阵的乘法次数的减少。或许应当研究3×3或5×5矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n^2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界Ω(n²)。因此到目前为止还无法确切知道矩阵乘法的时间复杂性。关于这一研究课题还有许多工作可做。

本页最后一次更新于09/29/2004
email: starfish@vip.sina.com
©2000 算法与数据结构 http://algorithm.126.com/ 版权所有 转载请保留出处

数学小电影。花花绿绿的很有意思，不过我没看懂……看来我还是没有想象四维空间的能力

中文名称：维度：数学漫步
英文名称：Dimensions: a walk through mathematics
资源类型：DVDRip
发行时间：2008年
地区：美国
语言：英语
简介：

《维度；数学漫步（Dimensions: a walk through mathematics）》是两小时长的CG科普电影，讲述了许多深奥的数学知识，如4维空间中的正多胞体、复数、分形（fractals）、纤维化理论（fibrations）等等。

mkv格式，英语声道，双字幕（中文及英语）默认中文字幕。
在这里做个小说明，文件里已经包含了中英字幕，切换字幕由于不同的播放器有不同的方法。在此就不一一例举了，个人推荐win下使用kmplayer,linux下用smplayer.

同时提供其它语言的字幕下载地址。
第一章
第二章
第三章
第四章
第五章
第六章
第七章
第八章
第九章
结尾第二部预告
同时在这里给各位道个歉，因为个人的失误在制作的过程中，误把TR当成第九章节了，
因此发布的时候没有把第九章节发布出去，现在特补上第九章节。

同时放上第九章节的http下载地址，其它章节有必要的稍后也一并放上。
第九章节－证明 http下载地址

第一章：二维空间

喜帕恰斯 (Hipparchus)说明了两数如何描述球面上之点。
他接着解释了球极投影法：我们要如何在一张纸上描绘出地球呢？

第二章 : 三维空间

M. C. Escher 叙述那些二维生物试图想象三维物体的故事.

第三、四章：四维空间

数学家 Ludwig Schläfli 介绍了存在於四维空间中的物体，让我们见识到了一系列奇形怪状的四维正多面体。它们有著24、120、甚至600个面!

第五、六章: 复数

数学家Adrien Douady讲解复数. 以简单的术语解释负数的平方根. 变换平面, 图片形变, 创造分形图形.

Chapters 7 and 8 : Fibration

The mathematician Heinz Hopf describes his "fibration". Using complex numbers he builds beautiful arrangements of circles in space.

第九章 : 证明

数学家 Bernhard Riemann将阐述数学中证明的重要性. 他将证明一个关于球极投影的定理.

最后章节：
第二部预告

http://www.verycd.com/topics/333658/

云风的blog [color=Yellow]http://blog.codingnow.com/[/color]

如果人生有一个终极追求的话，我想那是真理。

一个人的时间是有限的，而真理似乎在无限远处，探索真理需要一代代人的努力，我们靠近一点，就可以让下一代人的起步更接近一些。这可能也是我们的前辈所想所作，所以我们需要学习前人留下的知识。避免又从原点出发。

知识不是数据库中的数据，一个 copy 指令就可以复制出去，永不消逝。书是媒介，大脑才是载体。人类的信息输入带宽极其有限，远低于大脑的处理能力（如果你能善用他的话）。浪费带宽这种稀缺资源是让人痛心的，故而我爱读书。

心情平静的时候读，神情气爽；烦闷的时候读，调节心境；闲暇的时候读，消磨时光；繁忙的时候读，释放压力。我有睡前读书的习惯。昨晚，天气不热，但似乎楼上楼下的人家都习惯性的开着空调。窗外滴滴嗒嗒的是冷凝管滴水的声音。突然想起李清照的两句词来：枕上诗书闲处好，门前风景雨来佳。

这次枕边放的是一本：《什么是数学 》。

早听说这是一本好书，也买了很久了。总静不下心读。前次顺着翻了前面几章，权当催眠读物了。枯燥归枯燥，但我绝对承认这本书写的相当不错。相比许多数学读物，他已经非常生动了。知识点一环扣一环，遵循严密的逻辑推理，而不是凭空跳出一个结论让你接受。或是想当然的认为你应该受过专业的数学训练，承认一些公认的定理和规则。

什么是数学？数学表达的是对象与对象间的关系，而不探究对象到底是什么。它在公理的基础上演绎，而不讨论薄雾浓云愁永昼公理本身的真假。数学是美妙的，作为人类思维的表达形式，反映了人们积极进取的意志、缜密周详的推理以及对完美境界的追求。

学习掌握数学，可以极大的帮助我们洞察这个世界。数学是一种思维方式，而绝不是解题训练。

当反思为什么我一方面喜爱数学，一方面又觉得满是公式的数学书读起来枯燥无比时。我意识到，虽然逻辑推理演绎是缜密而有趣的，但并非人脑天然的运作方式，这个需要后天的训练。当突如其来的逻辑推理需求超过当时接收者大脑可以承受的压力时，必然会导致疲惫和挫折感。也就是处理能力小于信息输入带宽的表征吧。

我的机械记忆力不太好，从小开始，我就拒绝接受没有弄明白的道理。一知半解的东西在脑海中也总是只能暂时停留。以至于我对数学的掌握只能是熟练运用初等数学，而对高等数学粗通皮毛。记得读大学的时候，我的数学老师是全校最好的老师之一。可惜那个时候沉迷编程，觉得了解一点混过考试就够了，错过了学习高等数学最好的时机。大学毕业后，大部分都忘记了。直到前不久，我能记起并运用的微积分与线性代数知识还都是高中时代自学的。现在还依稀记得大学头两年的高数课，老师讲的其实还是满清晰的，也不是填鸭式教学，悔不该当初不多下点工夫真正理解啊。

发自内心的学习欲望，无论从什么时候开始都不晚。

昨天随便一翻书，居然是微积分章节的第一页。这个巧合让我一直读下去。没想到一发不可收拾，直到天色发白，才恋恋不舍的合上书睡去。这时，已经把这一章读完了。

我想起我的数学观念被启蒙前的一些事情，那个时候刚上小学，父亲工作忙，我主要是母亲带着。上学前她教我识字，计数，画画等，但没有特别教给我系统的科学知识。入学后，除了课本上的东西外，没有人强迫我学习更多东西。我记得那个时候自己老是瞎想，比如远近，轻重这些物理概念。说起距离这个概念，可以说是天生自然的诞生的，不需要人教。因为距离是可以直接比画被直觉感觉到的。但是，面积的概念却很难自发的产生。这个问题曾经困扰过我很久，父亲告诉我，矩形的面积就是长乘宽。我接受这个结论，并承认它的合理性，但内心总觉得别扭。虽然我自己从这个结论推导出更多例如三角形面积公式等，但我对其根源却总是心存芥蒂。

有一次我想知道圆的面积怎么计算，在白纸上画了个圆去问父亲。他并没有直接告诉我答案。现在想想，向一个小孩子解释 Pi 应该不是件容易的事情。我继续自己去想：如果能知道铅笔尖的面积，那么我一点点的将圆涂满，数一下用了多少点，应该可以相当于圆面积吧？父亲看我不停的在纸上戳点，问出我的想法，笑着说，原来我儿子这么小就懂微积分了 当然，向小孩子解释什么是微积分是很困难的。那个时候父亲一定跟我解释过，不然我不可能对这个名词记得这么清晰。但是我也肯定没弄懂。

后来我知道，求面积其实是一种积分（积累微小的分片、我这样理解这个词）的过程。学会抽象思维后，我不再对矩形面积公式介怀。

这些亲身经历的故事告诉我自己，无中生有的构造出新的概念，对于一个没受过数学训练的人不是件容易的事。新的知识一开始应该给人有直观的感受，才容易让人记忆深刻。逻辑、分析、构作，则可以加强这些记忆并接受它们。

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

其实原本是想谈谈 欧拉数 e 的。跑题太远了，谁让我是在写 blog 呢，无所谓了。

e 是一个很出名的数字，但在大众，远不如 Pi 来的有名。它不够直观，不像 Pi ，可以表示半径为 1 的圆的面积。

有一年校园招聘的时候，面试一个数学系的本科毕业生，我的同事提了个问题：什么是 e ？未能听到满意的答案。

是啊，我们知道科学计算器上总有个按纽上标着 ln ，说明书告诉我们它可以用来取以 e 为底的对数；大多数计算机编程语言的数学库中总会提供一个 exp 函数，用于求 e 的幂；中学老师告诉我们 e 是自然对数的底；e 是 2.718281828459 ……

但是 e 到底是什么？。可为什么要选择这么一个特殊数字命名为 e ？书本上一定讲过、课堂上许多老师也讲过，可还是很多人事后忘记了。我在这里再谈一次不为过。

跟 Pi 一样，e 也可以从几何上给出一个直观的表示。不过这个图形不没有圆那么容易画出来。我们需要作 f(x)=1/x 的函数图象，是一个双曲线。在第一象限，从 x=1 到 x=e 之间，曲线和坐标轴之间所夹的面积正好的单位 1 。

这样的几何上的描述对并不够有说服力，因为它只是诸多函数图象中的一个，没有什么特别。下面我们得看看， f(x)=1/x 这个函数的特殊之处。

如果你认可微积分在现代数学中的重要地位，那么就会发现，对多项式求导是研究各种问题的一个重要手段（比如在经典物理学中，研究速度、加速度、距离等之间的关系）。借助初等数学的推理，我们就可以得到对多项式求导的公式（这里就不展开列出了，但是这些推导过程对理解微积分很有帮助，而且仅需要初等数学知识就可以做到）： x ^ n 的导数为 n * x ^ (n-1) 。

反过来，x ^ n 就是 x ^ (n+1) / (n+1) 的导数。这种逆运算，被称之为不定积分。

btw, 诚如《什么是数学》书中所述：简单地定义“不定积分”为导数的逆运算，这种做法是把微分过程直接和“积分”这个词结合起来。然后引进作为面积或者和的极限的“定积分”的概念，而不强调这里“积分”这个词指的是完全不同的东西。会大大有碍于学生的真正理解。我个人也是很反感强加的概念：直接定义这种逆运算规则是让人不可接受的。其实这其中隐示的东西，正是牛顿和莱布尼兹为数学做出的杰出贡献。是他们首先把前人已经为积分和微分上做出的工作结合在了一起，思想上做了统一。这里不展开讨论微积分，仅仅只是不想离题太远而已。

当我们考察 x ^ (n+1) / (n+1) ，当 n=-1 时，分母为零，公式将失去意义。那么对 x ^ -1 即 1/x 的积分会引出怎样一种函数，就变的非常有趣了。以下，我们就直接用 ln x 来表示对 1/x 从 1 到 x 的积分。而 ln x 的导数则为 1/x 。

根据微积分中的基本定理（可直观的用初等数学方法证明的定理），我们可以得到若干对数运算的法则。又因为 ln(x) 是 x 的单调连续函数，当 x=1 时值为 0 ，且 x 增大时趋向无穷大，这样，就必定存在一个大于 1 的数，当 x 取此值的时候 ln(x) = 1 。

这个数值就是被欧拉称之为 e 的东西。

当我们考察 y=ln(x) 的反函数、即 x=exp(y) 时，会发现 exp(y) 这个函数的值在 y 为有理数时，和 e ^ y 的值总是一致的。这一点并不难证明。既而很容易得到幂函数的公式 e^a * e ^b = e^(a+b) ，且可证明它对任意有理数或无理数皆成立。

整个研究过程，从对数推导出幂函数，从自然数推导到有理数再到无理数，借助微积分这个工具的帮助，都很容易的走过来。这样的过程，在中学时，老师则是从整数幂 a^n 开始，定义 a^(1/m) 的意义，从而将幂函数推广到有理数集。两种推导方式向比较，中学时我们学过的初等数学的方法就不那么逻辑缜密了。这里面微妙的地方在于，初等数学借助一个想当然的定义跳过了逻辑的断层，而微积分就是来弥补这个裂痕的。虽然微积分的解释得花更多的脑力去理解，但它可以充分让我信服。

在这些讨论中，对数函数和指数函数都是以数 e 为“底”展开的，所以我们也把 e 称之为对数的“自然底”，或是“自然对数的底”。继续把底数 e 推广到任意正数的变换是容易作出的，而 e 则是变换的根本。

e 在其中的地位，好象 1 在自然数中的地位一样。虽然日常我们用 10 进制计数，但 2 进制却只用 0 和 1 ，即无和有两个概念，就衍生出了一切。其余的符号都是冗余。现代计算机广泛应用 2 进制之前，莱布尼兹就已经对二进制推崇倍至。我们可以把 10 进制记数规则看作是 2 进制的一种衍伸，人类选择 10 进制只是因为碰巧生了 10 个指头而已，而 2 进制则是永恒存在的。

最终，由微分法则我们可以得到一个奇妙的结论：以 e 为底的指数函数的导数就是它自身，即自然指数函数与它的导数恒等。这一点，实际上是指数函数所有性质的来源，并且是它在应用上之所以重要的基本原因。

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

ps.以上的文字并没有涉及具体的推理和证明，那需要相当的篇幅。但我觉得期盼得到高等数学真谛而未入其门的朋友都值得去找出书来读懂。这些过程用初等数学的知识就可以理解。

最后忍不住再提一下“素数定理”。它由高斯发现，并被誉为整个数学中最著名的发现之一。

至今人类未能找出一个产生所有素数的简单公式，也没有找到求前 n 个自然数中所有素数个数的简单公式。但是考察素数在自然数中的分布规律时，却找到了些许规律。

高斯发现，在自然数 n 极大时，n 与 n 之内素数个数的比值，近似等于 ln (n) 。n 越大越接近。不过前者是两个自然数的比值，是一个有理数；而 ln (n) 是一个无理数。两者只会无限接近，而永远不会相等。

素数的分布的平均状态居然可以用对数函数来描述，这太有趣了。两个似乎无关的数学概念在事实上竟有如此紧密的联系，真是让人拍案称奇。