博文

很久没来了,喘个气(2008-09-10 16:15:00)

摘要:对多个资源操作时,一次全部申请(等待),是最简单的防止死锁的方法,一次全申请并不会影响性能,如果占有时间不长的话~ Semaphore是对一种资源可同时占用的数量的描述,即被多少个线程使用,如果最大数为1,就是一个Mutex, binary semaphore~ 中秋快乐~~......

阅读全文(4806) | 评论:1

数字追凶(2007-08-09 00:07:00)

摘要:英文名叫《numb3rs》,老实说,情节不怎么吸引人,比较吸引人的是那个主角太有才了,真是无所不知,而且都对破案很有帮助。 原来数学可以这么用,太牛了,真是偶像级mather。 图书馆借的一本书,叫《数学的源与流》,感觉也很不错哦。......

阅读全文(5270) | 评论:3

本站内容链接(2007-07-06 02:43:00)

摘要:您现在访问的是 算法驿站 powered by 编程爱好者网站 这个小站是我修读《信息与计算科学》本科时就自己所学到的所感受的东西留于笔下,开始不叫这名字,后来才慢慢感觉到‘算法’的威力,而‘驿站’是指作者我也是在学习,大家一起学习的这个过程。 有这样一种说法,先不说它的正确与准确性,至少还是有些道理的,就是,程序=数据结构+算法,程序就是一段指令,看看现在的计算机技术,从硬件的描述语言,汇编,高级语言,脚本,其实可以都认为是‘程序’,及程序就是计算机的全部,就算你是做硬件的人,你用CAD吧,你会从逻辑门开始设计吗?可编程逻辑器件,什么Intel8253之类,你做单片机,你会从汇编开始吧,或者是C语言,你不会去做那个片(我国国内好像还不能做'片'),拿到一堆APIs就开始干活,无非是2个8位拼成16位,还不就是做程序,好,你做程序员,就算你做系统程序员,你写个OS之类的,下面也是用别人做好的指令,你不会去设计微指令吧,流水线也不用管,cache也透明,剩下的东西,还不就是编程,做应用程序员,站在XP上干活,站在linux上干活,到你去做的事情,还是编程。我想说的是,‘程序’可以代替一个词‘逻辑’,而逻辑就是计算机的全部,至少当前的冯计算机,不同的只是大家所处的层次不同(越低级的人越少,但是我不同意越赚钱)。 而程序是=数据结构+算法,数据结构是精心地准备好数据,将那些信息以一定的形式一定的逻辑组织在一起,以使算法的效用达到最大,算法是所有程序的核心,可以看成程序本身,也可以这样比,算法是无形的,而程序是有形的,不管你如何实现,算法是发挥最大作用的东西,而程序是算法的某个实例。 做IT这行,只要是做技术的,只要把算法学好,动手能力强,不管做哪一行(计算机行也分很多)都会很吃香,剩下的只是工具的问题,实现的具体环境,熟能生巧嘛,越是高级的工具其实越容易上手,少数可能门槛比较高,但也都没有算法本身重要。 好了不多说了,本文是想把小站的内容做个链接,做个目录,以下是目录。
目录 1 基础算法 排序由浅入深(一)::选择排序
排序由浅入深(二)::交换排序
排序是算法的切入点,这两篇可能也没什么深度,现在看,那些个经典的排序算法,要时刻牢记于心,那会是一种算法设计泛型,比如快排,归并,基数排序,桶排等。 穷举搜索::回溯与深搜
分......

阅读全文(9553) | 评论:15

