博文
很久没来了,喘个气(2008-09-10 16:15:00)
摘要：对多个资源操作时,一次全部申请(等待),是最简单的防止死锁的方法,一次全申请并不会影响性能,如果占有时间不长的话~
Semaphore是对一种资源可同时占用的数量的描述,即被多少个线程使用,如果最大数为1,就是一个Mutex, binary semaphore~
中秋快乐~~......
数字追凶(2007-08-09 00:07:00)
摘要：英文名叫《numb3rs》，老实说，情节不怎么吸引人，比较吸引人的是那个主角太有才了，真是无所不知，而且都对破案很有帮助。
原来数学可以这么用，太牛了，真是偶像级mather。
图书馆借的一本书，叫《数学的源与流》，感觉也很不错哦。......
本站内容链接(2007-07-06 02:43:00)
摘要：您现在访问的是
算法驿站 powered by 编程爱好者网站
这个小站是我修读《信息与计算科学》本科时就自己所学到的所感受的东西留于笔下，开始不叫这名字，后来才慢慢感觉到‘算法’的威力，而‘驿站’是指作者我也是在学习，大家一起学习的这个过程。
有这样一种说法，先不说它的正确与准确性，至少还是有些道理的，就是，程序=数据结构+算法，程序就是一段指令，看看现在的计算机技术，从硬件的描述语言，汇编，高级语言，脚本，其实可以都认为是‘程序’，及程序就是计算机的全部，就算你是做硬件的人，你用CAD吧，你会从逻辑门开始设计吗？可编程逻辑器件，什么Intel8253之类，你做单片机，你会从汇编开始吧，或者是C语言，你不会去做那个片（我国国内好像还不能做'片'），拿到一堆APIs就开始干活，无非是2个8位拼成16位，还不就是做程序，好，你做程序员，就算你做系统程序员，你写个OS之类的，下面也是用别人做好的指令，你不会去设计微指令吧，流水线也不用管，cache也透明，剩下的东西，还不就是编程，做应用程序员，站在XP上干活，站在linux上干活，到你去做的事情，还是编程。我想说的是，‘程序’可以代替一个词‘逻辑’，而逻辑就是计算机的全部，至少当前的冯计算机，不同的只是大家所处的层次不同（越低级的人越少，但是我不同意越赚钱）。
而程序是=数据结构+算法，数据结构是精心地准备好数据，将那些信息以一定的形式一定的逻辑组织在一起，以使算法的效用达到最大，算法是所有程序的核心，可以看成程序本身，也可以这样比，算法是无形的，而程序是有形的，不管你如何实现，算法是发挥最大作用的东西，而程序是算法的某个实例。
做IT这行，只要是做技术的，只要把算法学好，动手能力强，不管做哪一行（计算机行也分很多）都会很吃香，剩下的只是工具的问题，实现的具体环境，熟能生巧嘛，越是高级的工具其实越容易上手，少数可能门槛比较高，但也都没有算法本身重要。
好了不多说了，本文是想把小站的内容做个链接，做个目录，以下是目录。
目录
1 基础算法
排序由浅入深（一）::选择排序
排序由浅入深（二）::交换排序
排序是算法的切入点，这两篇可能也没什么深度，现在看，那些个经典的排序算法，要时刻牢记于心，那会是一种算法设计泛型，比如快排，归并，基数排序，桶排等。
穷举搜索::回溯与深搜
分......
数独的难度评价(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。......
到底应该如何分类？(2006-08-22 20:06:00)
摘要：学了C++，就学了一些面向对象的机制，或者这门语言对面向对象提供的支持，但是否真的懂了面向对象，我觉得这是两码事。
什么是面向对象？我常这样问自己。现在struct可以改用class，成员可以是函数，一个类有自己的一组成员，数据+操作，类可以生成它的实例：对象！
我常常写‘class’，但不知道为什么要写它，同样的功能我可以不这样写，于是就开始反思为什么要C++？前段时间写黑白棋，一开始分了好多类，类之间要相互引用，于是就开了好多friend/friend class，到最后发现这样分简直是糟透了，或许不用C++还不会这么一团糟，再后来，对实现过程没有变，重新分类，分两个：一个是CReversiMap，一个是CReversiBot。从模型的角度看，分‘类’就是对实物建模，我有多少个实物，就建多少个类，想象一下两个人下棋，无非就两个类：人和棋，人和棋之间只传递一些棋面数据，分工明确，人负责想棋，然后告诉棋盘怎么走棋，棋盘负责接受走棋规则，移动（改变）棋面再等待另一方走棋。这样分类，类和类之间没有什么耦合，只通过接口打交道。所以也不用开friend。做为黑白棋程序设计也是如此，CReversiMap负责棋盘的数据处理，包括走棋的结果和棋盘的显示，CReversiBot就是机器人棋手，然后其它的像置换表、搜索引擎都是它的一部分，如果你要将它们分开方便管理，可以用不同的.cpp文件来写，比如我可以用Evaluation.cpp写它的估值函数一部分。
C++是一种建模思想，也可以从‘代码复用’的角度建模，但我觉得基于实物的建模更合理，算法的复用可以用模板，写成库，实际开发的时候还是基于实物建模。建模建得好不好可以看你不得以用了多少friend，friend破坏类的封闭性，本质上就是一种耦合。
我的一点感想，还在学习中。......
关于人工神经网络(2006-08-20 14:34:00)
摘要：今天有看这方面资料，一点点感想。
首先这样的模型，从功能上讲是很强的，人脑有神经元10^11左右个，我们就可以随心所欲的思考。人的视觉，触觉，听觉都是输入，肢体的控制神经，语言中枢神经和口腔发声控制神经都是输出，从本质上讲这样的抽象是根本的，所谓思维就是这个神经网络中的神经元的相互作用的过程。其次，什么是记忆？记忆就是‘反馈神经’，不知道这个名词准确与否。在《数字逻辑》中时序逻辑电路中也是这样的，输出反过来当成输入，构成一个‘反馈线’，反馈线上的电信号就是‘记忆’，简单的触发器就是这样两个反馈线的与非门构成的，触发器就是‘存储器’的基本元件，一个触发器可以记录一bit，内存上的Memory就是这样做的，同样在神经网络中也是这样，我们把回忆拿出来，重新思考，我们把昨天未下完的一盘棋拿出来继续思考，这就是反馈输入嘛。至于有没有硬盘式的存储器，就不清楚了，实际上，如果把我们的神经系统看成‘电系统’，我们什么时候断过电哟，你拿你的脑袋使劲往墙上撞，有可能会断一会电-_-
其次一点，就是怎么‘学习’？总的来讲，分两种，有教师的学习和无教师的学习，有教师的学习就像是一种训练，我想要这组人工神经网络（ANN）的功能是这样的，我就拿一堆的正确的[输入，输出]去训练它，拿输入数据得到真实的输出，再和理论输出比较，拿这个误差去修改‘弧’上的权值，最终使得它满足所有的‘学习资料’，就拿最简单的与逻辑门来说吧，输入神经元x1,x2（0,1），输出y=f(x1*w1+x2*w2-e)，测试数据是：
0,0,0
0,1,0
1,0,0
1,1,1
初使w1,w2,e随机得到，假设是7,4,5吧，第三组数据训练有误差，结果是7-5=2输出是1，于是修正
w1=w1+a(0-1)x1
w2=w2+a(0-1)x2
其中a是(0,1)间的值，表示学习的增益因子，用于控制调整的速度，就取0.5吧，于是修正后的w1=6.5,w2=4，还是不满足，再修正几次，直到w1=4.5,w2=4,e=5就满足了，于是它就会做‘与’运算了。
这里教师的作用就是提供‘正确’的训练数据，这样做学得很快，跟人一样，我们在学校里学习就是这样。另外一种无教师的学习，就会慢很多，会在失败中学习，想起以前英语老师教我们学英语就是要"Make mistakes & try aga......
[2006/07/24]逼角棋(2006-07-24 13:58:00)
摘要：昨天和爷爷聊天，聊到我唯一的一个幺嗲嗲（我爷爷的弟弟），那年他仙逝我才三岁，农村里老人家过逝也是喜事，叫白喜事，要整顿酒，很多客人很热闹，那时我很聪明，我爸说的，刚教我走逼角棋，就在那一天，我赢了另外一个嗲嗲一盘棋，然后就不再下了，赢了就跑！
逼角棋的棋盘是这样的：
一方棋子是圈，一方是叉，可以随手用粉笔在地上画一个，然后用任何不同的东西做棋子，规则是棋子延着边线走，当已方的两个棋子将对方的一个棋子逼到一个角时，就吃了这颗子，直到全部吃光时胜。
呵呵，小时候的游戏啊！
今天我的黑白棋程序终于有点进展了，总算是界面部分做得差不多了，今天还做了位棋盘，我不会PS，棋盘和棋子是一个朋友帮画的，画得很棒，非常感谢！
......
家里的旧电脑差点罢工(2006-07-15 11:40:00)
摘要：回到家这是第五天了，家里的一台电脑是赛扬466的，跑WIN98，因为不想太难为它，就算这样昨天她还是发了次脾气。
具体情况是这样的，那天下午想上会网，按了电源后，正在启动，启动画面都出现了，突然显示器上下晃得厉害，好像电视机没有信号的样子，然后显示器倒数秒，10秒钟后显示器shut down，于是我按了一下电脑的复位键，再次启动的时候，‘嘀~嘀~’，长长的响了两声，然后显示器没任何反应漆黑一片，然后我又按了一下复位键，响都不响，显示器照样漆黑一片，就CPU风扇在那呼呼的响。
没修电脑的经验，我的第一感觉是显示器坏了，因为系统在没有检查到标准输出设备时是不进行启动的，然后我就把显示器接显示卡的接头拔了，再试一次，显示器没有黑屏，而是显示了一条英文，大概意思简单来说就是‘No singal’，这和前面的现象不一样，于是我就觉得不是显示器坏了。
然后我就怀疑是显卡坏了，找来把螺丝刀，把显卡拆了，刷灰，擦金手指，忙了半天，再放回去，重启，还是不行，这样的试了好几次，忙得一头是汗，没有成果。我甚至要确定是显卡坏了。
后来一想，不对呀，要是没有标准输出设备，系统至少会有一声‘警告’的，现在是任何声音都没有，非常奇怪，于是我就想到，可能是内存条的问题，于是我就拆内存条，我有两个内存条，加起来192MB，我把显卡先弄好成原来的样子，再把其中一块拔出来，重启，还是一样，一声不吭，我又擦干净了放回去，咦，再开机它有‘嘀’的响声了，但是显示器画面停在了内存检查那步，还是卡死了，没有后文，不过有希望了，至少我知道是附加内存没有接好，系统检测的内存有错误，于是我拆下另外一条内存条，在我擦这个内存的时候试了下启动，系统可以正常进入，但内存只有64MB，这时才放下心来，至少其它的没有坏，如此折腾了半天，才确定是我手上这块内存条有问题。唉，修电脑真麻烦~！
后来？后来我擦了好多次，再把‘坏’的那块内存条装上去，又好了，一切正常了现在。电脑就像女人啊，不过我这台电脑算是脾气好了，已经是用她五六年了，就发过两三次脾气而已，其它时候还是挺和睦相处的。
2006/07/15......
重读《悟空传》(2006-04-11 15:01:00)
摘要： 《悟空传》是本好书，任何年龄的人读都有不同的收获，我中学的时候第一次读，全当成笑话书，也是完全可以的。
悟空，有一个好名字，同样也注定有不同的一生。它不像《西游记》把悟空太过神化绝对化完美化，这里的悟空更加有血有肉一些，同样也包括另外一些人物，比如八戒、玄奘等。从人物的角度看，这是一本不错的小说。
我觉得非常经典的一回，少年玄奘和云游法师斗法的一回：
－－－－－－－－－－
第七回
--------------------------------------------------------------------------------
她化成一只纯白百灵来到大殿窗边，这里最多的是山雀，但她怎么能变那种俗鸟呢？
殿内坐了一地和尚，中间有两个老的。一个持禅杖，身边还有包袱，象是外地云游到此的。另一个自然就是本寺的主持了。
“法明长老，久闻金山寺佛法昌盛，特来请教。”那持禅杖的老和尚道。
“天杨师父，不敢。”
“什么不敢？”天杨忽厉声道，“敢做不敢应么？”
法明长老一愣，才悟道这就开始论法了，于是一笑答道：“敢应不敢放。”
“放下！”
“我两手皆空，放什么？”
“那为什么还抓着？”
“心有灵犀。”
两人一问一答，问的凶答的快，只听的两旁僧人议论纷纷。
“你听懂了么？”“没有啊？”“哎，太高深了。”“真是玄机啊！”
小白龙只找那玄奘，却见他在人群之中，正向这边看着她。
小白龙心一跳，只觉脸要红了，忽发现自己是一只鸟，他看不见脸红的。
只见玄奘对她笑了一笑。
这人莫不是认得我？小白龙想，不可能的，他不过一凡人而已啊。
这边论答已到了关键时刻，两个老和尚头上都起了白烟。
天杨：“如何是禅？”
法明：“是。”
天杨：“如何是正法眼？”
法明：“不是。” ......
我喜欢的台球游戏(2006-04-11 14:49:00)
摘要： 昨天突然想玩台球游戏，我就想起了两三年前玩的雅虎的台球游戏，我敲cn.games.yahoo.com打开久违了的游戏页面，选了Break It Up全球游戏室。
这个台球游戏很朴素，８球美式打法，跟我家乡的街头台球打法差不了多少。
来这里打球的人都是来自全球各地的，我偶尔甩两句我那破Ｅ语和人搭话，我发现大多数说英语的人都很有礼貌，他们喜欢台球但不争强好胜，打出好球会称赞你，自己打得不好就会笑一笑。
我虽不太喜欢英语，但和人交流的感觉还不错，这里都会说省略语，比如：ns:nice shot,gg:good game,ty:thank you,thx,thanks,lol,laugh out l..(就是笑一笑啦)。
我非常喜欢台球啊，虽然是一个人参与，但感觉我像是教练，而桌上八个小球都是我的队员，我会一个一个进球，直到黑球轻松完成游戏，整个是一个完整的：小球、黑球还有我和我的球杆。
我想我变了不少，我从一个与人争强（当然也可以说成是上进）一个自以为是一个目中无对手的孩子，慢慢成熟起来。......