博文

数独的基本玩法和解题模式(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。它的主要过程就是,考虑一个区域(行,列和宫),借助其它位置的数字排除这个区域内尽可能多的位置,从而最后确定只可能填的位置。 如果为每个格子......

阅读全文(34316) | 评论:7 | 复制链接

计算机产生的随机数[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()算是比较经典的产生了。计算机产生之后,一开始只是将随机数表搬计算机的存储器,......

阅读全文(8263) | 评论:2 | 复制链接

直方图均衡化的理解(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,呵~另外由于是离散的变换,所以结果不会绝对均衡,有时甚至会严重失真。......

阅读全文(15932) | 评论:3 | 复制链接

我写的简单矩阵类库 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[] 选行(列)运算<......

阅读全文(6264) | 评论:0 | 复制链接

解线性方程组的一些方法(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......

阅读全文(15537) | 评论:6 | 复制链接

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  ......

阅读全文(8495) | 评论:6 | 复制链接

简单方法算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)......

阅读全文(21931) | 评论:5 | 复制链接

证明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$

阅读全文(5342) | 评论:6 | 复制链接

中国剩余定理与大衍求一术(2006-11-05 15:27:00)

摘要:前面提到的‘中国剩余定理’是老外对我们中国古代数学家对同余理论作的贡献的肯定而命名的,其实它包括两部分,一是《孙子算经》中的定理,二是这里所谫的‘大衍求一术’,但是总的来说,它是对一次同余式组的一类通用解法。 《孙子算经》中有物不知其数问题,它表示成现代数学形式是: N=R1(Mod 3)
N=R2(Mod 5)
N=R3(Mod 7) 书中给出了这组方程的通解: N=70R1+21R2+15R3-105P 并副上一首诗歌:

三人同行七十(70)稀,
五树梅花二一(21)枝。
七子团圆正半月(15),
除百零五(105)便得知。
” 至于为什么要这么算,书中未作任何说明,实际上这一问题还是未解决。真正从完整的计算理论上解决这个问题的,是南宋时期的数学家秦九韶,在他的《数书九章》中提出的所谓‘大衍求一术’就是对这一问题的一般解法。 其实原理非常简单,拿前面的通式说明,为什么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)。不再赘述。......

阅读全文(10290) | 评论:4 | 复制链接

初等数论基础知识(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)......

阅读全文(7635) | 评论:7 | 复制链接