博文
Windows程序设计[1]-程序运行原理(2006-03-16 23:13:00)
摘要：今天又分了个新类出来，‘Win32编程’，其实Windows编程对我不算是刚接触，以前会一点VB，但VB对API封装得太深了，学C语言还是大一开始，决定更系统的学习一下。手上的书是《Windows程序设计》王艳平 著，感觉很不错。
废话少说，一起开始。
第1章是Windows编程基础，有对VC++的使用的以及Win32API介绍，略了。这里还提到代码风格，我觉得很重要。
记得大一的时候刚学完C，然后找本VC的书来看，硬是看不懂，像dword,bool，根本就没见过。书中推荐了一种写法：
1、原则，一个变量或者常量的名字应该越长越好，这里说的长是指所带的信息要足够，这和以前写的小程序不同，小程序里大可以用i,j,k,n之类的变量名，在大程序里就不能这样，在更大的工程里甚至还会用到命名空间，可见命名是很重要；那名字中要体现哪些信息呢？书中P6写到，‘本书规定的变量命名规则为：[限制范围的前缀]+[数据类型前缀]+[有意义的单词]’，限制范围是指变量的作用域，比如全局变量用g_(global)，m_表示成员变量，默认为局部变量等；数据类型也缩为一个字，如长整型n,布尔型b，举个完事的例子就是，int m_nErrorCode;(4字节长的成员变量，长整型，表示错误编号）。
2、现在VC中也用了很多的类型别名，用typedef...;定义的宏，如下：
typedef unsigned long DWORD;
typedef int BOOL;
typedef unsigned char BYTE;
typedef unsigned short WORD;
typedef float FLOAT;
typedef void far *LPVOID;
typedef int INT;
typedef unsigned int UINT
...
从中可以看出来，新的名字里隐含更多的信息，如P表示指针等，从现在开始要熟悉这些新名......
CRC循环冗余校验码(2006-03-16 11:17:00)
摘要：CRC（Cyclic Redundancy Check)循环冗余校验码
是常用的校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来‘确认信息’的困惑，书上提到红军和蓝军通信联合进攻山下的敌军的例子，第一天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信息，但是蓝军担心的是‘确认信息’如果也不可靠而没有成功到达红军那里，那自己不是很危险？于是红军再发一条‘对确认的确认信息’，但同样的问题还是不能解决，红军仍然不敢冒然行动。
对通信的可靠性检查就需要‘校验’，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。
CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。 它的编码规则是：
1、首先将原信息码(kbit)左移r位(k+r=n)
2、运用一个生成多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。
非常简单，要说明的：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是：
0+0=1+1=0,1+0=0+1=1
即‘异’则真，‘非异’则假。
由此得到定理：a+b+b=a 也就是‘模2减’和‘模2加’直值表完全相同。
有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。
例如： g(x)=x4+x3+x2+1,(7,3)码,信息码110产生的CRC码就是：
&n......
努力学习(2006-03-07 09:01:00)
摘要：一直都感觉良好，程序员然后是软件设计师，也很顺利，但这学期似乎没什么动力和目标。
手头上有一本《Thinking in C++》还没看完，上学期看得正爽的时候又非得准备期末考，我觉得很好的一本书；一本《Windows程序设计》也觉得不错。
原来一个中学同学找到我，说他想做个TIY（名字不给解释），简单来说是个比较智能的系统，说他有技术问题做不下去了，给我说过我觉得应该可以做出来，起码设计上的问题是没有的，实际编码不敢说。
这学期还得上华科的计算机专业双学位，周末被无情的夺走了。
对了，还有上次没过的CET4，damn!
看起来只有这些事情了。
努力学习，努力玩D2！......
欧拉图与哈密顿图的充分必要条件(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所有结点的度皆为偶数
它的证明也非常简单，必要性很显然，充分性可以用数学归纳法，不多说了。
二、哈密顿图
类似的问题还有哈密顿图问题，哈密顿图是这样的图，从任意一个结点出发，经过其它所有结点一次且仅一次，最后又回到出发点，是否存在这样的环路？这样的问题最开始叫做邮差问题，当邮差递信的时候，总是是希望走这样的环路而不重复去同一个地方，这样看上去简单的问题实际上并不简单。
确定哈密顿图的充分必要条件到目前还没有，只有必要条件或充分条件（书上这么说的），这似乎是告诉学数学的人努力去找到这样一个充分必要条件，就像在数学分析里柯西为函数收敛找到的充要条件而成为收敛原理一样，从而更加深刻地认识这样的数学问题。但我有不同的想法，数学应该更注重美，从哈密顿图的定义看是非常简单的，现在有必要条......
[代码]搬运工1(2006-02-08 18:25:00)
摘要：//: PORTER.H - PORTER HEADER - 2006.2 rickone
#include<iostream.h>
#ifndef _PORTER_HEADERFILE
#define _PORTER_HEADERFILE
class PorterMap
{
int width,height;
int *data;/* map data means :
0 - empty place
1 - goal place without box
2 - box on empty place
3 - box on goal place
4 - wall
0,1 r reachable
2,3,4 r unreachable
*/
int px,py;//porter place
int *reach;//mark the place where the porter now can reach
int boxnumber;
void dfsreach(int,int);
void reachmap(int,int);
public:
PorterMap(istream&);/*map data loaded from std input stream & its format(ascii) :
first line two integers for width & height -
&nb......
散列排序法(2006-01-27 18:51:00)
摘要：原来写过一篇文章在笔记本里，后来中病毒我把它格了，也没上网没机会发表出来，主要内容是关于一种比较另类的排序方法的，我叫它散列排序法。凭我的记忆把算法的主要思想写下来。
排序法总体上可以分两大类，一类是基于‘比较’的，主要有大家非常熟悉的：选择排序，交换排序，插入排序，归并排序等，其算法的复杂度也是用‘比较’的次数衡量的，其中有非常高效和优秀的‘快速排序’，可以说是他们中间的佼佼者，无论从时间还是空间上说都有很好的性能；另外一类也就自然是不基于‘比较’的，《数据结构》上介绍过一种叫‘基数排序’，我觉得也很经典，今天我要向大家介绍的跟基数排序很类似，原理也非常简单。
和基数排序的方法非常类似，也是采用分配和收集，而我管它叫‘散列’，因为就和hash散列表一样，而且我可以说当数据比较均匀的离散分布的时候，效率是非常高的，可以花很少的几次散列就得到有序结果。
[写在前面，也跟基数排序一样只适用于整数排序，因为不基于比较就只能从元素，即数的本身出发了。]
先举个例子，设待排序的数是：
4,2,5,1,3
我们排序的任务就是让上面一列数有序，看看我们要做的结果是什么：
1,2,3,4,5
于是我们的任务就是，把前面一列数各位数放到‘正确’的位置上去，使得它有序。而一个数和它的正确位置就是一个映射关系，于是我们就是要找到一个函数f(x)，使f(x)->‘x的正确位置’！
上面的例子非常简单，f(x)=x，但实际情况非常复杂，其实像这样的f(x)是不可能有很好的数学表达式的，别指望在这里做更多的努力。于是我着手找近似的f(x)，我的想法是，只要让它不会错太多就行了，不完善的可以慢慢做得完善。
实际上f(x)就是一个散列函数，只不过它不是用来检索而是用来排序，我给出一个f(x)=[(x-min)*(n-1)/(max-min)]，其中min是这列数的最小值，max是这列数的最大值，n是这列数的个数，那值域就会在[0,n-1]，再用这些值找散列存储位置。
在这样一个近似的f(x)函数下，会出些‘意外’的情况，首先可能会有两个元素得到相同的f(x)值，也就是‘冲突’，冲突如何解决？可以采用拉链法，类似于hash表的冲突处理。
为什么要用拉链法，其实可以从集合的角度看这个算法，实际上我是把整个数列看成一个集合，然后我着手把它分成更小一些的子集，......
[转]素数检验法(2006-01-11 18:01:00)
摘要： 数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个数是否是素数.
我们知道,费马小定理是现代素数判定方法的基础,如果该定理的逆命题成立那该多好,只要计算一下ap-a是否能被p整除,能则p是素数,否则p是和数.遗憾的是这只对1<p<341内的数成立,因为2341-2能被合数341整除,即费马小定理的逆命题不成立.前面已经说过像341这样的数叫做伪素数.
ARCL检验法改进了费马检验,它不再受伪素数的愚弄.这种检验法需要相当多的高深的数学知识.现在我还不能提供这个方法的详细情况,以后可能会的.在下面我将要讲的是n-1检验法和n+1检验法.
1.n-1 检验法
如果对于奇数 n,我们已经知道了n-1的素因子分解式,那么如下的n-1检验法将是有效的.在1891年,E.卢卡斯将费马小定理改进成对于检验素数很实用的形式,后来又由克拉奇科和莱默进一步改进:
定理一:设n>1是一个奇数,如果对于n-1的每一个素因子q存在一个整数a使得:
an-1 = 1 (mod n), and
......
[转]费马最后定理(2006-01-08 16:10:00)
摘要：费马定理
费马在1665年去世的时候，他已经是欧洲最著名的数学家 了，被称为"数论之王"。对于他，有两件事使人惊奇，第一，他是法学家，一生都在做官和议员，数学只是他的业余爱好。第二，他生平从未发表过一偏作品。他的著作是在他死后，他的儿子把他的文章、信件等整理后发表的。一位奇怪的老头。
费马在读丢番图的《算术》时，在有不定方x^2+y^2=z^2（x^2表示x的平方）那页的边上，写出了具有历史意义的一段文字 "但一个立方数不能分拆为两个立方数，一个四方数不能分拆为两个四方数。一般说来，除平方外，任何次幂都不能分拆为两个同次幂。我发现了一个真正奇妙的证明，但书上的空白太小，写不下。" 这就是说，费马已经声称，他证明了这一事实：不存在正整数x,y,z使得 x^n+y^n=z^n ,n>2。这个命题称为费马大定理，或费马最后定理。
自费马以后，这一问题困扰了世间智者358年。令人怀疑：费马当年真的证明出来，还是和世人开了一个玩笑？终于，费马问题由英国数学家维尔斯1995年解决。他的108页的论文《模曲线与费马大定理》在当代最有权威的数学杂志《数学年刊》上发表。1996年，维尔斯因此荣获"菲尔奖"。这是数学家心中的"诺贝尔奖"。费马大定理不仅是数论中的一个著名难题，更重要的是，它给整个数学带来了巨大财富，促进了代数数论和算术代数几何的建立，形成了现代数论无尽的前沿。......
[转]因数的分解(2006-01-08 15:57:00)
摘要：
因数的分解
来源：数学学习 作者： 日期：2005-4-9 22:38:14
数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个数是否是素数.
那么,如何去找合数的因子呢?试除法显然不适用于大数的因数分解,但实际上,目前所有用于素性检验和因数分解的方法中又都少不了试除法.一般在开始时它的运算并不慢,比如先用前一百万个素数去试除,如果找到一个因数,那么素性和因数分解问题就都解决了.若未找到,这时他如果是合数,就只有极大的因数,费马曾经找到了一种极其简单的对付这种情况的方法,以下就是这种方法的简单说明:
设n=uv,u和v都是大的奇数,不妨设u<=v令x=(u+v)/2,y=(v-u)/2.于是,0<=y<x<=n,且v=x+y,u=x-y故n=uv=(x+y)(x-y)=x*x-y*y或者 y*y=x*x-n,若能找到两个数x,y满足前式,则 n=(x+y)(x-y),即得出了n 的因数分解.费马本人就是用此方法找到了2027651281=44021X46061.可以这样进行,找出k>=√n 然后从x=k 开始,依次检验x=k+1,x=k+2...这些数是否能使x*x-n......
[转]怎样玩魔方(2006-01-04 06:33:00)
摘要：http://www.ahtvu.ah.cn/jxc1/zhykch/3002/wwww.files/c2.htm......