博文
数独的基本玩法和解题模式(2008-05-11 23:54:00)
摘要：学了很久数独，同是一个人工解独的爱好者，也是计算机解独的爱好者，另外还是一个解法研究的爱好者，写下一些感想，只希望有更多的人来玩这样一个好玩的游戏，数学游戏。
1 数独的基本玩法
第一次接触数独的人，恐怕都有一个想法，这个太难了，我要试多少次才能全部填出来？其实错了，数独绝对不是试着填填数字的小游戏。所以大多数人，都不愿意去接受它，觉得它太繁琐，太复杂。其实是一个方法问题，因为一些基本的方法还不了解。我有一个愿望，做一个数独软件，一个真的能让人一步一步了解数独学习数独的软件，让更多人为这个游戏疯狂。
问：玩这个游戏，需要什么知识？
答：1，逻辑推理；2，逻辑推理；3，还是逻辑推理。
数独的定义里除了约束条件外，还有两条规则：
1，任何数独的解都是唯一的
2，数独是完全可以依靠推理，来一步一步确定数字来完成的，而不是乏味的‘猜测’+‘试探’
所以玩数独有一个心态，就是不要‘猜’，而是相信自己的推理。推理即‘解法’，有简单的，有复杂的，这和认识和学习数独的过程有关，比如有人一上来就学‘X环’，它已经习惯这个手段是‘基本方法’，那也没办法，每个人解数独的方法都不同，主要依赖的模式也不同。以下介绍一些基本的方法，我会把有些方法进行总结和归纳，有很多是异曲同工的，我会挖出方法背后的原理，同时进行一定的扩展。
a 直观法
这个名字很奇怪，言下之意，就是直接用眼睛看，就能看出来，很直观。它的基本出发点就是：在一个区域里，如果只可能位置p上是x，那x一定就在p上。听上去很废话，对，任何数独的基本出发点都很简单，关键是，你能不能运用它在一个数独题里去解题。运用这个方法解题的关键是，在各种区域间进行交运算，比如在一行上有数字3，那它将影响它所在行上的并排三个宫内的数字，那些与这一行相交的区域就不会再出现3了，这样对区域有意识地进行交运算+排除，你就有可能把另外一个区域中很多的位置‘否定’掉，那剩下唯一的位置，自然一定是3，填上去。如图1示：
图1
G1=3 => 第1列的其它位置不能是3，和第1宫求交后A1,B1,C1不可能是3，同理由A8,B5上的3可以得到第1宫中绿色区域内没有3，那么3一定在红圈所示位置C3。它的主要过程就是，考虑一个区域（行，列和宫），借助其它位置的数字排除这个区域内尽可能多的位置，从而最后确定只可能填的位置。
如果为每个格子......
计算机产生的随机数[1](2008-05-03 01:23:00)
摘要：写在最前面。我有一个朋友，一个女程序员，她的业余爱好是写小说，我看着她的小说里栩栩如生的人物觉得很了不起，她的脑子里可以想这么多好玩的人和事，于是我问，你为什么写小说啊，她只是简单的回答，我只是想写点很好的东西。我写不来那些，但我也希望我写的东西很好，我尽全力。
这篇由几个帖子引出，也是一直争论的焦点，std::rand()的性能怎样，随机数如何才算‘随机’，随机数如何检验。
它们是：
http://www.programfan.com/club/post-273908.html
http://www.programfan.com/club/post-274446.html
1 随机数的应用
随机数应用在哪些方面？std::rand()有什么用？统计学在生产活动中有着非常广泛的应用，它深刻地影响到了科学界和人们的生活。工厂的产品检验，人口的普查，国家还有专门的统计局，资源能源等，几乎都离不开统计学。科学界，决策论，贝叶斯决策已经形成独立的理论，随机过程，计算机模拟，计算机访真，还有密码学，都是随着现代概率论和统计学的成熟而发展起来的一大批科学。
就计算机中的随机数来说，主要用处有2个：1，用于抽样的编号。这也是最原始和最主要的用途了，在没有计算机之前，人们是用随机数表来进行抽样的，做一个足够大的表，表中的数据是通过物理过程模拟得到，比如丢色子。比如，医学上有一种随机数表，叫乱数表，它是一个n*n的矩阵，每一个格子中填一个数字0-9，数字是混乱的，医学实验时，是这样得到随机数序列的，手指随便一指，指到一个格子，然后随机选一个方向，比如向右，然后延着这个方向读几个数字，组成随机数，然后将它平移到需要的范围内，比如，你要[0，150]的随机数，你得到的数字是378，那进行平移,378-150-150=78，就是78这个数。2，用于计算机模拟。比如统计计算中形成的一大类计算方法，蒙特卡罗方法，就是一种随机计算方法。比如，模拟退火算法中，会按当前温度和邻解和当前解的目标值差计算出一个概率值p，然后依这个概率p接受或者拒绝这个邻解，如果p=0.5，那就有一半的机会接受。再比如，遗传算法中的交叉概率和变异概率，都需要用到随机数来进行模拟。
2 随机数的经典产生
std::rand()算是比较经典的产生了。计算机产生之后，一开始只是将随机数表搬计算机的存储器，......
直方图均衡化的理解(2007-07-26 17:44:00)
摘要：其实数字图像处理的本质还是数字信号处理，但是还有一些广泛的知识可以利用，比如物理上成色的原理，人眼感知色彩的原理，形态学等，把这些原理的东西拿开就剩下数学了。
我看了半天书上表述的直方图均衡化，就是没弄明白，后来看了代码才恍然大悟，其实很简单。
定理：一维随机变量a~F(x)，则F(a)~U[0,1]，a从负无穷到正无穷，U[0,1]是标准均匀分布。
证明：（相反的思路）设b~U[0,1]，由定义，
0 x<0
P{b<x}={ x 0<=x<=1
1 x>1
设某值域为[0,1]的单调增函数F(x)的反函数是F-1(x)，则
考察F-1(b)的分布情况，由定义
P{F-1(b)<x}=P{b<F(x)}=F(x)
即F-1(b)~F(x)
令a=F-1(b)，则b=F(a)
有a~F(x)，且F(a)~U[0,1] |
这个定理说明了均匀分布的随机变量的地位，对于任意分布的随机变量，只要给出分布函数的反函数，就可能直接构造出来（不过大部分是很难有简单形式的）。
一张图片，可以看成是对现实景物的一次抽样，就是一个样本，样本有二重性，可以看成是随机变量，就某个特征，比如灰度，它有一定的分布，而直方图就是它的密度函数，均衡化就是先求出F(x)，把密度函数逐段求和就行了，再用F(x)作用每一个像素，将原图像的a，变换成F(a)，使直方图变得相对均衡。
实际实验效果比较恐怖，效果比较吓人，一个美女变成xxx，呵~另外由于是离散的变换，所以结果不会绝对均衡，有时甚至会严重失真。......
我写的简单矩阵类库 mat库(2007-07-14 02:50:00)
摘要：记得第一个跟我讲MATLAB的老师是数字信息处理的老师，他大概的意思是说MATLAB如何好，举个例子在MATLAB里做个转置就只要a'就行了，说用C语言还要循环套循环，麻烦~我当时就想，MATLAB好用还不是底层把事情都做好了，你只调用当然方便啦，我还是觉得C/C++才是最好的语言。
我想模仿MATLAB做事，有了我写的库，很多事会变得同样简单。
主要功能，用C++模板将已知类型数据组织成矩阵的形式，并提供基本的矩阵运算。
1，矩阵定义：
matrix<类型名> <变量名>;
比如定义一个double双精度的矩阵：
matrix<double> a;
2，矩阵的初始化：
从数组初始化：
double a[]={1,2,3,4,5,6};
matrix<double> ma(a,2,3);
构造出一个2 x 3的矩阵ma，其元素依次是：
1 2 3
4 5 6
从单个元素初始化：
matrix<double> a=0.0;
构造出一个1 x 1的矩阵，其元素是0
用size(h,w)成员函数指定存储大小：
matrix<double> a;
a.size(2,3);
构造出一个2 x 3的矩阵，元素值未知。可以接着用a=0.0;将所有元素赋成0或者其它值
用提供函数identify(T(),h,w)构造单位矩阵：
matrix<double> a=identify(double(),2,3);
第一个参数随便指定一个相同类型的值就行了，结果构造一个2 x 3的单位矩阵：
1 0 0
0 1 0
（和MATLAB里的eye相同）
3，矩阵的基本运算
由于这里的矩阵元素类型不一定为double型，所以不一定是用来做数值运算的，或者你也可以用其它你定义的类型，但有时是需要有+,-,*运算定义以及整数0，1的构造函数构造出0元和单位元的构造函数。有时你也可以把它想成一种容器（它现在的底层实现还不是很好），一种矩阵的容器。
3.1 选择运算
选择运算是最重要的，拿到一个矩阵要很容易选定它的元素或部分。
a,operator[] 选行（列）运算<......
解线性方程组的一些方法(2007-05-23 15:04:00)
摘要：第一大类是直接法，理论基础是高等代数里的矩阵和行列式，也是众所周知的消元法。
x+y=a
x-y=b
小学就开始会解了，所以消元法在每个人心里都很明白，计算机算法也相对简单和容易理解，有完全主元消去法，列主元消去法，高斯若当消去法（消去对角线下方元素的同时消去上方元素）等。
高斯列主元素消去法实现：
//高期列主元素消去法，ab为{A,b}增广矩阵
void gauss1(CMatrix &ab)
{
int h,w;
ab.size(h,w);
if(h+1!=w)//要求n阶方阵
return;
int n=h;
int i,j;
for(i=0;i<n;++i)
{
//从a[i,i]到a[n,i]找出最大元素所在行
int max=i;//max指向最大列主元素所在行
for(j=i+1;j<h;++j)
{
if(fabs(ab.elem(j,i))>fabs(ab.elem(max,i)))
max=j;
}
ab.swap(i,max);//交换行
if(ab.elem(i,i)==0.0)//det=0，计算停止
return;
//消元
for(j=i+1;j<h;++j)
{
ab.pt(i,j,-(ab.elem(j,i)/ab.elem(i,i)));
}
//将a[i,i]化成1.0
ab.mul(i,1.0/ab.elem(i,i));
}
&n......
FFT乘法和高精运算库(2)(2007-04-14 16:43:00)
摘要：
目前实现了，加，减，乘，乘方，阶乘和计算菲数，速度没有大幅度提高，唉，也没那么多时间做了，先放一放。（除法做得不好，太慢了，慢到不能用）
最后一次提升的快一些，因为我想到两个实数序列可以合并在一起，做为一个复数的实部和虚部，这样一起做FFT会快一些。推导很简单，公式是：
x(t),y(t)为N点实序列，设X(t)=DFT[x(t)] , Y(t)=DFT[y(t)]，记w(t)=x(t)+iy(t)，W(t)=DFT[w(t)]，于是由DFT的线性性质，有W(t)=X(t)+iY(t)，但是不一定就是W(t)的实部和虚部，为了由W(t)得到X(t)和Y(t)，是计算X(t)=(W(t)+W*((N-t))N)/2和Y(t)=(W(t)-W*((N-t))N)/2i。
这样一来，做一次乘法就只需要2次fft。
我的机子比较慢，测了几组数据，结果是：
Factorial Function Test (1.0)
_______________________
n! cost time (s)
1k! 0.028163
10k! 0.856568
20k! 2.215239
40k! 6.278020
80k! 16.574058
Test Date\2007\04\11
Factorial Function Test (1.01) [增加快速地址变换]
_______________________
n! Cost Time (s) Approximations
1000 0.025191 4.023872600770937735437 E 2567
10000 0.735035 ......
简单方法算pi和e，计算到小数点后面一万位(2007-03-29 15:20:00)
摘要：简单方法算pi和e，计算到小数点后面一万位
1， 计算pi(圆周率)
算pi的公式非常之多，下面是几个有趣的：
pi/4=1+(1*1/(2+(3*3/(2+(5*5/(2+…)))))) [布朗克连分式]
2/pi=(sqrt(2)/2)*(sqrt(2+sqrt(2))/2)*(sqrt(2+sqrt(2+sqrt(2)))/2)*… [韦达恒等式]
pi/4=(2/1)*(2/3)*(4/3)*(4/5)*(6/5)*(6/7)*(8/7)*(8/9)*… [华里达表达式]
pi*pi/6=1/1*1+1/2*2+1/3*3+… [欧拉等式]
虽然这些连分式、无穷级数、无穷乘积都收敛到pi或和pi相关的数值，但是收敛速度却各不相同，收敛和收敛速度是两个完全不同的概念。
现在PC机上很有名的SuperPi，采用了Gauss-Legendre算法，这个公式每迭代一次将得到双倍的十进制精度，比如要计算100万位，迭代20次就够了。虽然收敛速度是超线性的，但是随着展开的数据位数越来越高，迭代一次的代价会越来越大，这关系到高精度算法，实现起来相当复杂。高精度，这是个值得思考的问题。
在这里采用一个简单的公式计算，Machin公式：pi=16arctg(1/5)-4arctg(1/239) （可以把这个表达式输入到google上，然后google会告诉你结果是3.1415926）
下面从arctg(x)的展开出发，简单讨论一下这个公式。
可以从等比数列的极限开始：设|x|<1，1+x+x^2+x^3+…=1/(1-x)，等式左边是无限项，如果只取有限的n项，结果会是什么呢？这关系到一个余项的的问题，对右边的式子进行泰勒展开，有泰勒余项，于是：1/(1-x)=1+x+x^2+…+x^n+ x^(n+1)/(1-eps)^(n+1) （1），eps在0到x之间，最后的那个余项是进行误差分析的基础，也是决定收敛速度的式子。（1）只展开到有限项，于是对它两边进行代换得到，
1/(1+x^2)=1-x^2+x^4-…+(-1)^n*x^(2n)+ x^(2n+2)/(1+eps*eps)^(n+1)......
证明E的内部是开集(2006-12-01 21:51:00)
摘要：在书上看到的一个定理，书上留给读者证，我想了好久才想出来。
不知道下面这些CODE能不能作用，需要一个IE插件MathPlay观看。
定义：
0，邻域：在定义了正实函数p(a,b)满足距离定义之后，定义U(x,d)={y|p(x,y)<d}，称为x的d邻域
1，内点：如果存在x的邻域U(x,d)是E的子集，那x就是E的内点
2，点集的内部：假设记为$E^o$，定义为，$E^o$={x|x是E的内点}
3，开集：如果集合E，满足$E=E^o$，那么E就是开集。
试证：$E^o$是开集。
证明：由定义3，即证$(E^o)^o=E^o$
由定义1、2显然有$(E^o)^o\subseteq E^o$，于是只要证$E^o\subseteq (E^o)^o$
$\forall x \in E^o$ (1)
假设$x \notin (E^o)^o$ (2)
以下证出矛盾：
由(1)即
$\exists U0(x,d_0) \subset E$
由(2)即
$\forall U1(x,d) \exists x_0 \in U1(x,d) 且x_0 \notin E^o$
又即
$\forall U2(x_0,d) \exists x_1 \in U2(x_0,d)且x_1 \notin E$ (3)
于是矛盾慢慢出现了。
取
$U1(x,d)=U(x,d_0/2)$
$\therefore p(x,x_0)<d_0/2$
取
$U2(x_0,d)=U(x_0,d_0/4)$
$\therefore p(x_1,x_0)<d_0/4$
$\therefore p(x,x_1)<=p(x,x_0)+p(x_0,x_1)=3/4d_0<d_0$
$\therefore x_1 \in U0(x,d_0) \subset E$
$\therefore x_1 \in E$这与(3)矛盾，(3)由(1)(2)推出，故假设不成立。
$\therefore x \in (E^o)^o$
$\therefore E^o \subseteq (E^o)^o$
中国剩余定理与大衍求一术(2006-11-05 15:27:00)
摘要：前面提到的‘中国剩余定理’是老外对我们中国古代数学家对同余理论作的贡献的肯定而命名的，其实它包括两部分，一是《孙子算经》中的定理，二是这里所谫的‘大衍求一术’，但是总的来说，它是对一次同余式组的一类通用解法。
《孙子算经》中有物不知其数问题，它表示成现代数学形式是：
N=R1(Mod 3)
N=R2(Mod 5)
N=R3(Mod 7)
书中给出了这组方程的通解：
N=70R1+21R2+15R3-105P
并副上一首诗歌：
“
三人同行七十（７０）稀，
五树梅花二一（２１）枝。
七子团圆正半月（１５），
除百零五（１０５）便得知。
”
至于为什么要这么算，书中未作任何说明，实际上这一问题还是未解决。真正从完整的计算理论上解决这个问题的，是南宋时期的数学家秦九韶，在他的《数书九章》中提出的所谓‘大衍求一术’就是对这一问题的一般解法。
其实原理非常简单，拿前面的通式说明，为什么R1前的系数是70，用手算一下，它被5和7整除，但是被3除余1，也就是70=1 (mod 3)，于是70R1=R1(mod 3)，而对其它模为0，作成的和不影响其它的数，所以N是问题的解，可以从空间的角度理解，70,21,15就是那个通式方程组的基，随着R1，R2，R3取得不同，解都可以由他们的线性组合构成，而105是3，5，7的最小公倍数，即模他们都为0，是解的循环元。
而所谓的‘大衍求一术’就是求满足x=1(mod M1)且x|M2,x|M3...的x，方法是：先取(M2,M3,...Mk)的最小公倍数a，然后解方程ax=1(mod M1)，那么ax就是我们要求的R1前的系数，整体思想就是这样的，而在秦九韶的方法中非常复杂，但是拿现代的眼光看，这个问题已经解决，即我们熟悉的欧几里德算法（->EUCLID算法与RSA）。不再赘述。......
初等数论基础知识(2006-10-15 21:55:00)
摘要：以前听老师说，初等数论要到大四学，今天翻到一本书，不知道讲得全不全，原来就是余数定理那一块知识，回想起来初中的时候老爹就教过我，那个时候他说的是‘中国余数定理’。
这个定理呢是老外的叫法，叫“Chinese remainder theorem”，在中国叫“孙子定理”，源于《孙子算经》（这本书的作者是不是叫孙子，不清楚，应该不会，谁愿意叫这么个名儿），书中有这样一个题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”，小时候老爹跟我说的时候，我觉得这还不简单，不就列几个方程呗，然后就不知道怎么列，还要设商，三个商不知道，加一个未知数，四个未知数三个方程，怎么解？
我们记这样一个运算：Mod，a Mod b的结果表示a除以b的余数，且是一个非负的小于b的数（a,b皆非负）。简单的理解就是，模运算是将整数打个折都射到[0,1,...b-1]这样一个区间上。
另外还有这样一个关系：≡，表示同余关系，a≡b(Mod m)就是说a Mod m=b Mod m，比如7≡2(Mod 5)。我们在自然数集上考虑这个关系，它满足：
1）自反性
a≡a(Mod m)
2）对称性
if a≡b(Mod m)，then b≡a(Mod m)
3）传递性
if a≡b(Mod m)，b≡c(Mod m)，then a≡c(Mod m)
也就是说它是一种‘等价’关系，它划分了[0],[1],...[m-1]这样m个等价类，也叫同余类。
同余式有一些非常有用的运算定律：
1）if a≡b(Mod m) and c≡d(Mod m) , then a+c≡b+d(Mod m)
2）if a≡b(Mod m) and c≡d(Mod m) , then ac≡bd(Mod m)
3）if a≡b(Mod m) k>0 , then ak≡bk(Mod mk)
4）if a≡b(Mod m) and d|a,d|b,d|m , then a/d≡b/d(Mod m/d)
5）if a≡b(Mod m) and d|m , then a≡b(Mod d)
6）if ca≡cb(Mod m) and d=gcd(c,m) , then a≡b(Mod m/d)......