博文
证明(0,1)~[0,1](2006-06-03 20:29:00)
摘要：要证明(0,1)和[0,1]等势，就是要找到一个双射函数f:[0,1]->(0,1)，考虑函数f(x)=x，是一个f:(0,1)->(0,1)上的双射函数，而关键就是要在这中间加入0和1这两个元素。前面讨论过可数集，想想无穷饭店的老板在知道饭店已住满客人时又来了有限k位客人是怎么做的？没错，对于可数集完全可以做到，只要让所有客人往后平移k个房间号就可以住下了，而(0,1)的基是阿列夫1比可数集的阿列夫0要大，也就是说存在着一个它的子集是可数集。
这样一来思路就清晰了，从(0,1)中找一个子集A，使A是可数集，也就是一个无穷饭店啦，f(x)=x表示已经住满了客人，现在新来了两位客人0,1，要住下来，OK，所有客人往后移两个房间号搞定。A怎么找？其实怎么找都行，甚至我抽象的描述一下也可以，因为证明是要证存在，还是构造性的找出来比较好，设A={1/2,1/3,1/4,...1/n,...}，于是找到的函数就是：
g(x)=if(x==0) g(x)=1/2if(x==1) g(x)=1/3 //新来的两位客人住前两个房间if(x==1/n) g(x)=1/(n+2) n为正整数且n>=2 //老客人从n号房间搬到n+2号房间if(x属于(0,1)-A) g(x)=x //剩余的不变
双射已经找到了，故(0,1)~[0,1]，证毕。......
对无穷大的思考(2006-03-23 17:34:00)
摘要：无穷饭店在宇宙中有一个饭店叫无穷饭店，无穷饭店已经住满了人。一天，来了一个乘客要住店，怎么住？无穷饭店的老板非常聪明，他想到一个办法，设无穷饭店的房间号是0,1,2,...，那让所有住在i号房间的顾客改为住i+1号房间，那0号房间就空出来了。第二天，又来了n个乘客（n为某正整数），同样的办法，所有顾客只要往后移n个房间，这n个人就可以住进来。第三天，这回来了无穷多个乘客，这下怎么办？老板一拍脑袋，这样吧，让所有现在住i号房间的顾客都住到2*i号房间，这样就可以空出所有的奇数号房间，而且也可以住进无穷多个人。这个例子是以前数学分析的老师举的，其实这里的无穷只能限定为‘可数的’无穷，还有很多类无穷是不可数的。对于集合，可以简单的分成‘有限集’和‘无限集’，有限集很容易，有限个是很容易理解的，我们可以记集合的基为有限集的元素个数，它给人的感觉就是集合的大小。但对于无限集是否还有基的概念呢？首先是阿列夫0，这是一种基，是多少不知道，只是一个记号，基是阿列夫0的集合叫‘可数集’，定义为元素可以和自然数建立一一对应关系的集数。比如{正偶数}，{负奇数}，{整数}等。它有几个性质：1、可数集并有限集仍然是可数集2、有限个可数集的并集是可数集3、可数个可数集的并集是可数集第三个的意思是，虽然你给了我无穷多个可数集，但我可以把这些可数集按某种顺序排列起来，于是就可以建立与自然数的对应，结论就可以是无穷并集仍是可数集。利用3可以证明{有理数}是可数集。书上有证明，略。其次是阿列夫1，这也是一种基，是多少也不知道，同样是一个记号，也叫连续基数，它定义为实数集合R0={x|x属于(0,1)之间，x属于实数}的基。首先R0不可数，证明非常经典。首先把所有的(0,1)间的数全写成无穷小数，对于有限小数这样处理，比如0.23=0.229999...这样处理后所有的数都可表示成0.x1x2x3x4...的形式假设它是可数的，则可以排列成a1=a11a12a13a14...a2=a21a22a23a24......an=an1an2an3an4......并且这无穷多个数包含了全部(0,1)间的实数，现在再构造一个b=b11b22b33...方法是 2 aii==1bii={ ......
欧拉图与哈密顿图的充分必要条件(2006-03-07 08:50:00)
摘要：一、欧拉图 欧拉(Euler)是个绝顶聪明的家伙，当他在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动，Konigsberg城中有一条名叫Pregel的河流横经其中，在河上建有七座桥，他们在每个星期六作一次走过所有七座桥的散步，于是就热衷于这样一个问题，可不可以从一个起点出发，经过所有桥一次，最后又回到起点呢？这就是有名的七桥问题。 图1： http://www.lmedu.com.cn/Img/Content/2004-4-20/20044209342.gif 如果用结点表示四个位置，用弧表示七座桥，那就成了图论的一个问题：从任意一个结点出发，经过所有的弧一次且仅一次，最后又回到出发点，是否存在这样的环路？ 图2： http://www.lmedu.com.cn/Img/Content/2004-4-20/200442093412.gif 欧拉为此想到了一个非常简单的方法，确定在什么样的条件下有上面那样的性质，这样的图也就叫欧拉图。 无向图G(V,E)是欧拉图，当且仅当： 1、图G所有结点强连通 2、图G所有结点的度皆为偶数 它的证明也非常简单，必要性很显然，充分性可以用数学归纳法，不多说了。二、哈密顿图 类似的问题还有哈密顿图问题，哈密顿图是这样的图，从任意一个结点出发，经过其它所有结点一次且仅一次，最后又回到出发点，是否存在这样的环路？这样的问题最开始叫做邮差问题，当邮差递信的时候，总是是希望走这样的环路而不重复去同一个地方，这样看上去简单的问题实际上并不简单。 确定哈密顿图的充分必要条件到目前还没有，只有必要条件或充分条件（书上这么说的），这似乎是告诉学数学的人努力去找到这样一个充分必要条件，就像在数学分析里柯西为函数收敛找到的充要条件而成为收敛原理一样，从而更加深刻地认识这样的数学问题。但我有不同的想法，数学应该更注重美，从哈密顿图的定义看是非常简单的，现在有必要条件，那就是要了解它的性质，现在也有充分条件，那也可以用来判别哈密顿图，为什么要寻找形式上更加复杂的充要条件呢？给原本形式简单的数学问题套......
树的计数公式推导(2005-10-20 18:12:00)
摘要：树的计数公式推导
首先提出树相似的定义，如果两棵树T1和T2相似，那么须满足下列条件之一：（1） T1和T2同时为空树（2） T1和T2不为空树，则T1和T2的所有子树分别依次对应相似（显然这里只讨论有序树，树的孩子有序）树的计数问题描述为：给定一棵树的结点总数n，由n个这样的结点能组成多少棵互不相似的树呢？为了解决这个问题，首先把树转换成二叉树，因为一棵树可以唯一的转换成与之对应的二叉树，转换的方法是二叉树中的左孩子表示树中的最左孩子，二叉树中的右孩子则表示树中的相邻右兄弟，按这样的方法可以得到唯一的一棵二叉树，且它的根结点没有右子树（因为树的根结点没有兄弟）。根据一一对应关系，树的计数问题可以转换成等价的二叉树的计数问题，这使讨论更加方便容易。设n个结点可以表示的二叉树计为bn，先从简单的开始：如果n=0，显然b0=1如果n=1，显然b1=1如果n=2，b2=2 N N / \ N N如果n=3,b3=5如果n再大一些，就很难绘出来了。当n>1时可以得到一个递推公式，此时有一个根结点，剩下n-1个结点可以用来构成两个左右子树，设左子树有i个结点，则右子树就有n-i-1个结点，由左右子树的不对称性（前面提到只讨论有序树），所以有b[i]*b[n-i-1]种构成方法，当i取值不同结果也不同，所以所有的构成方法为各种i值情况的和，所以bn=∑b[i]*b[n-i-1]，i从0取到n-1所以整个数列可以递推的定义为：b[0]=b[1]=1b[n]= ∑b[i]*b[n-i-1]，i从0取到n-1
为了求出bn的通项，需要引入构造函数B[n]，在这之前首先提一下广义的二项式定理。
二项式是这样的形式：(a+b)^p，a+b为一个代数和形式，p为非0的实数。作函数F[x]=(a+x)^p，由幂极数在x0=0处展开F[x]得：F[x]=m0+m1x+m2x^2+…+mnx^n+…其中mi=F^(i)[0+]/i!，F^(i)[0+]定义为F[x]的i阶导数在x=0处的值或者极限，且0!=1，0阶导......
称小球问题的数学证明(2005-08-16 23:29:00)
摘要：[转自CSDN]由网友feng5166(枫之羽)间接提供
【问题描述】
十三个球看上去一模一样，但其中一个质量不同（不知道是重了还是轻了），现在有一个天平，要求给出一种操作的方法，使得在不超过三次之内把这个球找出来（排除一切偶然情况），给出必胜策略。
【推广到N个小球】
有N个小球外形无区别，但是有一个在质量上与其他的球不一样。用天平称最少m次一定将不同的球找出来。显然随N增大，m不会减小。现在想解决的问题是对于任何给定的次数m,找出在该次数下能解决的最大的N值,用Nmax来表示。并给出对应于(Nmax,m)的一种解法。
【关于所能解决的上限】
现在来求m次所能解决的上限Nmax(m)问题。
为解决这个问题，我们给出几个引理。
引理一：无论加上什么其他的附加条件，只要k个球中的任一个都有可能是坏球（概率不
为0），则当k>3^L时，称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球,
除k个未知球外还提供若干个标准球，以及k个球中某些的质量和大于另外一些的和等等，
只要在这些条件下k个球中的任一个都还有可能是坏球就可以是引理所说的附加条件。
证明：很显然，若k>3^L，则哪个球是坏球一共有k中情况，而称L次一共有3^L种情况，
由k>3^L知不可能一定分辨出哪个球是坏球。
引理二：如果另外在提供任意多个标准球（即在N个未知球外还任给标准球作"砝码"用）?br /> 则称m次最多能从N1max(m)=(3^m+1)/2个球中找出坏球来。
证明：对该引理的证明可以采用数学归纳法。
当m=1时，显然若只有两个球，则任挑一个与另外的标准球比较（额外提供的，不是
两个中的），若相等则是剩下那一个，若不等则是这一个。所以N1max(1)>=2。
而对于三个球的情况，如果第一次称用了两个或三个未知球，则无法判断出用
过的球中谁是坏球（只称一次），而如果第一次称只用了一个未知球，则剩下
的两个球无法区分。因此一次不能解决三个球的问题。所以N1max(1)<3。
由N1max(1)<3和N1max(1)>=2知，N1max=2。
设当m<=k-1时命题都成立，则考虑m=k的情况。
第一次称不能使用超过3^(k-1)个未知球，否则如果坏球在这超过3^(k-1)个
球中的话，由引理一，在剩下的(k......
幂极数在近似计算上的应用(2005-07-08 21:29:00)
摘要：今天数学分析考完了，趋着这两天数学感觉还在，就简单谈谈极数在计算机中近似计算的简单应用吧。
极数是一种和的形式，注意只是一种形式，至于它到底是否具有和的意义，还需要数学上的证明，如
∞
∑x^n=1+x+x^2+x^3+...+x^n+...
n=0
也称为无穷极数。
它的意义一般不用管，这是数学研究的人的事，我们只记住它的形式，即一般是具有和的意义的。
极数的一个性质就是收敛或发散，收敛是我们想要的，如
∞
∑(1/2)^n就是我们中学熟悉的等比数列的和，它的和极限是存在的，
n=0
也就是说它收敛于S。
还有x项的级数叫函数项级数，它收敛于一个函数S(x)，反过来我们称极数是S(x)的极数展开，正如泰勒公式一样，将一个函数展开成多项式的和。
形如
∞
∑an(x-x0)^n
n=0
的极数称为幂级数，也就是一个在x=x0点展开的多项式，对于计算机来说多项式意味着只需做加法和乘法，而它却可以表示很多比较复杂的初等函数。
对幂级数来说，收敛半径R指的是它的收敛范围，如果它是在x0点展开，则当x取(x0-R,x0+R)时一定收敛于S(x)，若x取(-∞,x0-R)和(x0+R,+∞)时一定发散，如果取端点x0±R则不一定，需进一步判断。
R如何求，我不讨论，我只介绍用这样的方法算几个函数的展开。
1、求exp(x)的值，即以e为底，x为指数的函数值。
按泰勒级数展开：
exp(x)=1+x+x^2/2+...+x^n/n!+...
∞
=∑x^n/n!
n=0
所以可以用来近似计算：
double exp(double x)
{
int tag=0;//标记x
double s=0.0,a=1.0,n=1.0;
if(x<0){tag=1;x=-x;}//若x<0，进行标记
while(1)
{
s+=a;//累加求和
a=a/n*x;//递推法
if(a<1e-10)break;//精确值
n+=1.0;
}
if(tag)s=1/s;//若x<0,exp(x)=1/exp(-x)
return s;
}
它的收敛半径是无穷大，什么数都能对付。
2、求ln(x)的值，即以e为底，x的对数函数值。
按ln(x)在x......