博文
数独游戏(2007-02-14 16:10:00)
摘要：没最终做完的半成品，没写帮助文档，会玩数独的试一试，数独游戏规则相当简单，就是每一行，每一列，每一个小九宫内填1-9九个数字，不能重复，且要全部填满才算完成游戏。
下载：
http://www.programfan.com/wysoft/showwysoft.asp?id=2209
......
要好好学VC(2007-02-04 23:37:00)
摘要：记得原来听有人说VC是做底层的，像做个写字板程序就费劲，用VB简单之云云，所以我一直以为用VC做东西首先要有心理准备，准备好，累。
现在看来，别听那些，全是些半桶水，可能是某些做其它行业的人，用用VC，全都是瞎子摸象，你说去吧！
VC写个写字板程序可以不用写一行代码，单文档应用程序，再用AppWizard把CMyView改成从CEditView类继承，就搞定啦。还有像DDX/DDV啊，感觉真的好用嘛，VB可没做这么好。
也有人说它不是纯C++，说还是有过程化的影子，我觉得MFC封装得挺好，做开发也是全在设计类，哪里不是面向对象，偶尔用一用平台SDK，那叫底层~
VC本来就是又强大又好用。。。......
数独的难度评价(2007-01-26 14:46:00)
摘要：随便说几句，刚从网上找了一下一些比较难的CASE，似乎用计算机做也是‘口算’得到结果，于是我就想，看来我还是真不懂数独，数独毕竟是人玩的，要按游戏规则出牌。于是我就想如何评价一个数独的难度，以让人可以接受，因为人在玩游戏的时候是需要信心的，由易到难是一般做法。
数独的难度不好评价，因为它的各种局面互不相关，你别想用一种方法解决所有数独，这也是它的魅力所在，有人爱玩数独，因为他上瘾了，真的欲罢不能。
数独的推理性强，像一些数学思想，推理，假设，反证（找矛盾）都有影子，换成计算机，它也做类似的事情，推理和假设变成搜索，反证变成回溯，做一件数学工作，难度就体现在这些基本的工作重复了多少，越多越难，如果推两下就出结果，那就容易，所以……
就一般性的数独难度，拿两个指标来衡量，搜索次数S和回溯次数T，T越大越难，但和S也有关系，应该描述成回溯率，比如同样是回溯了10次，一个是20次的搜索，另一个是80次的搜索，那难度应该不同。换个思路，T可以看成是无效搜索，它一定是S的一子集，即T<=S，如果T=S就表示无解，回退到了一开始的情况，而难度应该和有效搜索有关系，有效搜索比率就定义为难度系数，即H=(S-T)/S，它是[0，1]内的小数，它越小越难，那对一个难度的评价，可以取它的倒数，或者负对数，怎么表示好，看实验情况。
其它因素。科学的评价，应该要考虑其它因素，像空格数，做为初学者就会觉得很重要，还有各个空格的不确定度，但是这些因素都会或多或少的影响到S和T。这里评价的前提是按照同样的搜索算法，那个算法和不确定度有关系，所以也可以反映出来。
总结出来，评价的具体方法是，运用偶的搜索算法试解一个数独，在调用dfs时S计数加一，在dfs退出时T计数加一，在搜索到第一个解时停止统计，计算H，给出S，T和H。......
数独(sudoku)的生成与破解(2007-01-25 21:06:00)
摘要：数独(sudoku)的生成与破解
最近在网上比较流行的智力游戏。笔者本人也玩过，可以下个模拟游戏试试，简单的还可以，太难就无从下手了。虽然偶脑子不好使，但偶是计算机科班出身，怕你不成，老规矩，编程破解。
首先，偶是第一次做数独的程序，可能程序不强，以后有时间再改进改进。望高手评析。
还是把数独游戏的规则说一说吧，或许你是刚刚听说这个名字的朋友。数独(sudoku)，起源于瑞士，于1970 年代由美国的一家数学逻辑游戏杂志首先发表，当时名为Number Place。及后在日本大力推广下得以发扬光大，于1984 年取名“数独”，即“独立的数字”的省略，在一个9x9的方格中，有81个小方格组成，然后又分9个大块，每块由3x3的方格组成，就是中国的九宫图，大九宫里面再套9个小九宫，共九九八十一个小格子，游戏开始前会有一些格子上写好了数，你需要在剩下的格子里填数，真到把所有格子填满，并且要求，任何一行或一列或者一个小九宫中没有相同的数字，当然你只能用1-9之间的9个数字。如下图就是一个数独。希望我解释清楚了，如果你还不清楚，用google搜索一下相关资料，点这里http://www.google.com/search?q=sudoku%20%E6%95%B0%E7%8B%AC&hl=zh-CN&lr=&nxpt=10.1471893728569764719035
好啦，言归正传。简单来说，我的破解法非常简单，就是超级无敌强硬大搜索，呵呵，别拿你想数独的那套来让计算机想，它比你可笨得多了，它只会照程序做事，做得快而已，快就是它的本事，其它的一概不会。
核心算法：深度优先搜索（其它形式的搜索也可以）
数据结构：如果用递归的形式写深搜，定义在函数dfs里的所有变量都可以看成是这里的数据结构，因为它们自动地被系统压入栈内，所以，省了，你唯一要做的就是一个二维数组，存放当前数独的状态。
当然有了这些，偶还不敢动手做，如果你做过马遍历的程序，大概会有点怕，那才8x8，这里是9x9，不来点‘启发式’谁敢动手写程序，有可能一个数独来几千几万个解，一个解要搜80层上下（估计），懂得树这个数据结构的人就会明白，80层是什么概念，1-9有9个数字，就是9叉树，至少是9^80量级的代价，什么？计算机反正算得快？也不行，再快的计算机遇到指数复杂度的程序......
初学MATLAB(2006-12-31 02:03:00)
摘要：我们数字信息处理的老师给我们顺带讲了一下MATLAB,我发现它很好用,而且很有用,对数学专业的学生至少很有用,而且功能实在强大。
MATLAB很容易上手，至少我这么认为，做软件的有一大忌：上手难，不管什么软件，系统软件，应用软件都是这样，就像微软用一只小老鼠横扫个人电脑市场一样，它赢就赢在‘那实在是太容易操作了’，让计算机这么一个半个世纪前还只能被少数精英掌握的东西现在却如此普及！难道你要在你卖电脑的时候，给用户解释，计算是怎么组成的啊，什么是磁盘啊，什么是文件啊，操作系统又是什么，哦，太多问号了，我不买了~~~~呵呵
发现现在中文著的《MATLAB教程》之类的书很多，其实没必要，这款软件也非常容易上手，简直是太容易了，并没有你想的那么难用。从网上抓个MATLAB7下来，装进你的计算机，大概要2G左右的，然后进‘开始’-‘程序’-‘MATLAB7’-开始你的奇幻数学旅行吧！打开手，它有欢迎窗口，然后会提示，你是First time user吗？是的，OK，点Getting start with matlab!，多么好的一本多链接式电子书啊，而且写得很好，也有sample，相当简单。
MATLAB的名字是两个词的缩写‘Matrix’和‘Labrary’，也就是‘矩阵实验室’，照帮助你的解释，也就是说，在这里，你最好把任何东西都想像成‘矩阵’，这里全是‘矩阵’，运算符也大部分是面向矩阵的，矩阵也就是一个元素集E的E^(n*m)空间，从本质上看它和E^N空间是对等的，只是思考的方式不同，比如如果n=1或者m=1就是一个数组，一个向量，如果n=m=1就可以‘看成’一个元素。
MATLAB不算是严格意义上一门语言，应该看成一个工具，但是它也可以写代码，它的程序语法比较简单，语法80%像C，20%像BASIC，也可以觉得是综合了各自的优点，反正目的只是为了让它更容易和更简单的表达，它的M函数很强大，让你轻轻松松做出很复杂的事来。
比较喜欢它的绘图功能，今天写了一个函数：
function earth(n,m,tag)
if(nargin < 2 || nargin > 3)
error('Format error! earth(n,m,tag)');
retur......
算法设计小结(2006-12-02 13:38:00)
摘要：前段时间借了本《算法设计》大致看完了，作个小结。
大的方向：分治与递归
发现这个是经典啊，递归是分治思想的实现方法。递归有两个方面，一个是递归方程，是设计分治问题的数学工具，于是就有主方法，主定理，这一块比较容易用来考试，像考研啊可能会比较喜欢这块内容，还有一个就是程序中的递归，这个需要技巧，先别乱用。
分治这条线下来，看最优问题中的两个常见范型，DP和贪心，她们的共同点是有最优子结构，怎么刻划最优子结构？就是递归方程，写成方程是最终目的，一开始可以简单表示，然后考虑需要考虑的量，然后转化成方程，有了递归方程再做程序，程序中不要用递归，而是打表，做备忘录或者直接递推，最后再由结果构造最优解，这样DP算法设计完毕。贪心的数学工具是拟阵，它是非空的，可遗传的，可独立扩充的一个二元集合，对拟阵有Greedy算法，这是有证明的算法，于是在贪心算法的具体问题上如果发现它满足拟阵的定义就可以直接运用贪心算法。贪心和DP的区别在于，贪心是从当前状态简单的做出最优判断，做状态转移，也可以看成是先排序（或大致有序）再一一进行选择，然后最优解就可以简单地构造出来，而DP是对当前状态进行一个计算，然后再构造最优集。贪心算法从理论上虽然不完美，但实际中有很重要的作用，像Dijkstra单源点最短路径算法，Prim算法等都是贪心。顺便提一下优先队列，这个数据结构可以用于最优问题中的选择算法，它可以动态的维护一个堆，而不是作相对费时的排序操作，而使算法性能提高很多。这一块分出来，叫面向数据结构的算法设计。此外，最优化问题远不仅如此，像LP等，那都是工科数学做的，应用方面多在工程上。
分治DP这一块有很多很多经典问题，有些问题本身都可以看成是算法设计范型，应用相当广泛，像LCS，归并，快排等。
递归这条线下来，看回溯法。回溯是王道啊。这里要了解解集和解集树的概念，在不是最优问题时或者没有最优子结构的最优问题里，就需要先构造解集树。这里和图论中的DFS有一些联系，实际上对图的一次DFS就是对它的某个生成树的遍历，其实质上也就是回溯。回溯就是先构造解的一部分，再决定是继续构造解还是退回，也就是回溯一词的本意。更广泛的来讲，回溯不仅限于DFS，DFS只是延深度方向延拓结点构造解，而回溯也可以延广度方向，或者是其它形式。理解了DFS，相当于理解了回溯的一大半，于是你就可以轻松的设计全排列、8皇......
证明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$
FibonacciHeap的C++模板实现(2006-11-23 17:01:00)
摘要：FibonacciHeap是一种优先队列，它的性能如下图所示。
就平均而言有很好的性能，所以在一些图论算法中可以用来作改进算法的数据结构，尤其是那些稀疏图，总之是很好的工具。下面以设计者的角度简单描述我设计它的过程和思路。
1、组织方法
采用C++提供的模板支持设计这个模板类，以达到很高的适应性。参数列表中只有一个类class T，它表示这个容器的元素类型，然后需要对它进行小的封装，封装的结果是得到一个内部小数据结构fibnode，如上图所示。
fibnode是组织FibonacciTree的结点结构，它包括了全部的指针和标记，整个FibonacciHeap就由它组成的，这个FibonacciTree在外部看来，只有一个min指针，指向它的根一层结点。
由于这样的组织形式，所以在析构的时候需要以递归的方式进行，递归的调用release()完成内存单元的回收。
这样的组织元素会遇到一个外部的问题，那就是内外数据的映射，由于元素是采用COPY的方式放入容器的，所以在内部是不知道哪个元素被封在哪个fibnode里，在内部确定一个元素的唯一方法就是找到它的fibnode指针，而为此如果做查找运算的话那它的优势将无法发挥出来。这个问题我没有在内部给出解决方法，原因是为了高适应性，因为这个T是未知的，所以我没办法给个O(1)的映射算法，如果用红黑树做Map，那会有O(lbn)的时间开销，那将使Decrease_Key()等调用的性能下降，唯一更好的办法是采用Hash表，而如果确定Hash函数又是和T有关的事情，所以这些事留给使用着在外部解决，根据具体的数据内容选择好的Hash函数，做外部的从T到const fibnode*的映射。值得说明的是，任何的fibnode指针都会在insert()过程的返回值中得到，如列程序所示：
Heap::FibonacciHeap<int> h;
const Heap::FibonacciHeap<int>::fibnode *x;
x=h.insert(100);
x将得到元素100的内部指针。于是可以将x作为Decrease_Key()的参数进行操作。
2、几个实现中的问题
从FibonacciHeap的算法描述到实现其实不是太难，很多操作都轻而易举的事，我额外定义的......
Priority Queue - Binary Heap(2006-11-14 17:14:00)
摘要：没什么好写的，都在《Introduction to Algorithms》里面，老外的教材就是厉害，不像我们国内，计算机类书籍不少，优点是：一、贵，二、内容不全，有时候要学个什么东西查一本书还不行，唉，写书都是为了赚钱，哪有什么好书。
前些天我借了本《算法设计与分析》的书，读着读着发觉怎么好像读过，一想，哦，是这本书里看过，那时候觉得看英文累，印象深刻，原来写中文书还有这么一招，直接翻译来就OK。老外不喜欢东搞西搞，一本书，比砖头还厚，把想说的全说完，全部搞定，简单，容易查阅，买一本一辈子带身边。哈哈，我刚好有一本，影印版的。
这个Priority Queue原来学《数据结构》的时候老师没讲，自己也没重视，现在翻出来学，发现很有用的。
一般的queue都是FIFO，元素间的前后关系完全取决于入队的时间，而不是某种数学上的偏序关系。而现实中的队列却是有优先级的，按优先级排个序，最先出来的应该是优先级最高的，这个时候的queue有个新名字，heap。
按我自己的理解，一个heap就是一个具有某种偏序关系的有序集合，它是一种半‘排序’化状态，我们感兴趣的就是第一个从heap里出来的元素，这时它是最小的，但是你要一次让第k小的出来，做不到，因为它内部组织数据的时候没有完全有序，并不是那么简单的。为什么只需要知道最小元素呢，因为它是一个Priority Queue。
像消息队列就应该是一个Priority Queue，有系统消息，各种用户级别的消息等。
另外像有的时候在需要动态维持一个有序集，同时又需要求最小元素时，很适合使用。像Dijkstra单源点最短路径算法中就可以用Priority Queue优化算法，还有最小生成树算法等。
Priority Queue有很多种，最简单的二叉堆，还有Binomial Heap,Fibonacci Heap等。它们的效率各不相同，优点各异，二叉堆在实现上比较简单，而且重要的操作，像Extract_Min()（取最小元素并移出队列）,Insert()等，都有较好的时间复杂度，但是缺点是Union()操作太废时，这本书上说是O(n)的，而且就给了一句话：By concatenating the two arrays that hold the binary heaps to be merged and then running......
Fibonacci数列的计算(2006-11-06 17:43:00)
摘要：Fibonacci数列F(n)递归地定义为：
1 n<=2
F(n)={
F(n-1)+F(n-2) n>2
列出前几项：1，1，2，3，5，8，13，21，34。。。
注意到这些数字没有，很多都是在大自然中出现的，我知道的少，不过你可以在互联网上搜一下，关键词：黄金分割。
没错，这个数列中体现了黄金分割，用数学方法很容易证明。首先它是发散的，但是不妨假设F(n+1)/F(n)是可以收敛的，设e=limF(n+1)/F(n)，由递推方程：F(n)=F(n-1)+F(n-2)，两边同除F(n-1)得（在极限情况下）：e=1+1/e，解出来就得e=1.618...，同时也得知它近似地相当于指数数列1.618^n，至少会以这样的增涨率增涨。
以下总结一下Fibonacci数列的计算方法。
1，直接递归计算。
int fibonacci(int n)
{
if(n<=2)
return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
它的计算效率同它的数值增涨效率一样是指数型的（O(1.618^n)），因为它会在递......