博文

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

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

阅读全文(8455) | 评论: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,呵~另外由于是离散的变换,所以结果不会绝对均衡,有时甚至会严重失真。......

阅读全文(16076) | 评论: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)构造单位矩阵:
mat