数独的难度评价(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。......

阅读全文(8661) | 评论:5

到底应该如何分类?(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破坏类的封闭性,本质上就是一种耦合。 我的一点感想,还在学习中。......

阅读全文(4133) | 评论:1

关于人工神经网络(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......

阅读全文(7753) | 评论:3

[2006/07/24]逼角棋(2006-07-24 13:58:00)

摘要:昨天和爷爷聊天,聊到我唯一的一个幺嗲嗲(我爷爷的弟弟),那年他仙逝我才三岁,农村里老人家过逝也是喜事,叫白喜事,要整顿酒,很多客人很热闹,那时我很聪明,我爸说的,刚教我走逼角棋,就在那一天,我赢了另外一个嗲嗲一盘棋,然后就不再下了,赢了就跑! 逼角棋的棋盘是这样的: 一方棋子是圈,一方是叉,可以随手用粉笔在地上画一个,然后用任何不同的东西做棋子,规则是棋子延着边线走,当已方的两个棋子将对方的一个棋子逼到一个角时,就吃了这颗子,直到全部吃光时胜。 呵呵,小时候的游戏啊! 今天我的黑白棋程序终于有点进展了,总算是界面部分做得差不多了,今天还做了位棋盘,我不会PS,棋盘和棋子是一个朋友帮画的,画得很棒,非常感谢! ......

阅读全文(4661) | 评论:4

家里的旧电脑差点罢工(2006-07-15 11:40:00)

摘要:回到家这是第五天了,家里的一台电脑是赛扬466的,跑WIN98,因为不想太难为它,就算这样昨天她还是发了次脾气。

具体情况是这样的,那天下午想上会网,按了电源后,正在启动,启动画面都出现了,突然显示器上下晃得厉害,好像电视机没有信号的样子,然后显示器倒数秒,10秒钟后显示器shut down,于是我按了一下电脑的复位键,再次启动的时候,‘嘀~嘀~’,长长的响了两声,然后显示器没任何反应漆黑一片,然后我又按了一下复位键,响都不响,显示器照样漆黑一片,就CPU风扇在那呼呼的响。

没修电脑的经验,我的第一感觉是显示器坏了,因为系统在没有检查到标准输出设备时是不进行启动的,然后我就把显示器接显示卡的接头拔了,再试一次,显示器没有黑屏,而是显示了一条英文,大概意思简单来说就是‘No singal’,这和前面的现象不一样,于是我就觉得不是显示器坏了。

然后我就怀疑是显卡坏了,找来把螺丝刀,把显卡拆了,刷灰,擦金手指,忙了半天,再放回去,重启,还是不行,这样的试了好几次,忙得一头是汗,没有成果。我甚至要确定是显卡坏了。

后来一想,不对呀,要是没有标准输出设备,系统至少会有一声‘警告’的,现在是任何声音都没有,非常奇怪,于是我就想到,可能是内存条的问题,于是我就拆内存条,我有两个内存条,加起来192MB,我把显卡先弄好成原来的样子,再把其中一块拔出来,重启,还是一样,一声不吭,我又擦干净了放回去,咦,再开机它有‘嘀’的响声了,但是显示器画面停在了内存检查那步,还是卡死了,没有后文,不过有希望了,至少我知道是附加内存没有接好,系统检测的内存有错误,于是我拆下另外一条内存条,在我擦这个内存的时候试了下启动,系统可以正常进入,但内存只有64MB,这时才放下心来,至少其它的没有坏,如此折腾了半天,才确定是我手上这块内存条有问题。唉,修电脑真麻烦~!

后来?后来我擦了好多次,再把‘坏’的那块内存条装上去,又好了,一切正常了现在。电脑就像女人啊,不过我这台电脑算是脾气好了,已经是用她五六年了,就发过两三次脾气而已,其它时候还是挺和睦相处的。

2006/07/15......

阅读全文(4215) | 评论:2

重读《悟空传》(2006-04-11 15:01:00)

摘要:  《悟空传》是本好书,任何年龄的人读都有不同的收获,我中学的时候第一次读,全当成笑话书,也是完全可以的。
  悟空,有一个好名字,同样也注定有不同的一生。它不像《西游记》把悟空太过神化绝对化完美化,这里的悟空更加有血有肉一些,同样也包括另外一些人物,比如八戒、玄奘等。从人物的角度看,这是一本不错的小说。
  我觉得非常经典的一回,少年玄奘和云游法师斗法的一回:

----------

第七回

--------------------------------------------------------------------------------

  她化成一只纯白百灵来到大殿窗边,这里最多的是山雀,但她怎么能变那种俗鸟呢? 
  殿内坐了一地和尚,中间有两个老的。一个持禅杖,身边还有包袱,象是外地云游到此的。另一个自然就是本寺的主持了。 
  “法明长老,久闻金山寺佛法昌盛,特来请教。”那持禅杖的老和尚道。 
  “天杨师父,不敢。” 
  “什么不敢?”天杨忽厉声道,“敢做不敢应么?” 
  法明长老一愣,才悟道这就开始论法了,于是一笑答道:“敢应不敢放。” 
  “放下!” 
  “我两手皆空,放什么?” 
  “那为什么还抓着?” 
  “心有灵犀。” 
  两人一问一答,问的凶答的快,只听的两旁僧人议论纷纷。 
  “你听懂了么?”“没有啊?”“哎,太高深了。”“真是玄机啊!” 
  小白龙只找那玄奘,却见他在人群之中,正向这边看着她。 
  小白龙心一跳,只觉脸要红了,忽发现自己是一只鸟,他看不见脸红的。 
  只见玄奘对她笑了一笑。 
  这人莫不是认得我?小白龙想,不可能的,他不过一凡人而已啊。 
  这边论答已到了关键时刻,两个老和尚头上都起了白烟。 
  天杨:“如何是禅?” 
  法明:“是。” 
  天杨:“如何是正法眼?” 
  法明:“不是。” ......

阅读全文(5177) | 评论:2

我喜欢的台球游戏(2006-04-11 14:49:00)

摘要:  昨天突然想玩台球游戏,我就想起了两三年前玩的雅虎的台球游戏,我敲cn.games.yahoo.com打开久违了的游戏页面,选了Break It Up全球游戏室。
  这个台球游戏很朴素,8球美式打法,跟我家乡的街头台球打法差不了多少。
  来这里打球的人都是来自全球各地的,我偶尔甩两句我那破E语和人搭话,我发现大多数说英语的人都很有礼貌,他们喜欢台球但不争强好胜,打出好球会称赞你,自己打得不好就会笑一笑。
  我虽不太喜欢英语,但和人交流的感觉还不错,这里都会说省略语,比如:ns:nice shot,gg:good game,ty:thank you,thx,thanks,lol,laugh out l..(就是笑一笑啦)。
  我非常喜欢台球啊,虽然是一个人参与,但感觉我像是教练,而桌上八个小球都是我的队员,我会一个一个进球,直到黑球轻松完成游戏,整个是一个完整的:小球、黑球还有我和我的球杆。
  我想我变了不少,我从一个与人争强(当然也可以说成是上进)一个自以为是一个目中无对手的孩子,慢慢成熟起来。......

阅读全文(7062) | 评论:5